← Browse / Graphs

Algorithm BFS: Breadth-First Search

Moore (1959, "The shortest path through a maze") and Lee (1961, routing on circuit boards). The same algorithm, discovered independently.

Graphs

Given an undirected graph $G = (V, E)$ and a $source$ vertex $s \in V$, find the shortest-path distance from $s$ to every other reachable vertex, measured in edges. As a side effect, also produce the BFS tree: a parent pointer for each reached vertex that lets you reconstruct a shortest path back to $s$.

Why BFS matters. This is the algorithm interviewers reach for when the problem says "shortest path on an unweighted graph" — and it's the substrate underneath a huge family of grid problems (shortest path in a maze, minimum moves to reach a state, multi-source BFS, 0-1 BFS, bidirectional search). On weighted graphs you graduate to Dijkstra (which we'll ship as a separate Knuth topic); BFS is Dijkstra's special case when every edge weight is 1.

The FIFO invariant. The whole correctness story rests on one structural property: the queue is FIFO, so vertices come out in the same order they went in. Combined with the rule "only enqueue a vertex the first time you reach it," this guarantees the queue at any moment contains at most two consecutive distance layers: a (possibly empty) prefix of vertices at distance $k$ from the source, followed by a suffix of vertices at distance $k+1$. When all the distance-$k$ vertices have been dequeued and processed, the queue contains only distance-$(k+1)$ vertices, which then expand into distance-$(k+2)$ ones, and so on. This is why every dequeue at S2 reports a distance one more than the previous "layer" — and why the first time you reach any vertex is automatically the shortest way to reach it.

BFS vs. DFS. Both are graph traversals; the only difference is queue (FIFO) vs. stack (LIFO). That single substitution flips every property:

If you're shipping a graph algorithm in an interview, ask first which property you need. "Find any path" → DFS is fine and uses less memory. "Find a shortest path on an unweighted graph" → BFS or Dijkstra-with-weight-1.

One S3 emit per neighbor, even on skip. Most pseudocode glosses over the visited check ("if w not visited, do..."). The trace below emits one S3 step for every neighbor, including the ones that get skipped because they're already visited. This matters because the skip case is where a huge fraction of real-world BFS time goes — graphs with lots of edges per vertex (social networks, search-space exploration) hit the visited check far more often than they hit the "first visit" case. Watching the trace step through skip events makes the $E$ in $\Theta(V + E)$ visible.

Step labels — why "S" and not "B"? Algorithm B (Binary Search) already claimed B1–B5 in the same Knuth library. Rather than collide on the unified review-card surface, BFS uses S1–S5 ("S" for Search). The same convention will hold for DFS when we ship it — it'll get its own letter prefix scoped per topic, with the slug carrying the algorithm name (/knuth/dfs).

Pick a preset graph in the playground below and step through the search. Watch the queue grow when distance-$k$ vertices enqueue distance-$(k+1)$ vertices, watch it drain as the wave moves outward, and watch the BFS tree (highlighted edges) emerge.

Computation Method

S1
Initialize
Set $\textit{queue} \leftarrow [source]$, $\textit{visited} \leftarrow \{source\}$, $\textit{dist}[source] \leftarrow 0$. All other distances are $-1$ (unreached) and all parents are $-1$ (none). This is the seed of the breadth-first wave.
$\textit{queue} \leftarrow [s],\ \textit{visited} \leftarrow \{s\},\ \textit{dist}[s] \leftarrow 0$
S2
Dequeue
If the queue is empty, the search is complete — go to S5. Otherwise pop the front of the queue: $v \leftarrow \textit{queue}.\text{pop\_front}()$. FIFO order is the heart of BFS — it guarantees we visit vertices in increasing order of distance from the source.
$\textit{queue} = \varnothing \rightarrow$ goto S5; else $v \leftarrow \textit{queue}.\text{pop\_front}()$
S3
Inspect neighbor
For each neighbor $w \in \text{adj}[v]$: if $w$ is unvisited, mark it visited, set $\textit{dist}[w] \leftarrow \textit{dist}[v] + 1$, set $\textit{parent}[w] \leftarrow v$, and enqueue it. If $w$ is already visited, skip it — its current distance is already optimal. The playground emits one S3 step per neighbor, including the skipped ones, so you can see the visited check fire.
$\forall w \in \text{adj}[v]$: if $w \notin \textit{visited}$ then $\textit{visited} \leftarrow \textit{visited} \cup \{w\}$, $\textit{dist}[w] \leftarrow \textit{dist}[v]+1$, $\textit{parent}[w] \leftarrow v$, $\textit{queue}.\text{push\_back}(w)$
S4
End of neighbor list
After inspecting all of $v$'s neighbors, return to S2 to dequeue the next vertex. This is a no-op book-keeping step — included so each iteration has a clean ending in the labeled trace.
goto S2
S5
Done
The queue is empty. Every vertex reachable from $source$ has been visited and assigned the correct shortest-path distance. Unreached vertices keep their initial $\textit{dist} = -1$ marker, indicating no path exists in the graph.
return $\textit{dist},\ \textit{parent}$

Why It Works

Key Identity
$$\text{For all reached } v: \textit{dist}[v] = \min\{\,|\,P\,| : P \text{ is a } source \to v \text{ path}\,\}$$

BFS visits vertices in *non-decreasing order* of distance from the source. The proof is by induction on distance. Base: $\textit{dist}[source] = 0$, set at S1. Inductive step: assume every vertex at distance $\leq k$ from source has been correctly assigned $\textit{dist}$ and enqueued before any vertex at distance $> k$. The FIFO queue then dequeues all distance-$k$ vertices before any distance-$(k+1)$ vertex, so when we process a distance-$k$ vertex $v$, every unvisited neighbor $w$ must be at distance exactly $k+1$ (not less, because all distance-$\leq k$ vertices are already visited; not more, because $v$ is at distance $k$ and there's an edge $v$–$w$). Therefore $\textit{dist}[w] \leftarrow k+1$ is correct, and the invariant extends to distance $k+1$. The same argument shows $\textit{parent}[w] = v$ gives a valid shortest-path tree: following parent pointers backwards from any reached $w$ reconstructs a path of length $\textit{dist}[w]$ to the source.

Interactive Trace

Pick a preset graph and step through the search. The current vertex (v) is outlined in accent, its neighbor under inspection (w) in warning, and the BFS-tree edges thicken in accent as the search progresses. Queue, visited set, and per-vertex distance + parent update on every step.

Complexity: $\Theta(V + E)$ / Space: $\Theta(V)$ — Each vertex is enqueued at most once (the visited check at S3 prevents re-enqueuing) and dequeued at most once at S2, giving $\Theta(V)$ work in the outer loop. Each edge $(u, v)$ is inspected at most twice in total — once when $u$ is dequeued and we scan $\text{adj}[u]$, once when $v$ is dequeued and we scan $\text{adj}[v]$ — giving $\Theta(E)$ work in the inner loop. Space is dominated by the visited bitmap, distance array, parent array, and the queue itself, each $\Theta(V)$. The $\Theta(V+E)$ bound is tight: any algorithm that produces shortest-path distances must inspect every edge in the worst case (consider a graph where the only path uses every edge).

Review Cards

Conceptual Step
What does step S5 do in Breadth-First Search, and why does it guarantee progress toward termination?
Invariant
What mathematical identity ensures correctness at each step of Algorithm BFS?
When to Use
When would you reach for Breadth-First Search over alternative approaches?
Complexity
What is the time complexity of Breadth-First Search?