Introduction

I will explain the implementation of breadth-first search using python. (Just put the one I always implement.) Breadth-first search often raises the issue of distance, so this time we will implement a function that returns the distance from one vertex to each vertex.

Breadth-first search

I think that a lot of general knowledge about breadth-first search will come out if you look it up, so I will omit it in detail, but I will explain it briefly. 　　　 As shown by the blue arrow, follow the vertices in order from the closest one. For the distance to be handled this time, add 1 to the distance to the previous vertex. (In the image, it is shaken from 1, but if it is a distance, you can shake it from 0.) The order of searching for this vertex is managed by the queue. A queue is a first-in, first-out data structure. In this example, the start 0 is entered first. ([0]) Next, take out the contents from the front and examine the adjacent vertices. (1 and 2 this time) If you are visiting for the first time, add it to the queue. ([1, 2]) If you repeat this, you can examine the vertices in the order of the blue arrows. （[2, 3, 4]→[3, 4, 5, 6]→[4, 5, 6, 7]...） The search ends when the queue is empty. thank you for your hard work.

Implementation

input

Given the number of vertices n and the number of edges m, then the adjacent vertices are given over m rows.

code

import sys
input = sys.stdin.readline

n, m = [int(x) for x in input().split()] #n is the number of vertices, m is the number of sides
g = [[] for _ in range(n)] #Adjacency list

for _ in range(m):
    a, b = [int(x) for x in input().split()]
    g[a].append(b)
    g[b].append(a)

from collections import deque

def bfs(u):
    queue = deque([u])
    d = [None] * n #Initialization of distance from u
    d[u] = 0 #Distance to myself is 0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
    return d

#Distance of each vertex from 0
d = bfs(0)
print(d)

output

Outputs a list with the distance from vertex 0 in order of vertex number from the left. The distance to you is 0, and the vertices you cannot reach are None.

[0, 1, 1, 2, 2, 2, 2, 3, 3, 4, None]

in conclusion

Please let me know if you have any mistakes! I would be grateful if you could give me some advice!

Algorithm in Python (breadth-first search, bfs)