Breadth-first search (BFS) explained: how it works, code and complexity

What problem BFS solves

Many problems are graphs in disguise: web pages and links, friends in a social network, squares on a game board, states of a puzzle. BFS answers two common questions about such a graph: which nodes can I reach from a start node, and what is the smallest number of steps to reach each of them?

Because BFS explores in rings of increasing distance, the first time it reaches a node is always along a path with the fewest edges. This makes it the standard algorithm for shortest paths when every edge has the same cost.

The idea in plain words

1. Put the start node in a queue and mark it as visited.
2. Take the node at the front of the queue.
3. For each neighbor that is not visited yet, mark it as visited and add it to the back of the queue.
4. Repeat steps 2 and 3 until the queue is empty.

Mark a node as visited when you add it to the queue, not when you take it out. Otherwise the same node can be added many times before it is processed.

Worked example, step by step

Take this undirected graph: A–B, A–C, B–D, C–D, C–E, D–F. Start at A and visit neighbors in alphabetical order.

The visiting order is A, B, C, D, E, F. D is reachable from both B and C, but it is discovered only once, from B, because it is marked as visited at that moment.

Python implementation

Use collections.deque for the queue: popleft() is O(1), while list.pop(0) is O(n). The graph is a dictionary that maps each node to a list of neighbors (an adjacency list).

from collections import deque
def bfs(graph, start):
    """Return the distance (number of edges) from start to each reachable node."""
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nxt in graph[node]:
            if nxt not in dist:          # not visited yet
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return dist
graph = {
    "A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"],
    "D": ["B", "C", "F"], "E": ["C"], "F": ["D"],
}
print(bfs(graph, "A"))  # {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3}

Here the dist dictionary does double duty: it is the visited set and it stores the answer. To rebuild the actual path, also store the parent of each node and walk back from the target.

def shortest_path(graph, start, goal):
    parent = {start: None}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == goal:
            path = []
            while node is not None:
                path.append(node)
                node = parent[node]
            return path[::-1]
        for nxt in graph[node]:
            if nxt not in parent:
                parent[nxt] = node
                queue.append(nxt)
    return None  # goal not reachable
print(shortest_path(graph, "A", "F"))  # ['A', 'B', 'D', 'F']

Time and space complexity

V is the number of vertices (nodes) and E the number of edges. With an adjacency matrix instead of lists, the time becomes O(V²) because finding the neighbors of a node costs O(V).

Variants and common mistakes

• Grid BFS: treat each cell as a node and the four (or eight) neighboring cells as edges. Check bounds and walls before adding a cell.
• Multi-source BFS: put several start nodes in the queue at distance 0. This finds the distance to the nearest source, for example the nearest exit in a maze.
• 0-1 BFS: when edge weights are only 0 or 1, use a deque and push 0-weight neighbors to the front. It gives shortest paths in O(V + E).
• Bidirectional BFS: search from the start and the goal at the same time and stop when the two frontiers meet. It often explores far fewer nodes.
• Level-by-level processing: record len(queue) at the start of each round and pop exactly that many nodes to handle one level at a time.

When to use BFS and real-world uses

• Interview problems: shortest path in a maze or grid, word ladder, rotting oranges (multi-source BFS), binary tree level-order traversal, minimum number of moves for a knight.
• Networks: finding all devices within k hops, broadcast in peer-to-peer networks, "people you may know" at distance 2 in a social graph.
• Web crawlers that visit pages in order of link distance from a seed page.
• Garbage collectors (for example Cheney's copying collector) and puzzle solvers that need the fewest moves.