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.
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.
Given the number of vertices n and the number of edges m, then the adjacent vertices are given over m rows.
11 9
0 1
0 2
1 3
1 4
2 5
2 6
3 7
5 8
8 9
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)
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]
Please let me know if you have any mistakes! I would be grateful if you could give me some advice!
Recommended Posts