Breadth-First Search
Motivation
Given a graph and a starting node, breadth-first search (BFS) visits every reachable node by expanding outward one level at a time (Russell and Norvig 2020). Because it exhausts all nodes at depth \(d\) before any node at depth \(d+1\), it finds the shallowest solution in any search problem with uniform edge costs.
Problem
A search problem consists of:
- A graph \(G = (V, E)\), directed or undirected
- A start node \(s \in V\)
- A goal test \(\text{goal} : V \to \{\text{true}, \text{false}\}\)
The depth of a node is its distance from \(s\) in number of edges. The branching factor \(b\) is the maximum number of successors of any node.
Algorithm
BFS maintains a queue (FIFO) of nodes to visit and a set of visited nodes to avoid revisiting.
- Enqueue \(s\); mark \(s\) as visited.
- While the queue is non-empty:
- Dequeue node \(v\).
- If \(\text{goal}(v)\), return \(v\).
- For each unvisited neighbor \(w\) of \(v\): mark \(w\) visited, set \(\text{parent}(w) = v\), and enqueue \(w\).
- Return failure.
The visited check happens at enqueue time, not dequeue time, which prevents the same node from entering the queue more than once. Recording \(\text{parent}(w)\) at enqueue time is optional but lets us reconstruct the path from \(s\) to any visited node by tracing pointers backward from the goal and reversing.
Walkthrough
Layer numbering
Starting from \(s\), BFS dequeues nodes in non-decreasing order of depth. The first node dequeued is \(s\) at depth \(0\); then all neighbors of \(s\) at depth \(1\); then their unvisited neighbors at depth \(2\); and so on. Recording the depth at which each node is first enqueued labels every reachable node with its distance from \(s\) in edges.
The dequeue order respects layers: every node at depth \(d\) is dequeued before any node at depth \(d+1\). Note that node \(d\) has two layer-1 neighbors (\(a\) and \(b\)), but it is only enqueued once — by whichever neighbor is dequeued first — because the visited check at enqueue time blocks the second enqueue.
Queue state and parent pointers
Use the same graph with start node \(s\), expanding neighbors in alphabetical order. The table below tracks the queue contents and parent pointer assigned each time a node is enqueued.
| Dequeue | Enqueue | Parent set | Queue after step |
|---|---|---|---|
| — | s | parent[s] = none | [s] |
| s | a, b, c | parent[a,b,c] = s | [a, b, c] |
| a | d (first visit) | parent[d] = a | [b, c, d] |
| b | e (first visit) | parent[e] = b | [c, d, e] |
| c | f (first visit) | parent[f] = c | [d, e, f] |
| d | g (first visit) | parent[g] = d | [e, f, g] |
| e | — (d,f visited) | — | [f, g] |
| f | — (g visited) | — | [g] |
| g | — | — | [] |
To recover the path from \(s\) to \(g\): trace parent pointers backward — \(g \leftarrow d \leftarrow a \leftarrow s\) — then reverse: \(s, a, d, g\). This path has length 3, which equals \(g\)’s layer number, confirming it is shortest.
Note that \(d\) is only enqueued once (by \(a\) at depth 1) even though \(b\) also has an edge to \(d\); when \(b\) is dequeued, \(d\) is already marked visited so the second enqueue is skipped.
Complexity and Tradeoffs
Time complexity. On an explicit graph \(G = (V, E)\), BFS visits each vertex once and inspects each edge a constant number of times, giving \(O(V + E)\). When the graph is implicit and bounded by branching factor \(b\) and goal depth \(d\) — as in tree-style search where vertices are not enumerated in advance — the same bound expressed in those parameters is \(O(b^d)\).
Space complexity. On an explicit graph, BFS stores the visited set and queue, both at most \(O(V)\). In tree-style search the queue holds the entire current frontier, \(O(b^d)\). Space is the binding constraint for BFS on large graphs.
Important tradeoffs:
- Completeness: BFS finds a solution if one exists, provided the graph is finite or the solution is at finite depth.
- Optimality: among solutions, BFS returns the one at minimum depth. For graphs where all edges have equal cost, minimum depth equals minimum cost. (proof)
- Memory vs. shallowness: BFS pays \(O(b^d)\) memory to guarantee shallow solutions. DFS trades that guarantee for \(O(bm)\) memory; iterative deepening recovers shallowness with DFS-style memory by paying extra time.
When to Use It
BFS is the right choice whenever the shallowest solution is required, when distances in number of edges are needed, or when memory permits exploring the full frontier.
- Find the nearest node satisfying a property \(P\): the first node dequeued where \(P(v)\) holds is guaranteed to be at minimum depth. (proof)
- Find all nearest nodes: continue dequeuing until the depth increases past the first match.
- Find all reachable nodes satisfying \(P\): remove the early-return and collect every \(v\) where \(P(v)\) holds.
- Single-source shortest paths in unweighted graphs: the layer at which each node is enqueued is its shortest-path distance from \(s\). For weighted graphs, see Dijkstra’s algorithm, which generalizes BFS to non-negative weights.
- Path reconstruction: parent pointers stored at enqueue time recover any shortest path back to \(s\).