Breadth First Search

Python C++

  • Input:
    • directed or undirected unweighted graph with N nodes and M edges
    • source node
  • Output:
    • array distance of length N, where:
      • distance[i] - the shortest distance from source node to node i if i is reachable
      • distance[i] = $\infty$ otherwise
  • Time complexity: $O(N + M)$

Description

Initialization

Create a queue which will contain the nodes to be processed.

Initially, push the source node to the queue and set distance[source_node] = 0, and for all other nodes v set distance[v] = -1.

Loop iteration

Loop until the queue is empty and in each iteration, pop a node u from the front of the queue. Iterate through all the edges going out of this node u and if some of these edges go to nodes that are not already visited (i.e. distance[v] = -1), set distance[v] = distance[u] + 1 and place them in the queue.

Example

Let's see how the Breadth First Search algorithm works with an example. We use an undirected graph with 5 nodes.

We start from node 1. The BFS algorithm starts by putting it in the queue and setting distance[1] = 0.

Next, we iterate through all the edges from node 1, adding all unvisited neighbours (node 2, node 3) to the queue and setting distance[2] = 1 and distance[3] = 1.

Next, we iterate through all the edges from node 2, adding all unvisited neighbours (node 4) to the queue and setting distance[4] = 2.

Next, we iterate through all the edges from node 3, adding all unvisited neighbours (node 5) to the queue and setting distance[5] = 2.

After we visit the node 4, it doesn't have any unvisited adjacent nodes, so we just pop it from queue. Same for node 5, so we have completed Breadth First Search.

Code

Python 

                        def bfs(
                            graph: Dict[int, List[int]],
                            source_node: int,
                        ) -> List[int]:
                            from collections import deque
                        
                            n = len(graph)
                            distance = [-1] * n
                            distance[source_node] = 0
                            queue = deque([source_node])
                            while queue:
                                u = queue.popleft()
                                for v in graph[u]:
                                    if -1 == distance[v]:
                                        distance[v] = distance[u] + 1
                                        queue.append(v)
                            return distance
C++