Breadth-first search & shortest paths — COMP 372

What BFS computes

Given a graph $G$ and a source $s$ , breadth-first search discovers every vertex reachable from $s$ and computes $v . d = δ (s, v)$ , the minimum number of edges on any $s$ -to- $v$ path. It also builds a breadth-first tree via parent pointers $v . π$ , 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 . π = u$ , turns gray, and is enqueued. When $u$ 's list is exhausted, $u$ turns black.

Why $Θ (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} ∣ A d j [u] ∣ = Θ (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 $π$ pointers from the target back to $s$ and reverse: the path to $u$ is $s \to w \to t \to u$ , length $3 = δ (s, u)$ . PRINT-PATH does this recursively — recurse to $v . π$ first, print $v$ on the way out, so the path prints in forward order in $O (path length)$ .

Round 1. s has been dequeued and its list scanned, so r and w are discovered (gray, d = 1) and queued. The queue holds exactly the gray vertices — the frontier between explored and unexplored.

Round 2. Dequeuing r then w discovers the whole d = 2 layer in one go. FIFO order is what guarantees it: every distance-1 vertex is dequeued before any distance-2 vertex. (u and y, at d = 3, are off-figure.)

Following π back from u and reversing gives s → w → t → u: three edges, exactly δ(s,u) = 3. Every root-to-vertex path in this tree is a shortest path.