Breadth First Search (BFS)

BFS is a simple graph traversal algorithm that explores all vertices of a graph reachable from the source. It uses a queue to keep track of the vertices to be explored. It has the following common applications:

1. Finding the shortest path between two nodes in an unweighted graph
2. As a subroutine in the Ford-Fulkerson method to compute the max flow in a flow network
3. Testing the bipartite-ness of a graph

Algorithm

The idea behind BFS is to explore/visit all the neighbours of a node before moving on to the next level of nodes. We maintain a queue of nodes to process. We start from the root node, mark it as visited, and then add all of its neighbours that are not yet visited into the queue to be explored. We repeat this process as long as there are nodes in the queue.

Pseudocode

procedure BFS(G, root) is
    let Q be a queue
    label root as explored
    Q.enqueue(root)
    while Q is not empty do
        v := Q.dequeue()
        if v is the goal then
            return v
        for all edges from v to w in G.adjacentEdges(v) do
            if w is not labeled as explored then
                label w as explored
                w.parent := v
                Q.enqueue(w)

Implementation

from collections import deque

def bfs(graph, root, process=None):
    """
    Visits all nodes in a graph using BFS
    """
    visited = set()
    queue = deque([root])
    visited.add(root)

    while queue:
        node = queue.popleft()
        if process:
            process(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return visited