Breadth-first search (BFS) is a standard algorithm for finding a node in a graph. Starting at a given node, all neighbors are examined. Then all neighbors of neighbors are visited if they have not yet been visited, and so on. Typically, this is implemented with a queue of nodes to visit. The queue is primed with the staring node. While the queue is non-empty, the next node to visit is dequeued and each of its unvisited children is enqueued. If the queue empties before a node is found, there must not be a path from the starting node to the target node. Assuming each edge in the graph has the same (non-negative) length/weight, BFS will find the length of the shortest path from the starting node to each other node that can be reached from it.
In this implementation, we store the graph as an “adjacency list” using a Python dictionary. Since the graph is undirected, we need to make two entries for each edge. The dists object serves double duty. The default value of -1 indicates that the vertex has not been visited. As soon as a node is seen, its (non-negative) distance is calculated, indicating that it doesn’t need to be explored again.
We also use the deque data structure as we are popping from the front of the queue, recalling that calling pop(0) on a Python list takes time $O(n)$ for a list of $n$ elements. While the size of the graph isn’t very large in this case (it’s at most 1000 nodes), we’ll take this opportunity to remind you of the deque data structure which is “list-like” in nature but has fast addition and removal methods for both ends of the “list”.
from collections import defaultdict
from collections import deque
def bfs(n, m, edges, s):
graph = defaultdict(list)
for node1, node2 in edges:
graph[node1].append(node2)
graph[node2].append(node1)
dists = defaultdict(lambda: -1)
dists[s] = 0
queue = deque([s])
while queue:
v = queue.popleft()
for neighbor in graph[v]:
if dists[neighbor] < 0:
queue.append(neighbor)
dists[neighbor] = dists[v] + 6
return [dists[i] for i in range(1, n+1) if i != s]