BFS: Correctness and Properties

What We Need to Prove

When BFS terminates, for every vertex $v$ reachable from source $s$, the value $v.d$ equals the true shortest-path distance $\delta(s, v)$ (the minimum number of edges on any path from $s$ to $v$). For unreachable vertices, $v.d = \delta(s, v) = \infty$. Additionally, following predecessor $\pi$ pointers backwards from any vertex reconstructs a shortest path to $s$.

The proof proceeds through three lemmas, culminating in a contradiction argument that no vertex can be the “first” to receive a wrong distance.

Lemma 1: Upper Bound on Neighbour Distance

If $(u, v) \in E$, then $\delta(s, v) \le \delta(s, u) + 1$.

Proof: If $u$ is unreachable from $s$, then $\delta(s, u) = \infty$ and the inequality trivially holds. If $u$ is reachable, the shortest path to $v$ is at most the shortest path to $u$ plus one more edge $(u, v)$. It cannot be longer than that (though it could be shorter if there is a path to $v$ that bypasses $u$). Hence the inequality.

Lemma 2: $v.d$ Never Underestimates

On termination, for all $v \in V$, we have $v.d \ge \delta(s, v)$.

Proof by induction on the number of enqueue operations:

Base case: Immediately before the while loop begins: $s.d = 0 = \delta(s, s)$, so the hypothesis holds for $s$. For all other vertices, $v.d = \infty \ge \delta(s, v)$, even if unreachable. Hypothesis holds.

Inductive step: The while/for loops only change $v.d$ when $v$ is white (not pending), via the assignment $v.d = u.d + 1$. By the induction hypothesis, $u.d \ge \delta(s, u)$. Then: $v.d = u.d + 1 \ge \delta(s, u) + 1 \ge \delta(s, v)$ where the last inequality is Lemma 1. Since $v.d$ is never changed again (it becomes grey immediately), the property persists.

This lemma says the algorithm never reports a distance too low; it may overestimate until convergence.

Lemma 3: Queue Disciplines the Order

Queue property $\phi$: If the queue is $Q = v_1, v_2, \ldots, v_x$ (head to tail), then $v_x.d \le v_1.d + 1$ and the $v.d$ values are non-decreasing from head to tail: $v_i.d \le v_{i+1}.d$ for all $i = 1, \ldots, x-1$.

Proof by induction on queue operations.

• Dequeue: Removing $v_1$ leaves $v_2$ as the new head. From $\phi$ we have $v_x.d \le v_1.d + 1 \le v_2.d + 1$ (since $v_1.d \le v_2.d$). So $\phi$ holds after dequeue.
• Enqueue: When $v$ (with $v.d = u.d + 1$) is appended, we need to verify $v_1.d \le \cdots \le v_x.d \le v.d$ and $v.d \le v_1.d + 1$. The first holds because $v_x.d \le u.d + 1$ (from $\phi$ before dequeue, $v_x.d \le v_1.d (= u.d) + 1 = u.d+1 = v.d$). The second holds because $v.d = u.d + 1 = v_1.d + 1$.

Corollary: If vertex $a$ is enqueued before vertex $b$, then $a.d \le b.d$ on termination. This follows from the non-decreasing property when $a$ and $b$ are simultaneously in the queue and from transitivity of $\le$ when they are not.

Termination: Proof by Contradiction

Assume the algorithm errs. Let $v$ be the vertex with minimum $\delta(s, v)$ whose $v.d \neq \delta(s, v)$. By Lemma 2, we must have $v.d > \delta(s, v)$. Also $v \neq s$ (since $s.d = 0$ is correct), and $v$ must be reachable from $s$ (otherwise $\delta(s,v) = \infty \ge v.d$).

Let $u$ be the immediate predecessor of $v$ on a true shortest path $s \leadsto v$. Then $\delta(s, u) = \delta(s, v) - 1$. Since $\delta(s, u) < \delta(s, v)$ and $v$ is the minimum-$\delta$ vertex with a wrong $d$, we have $u.d = \delta(s, u)$. Hence: $v.d > \delta(s, v) = \delta(s, u) + 1 = u.d + 1$

Now consider the moment $u$ was dequeued from $Q$. Vertex $v$ was in exactly one of three states:

1. Not yet enqueued (white): The inner loop would explore the edge $(u, v)$ and set $v.d = u.d + 1$. But we have $v.d > u.d + 1$ — contradiction.
2. In the queue (grey, pending): $v$ was enqueued earlier by some $w$ with $v.d = w.d + 1$. By the corollary, $w.d \le u.d$ (since $w$ was enqueued before $u$ was dequeued, and $u$ was dequeued before $v$, so $w \le u \le v$ in dequeue order). Thus $v.d = w.d + 1 \le u.d + 1$, contradicting $v.d > u.d + 1$.
3. Already dequeued (black): By the corollary, $v.d \le u.d$, contradicting $v.d > u.d + 1$.

All three cases produce contradictions. Therefore no such $v$ exists; BFS computes correct distances for all vertices.

Shortest-Path Tree

The predecessor subgraph $G_\pi = (V_\pi, E_\pi)$ where $V_\pi = \{v \mid v.\pi \neq \text{NIL}\} \cup \{s\}$ and $E_\pi = \{(\pi[v], v) \mid v \in V \setminus \{s\}\}$ forms a breadth-first tree. It is a tree because each vertex (except $s$) has exactly one predecessor and no cycles exist. The unique path in $G_\pi$ from $s$ to any reachable $v$ is a shortest path in $G$.

Applications

Application	How BFS solves it
Unweighted shortest paths	$v.d = \delta(s,v)$ in edge count
Bipartite testing	Colour layers alternately; check for conflicts
Connected components	BFS from any unvisited vertex; repeat
Web crawling	Explore by link distance from seed
Social network analysis	Degrees of separation via BFS depth

Summary

Property	Statement
Lemma 1	$\delta(s,v) \le \delta(s,u) + 1$ if $(u,v) \in E$
Lemma 2	$v.d \ge \delta(s,v)$ at all times
Lemma 3	Queue has at most 2 consecutive $d$ values
Correctness	$v.d = \delta(s,v)$ for all $v$ on termination
Predecessor tree	$(\pi[v], v)$ edges form a BFS tree rooted at $s$

Past paper questions: y2025p1q9(a)(i) (BFS time analysis with different representations).