Breadth-first search & shortest paths

What BFS computes

Given a graph $G$ and a source $s$, breadth-first search discovers every vertex reachable from $s$ and computes $v.d = \delta(s, v)$, the minimum number of edges on any $s$-to-$v$ path. It also builds a breadth-first tree via parent pointers $v.\pi$, and that tree's $s$-to-$v$ path is a shortest path.

BFS uses three colours: white (undiscovered), gray (discovered, frontier), black (fully explored). The central invariant: the FIFO queue holds exactly the gray vertices — the boundary between explored and unexplored. Because the queue is FIFO, BFS expands level by level: all distance-1 vertices before any distance-2 vertex.

The algorithm

Initialise every vertex white with $d = \infty$, set $s.d = 0$, gray $s$, enqueue it. Then repeatedly dequeue a vertex $u$ and scan its neighbours: each white neighbour $v$ gets $v.d = u.d + 1$, $v.\pi = u$, turns gray, and is enqueued. When $u$'s list is exhausted, $u$ turns black.

Why $\Theta(V + E)$ (aggregate analysis). Initialisation is $O(V)$. Each vertex is enqueued and dequeued at most once — the white-check before enqueueing guarantees it — so all queue operations total $O(V)$. Each adjacency list is scanned exactly once, when its owner is dequeued, summing to $\sum_u |Adj[u]| = \Theta(E)$. Total: $O(V + E)$.

Worked example

On the CLRS grid graph with source $s$, BFS assigns distances $s{=}0$; $r, w {=} 1$; $t, v, x {=} 2$; $u, y {=} 3$. To recover a path, follow $\pi$ pointers from the target back to $s$ and reverse: the path to $u$ is $s \to w \to t \to u$, length $3 = \delta(s, u)$. PRINT-PATH does this recursively — recurse to $v.\pi$ first, print $v$ on the way out, so the path prints in forward order in $O(\text{path length})$.