BFS Finds the Shallowest Solution
Claim
Breadth-first search (BFS) dequeues nodes in non-decreasing order of depth. Consequently, the first goal node dequeued is at the minimum depth among all goal nodes reachable from the start (Russell and Norvig 2020).
Proof
Lemma: nodes are dequeued in non-decreasing depth order.
Let \(d(v)\) denote the depth of node \(v\) (number of edges from the start \(s\)). We prove that if \(u\) is enqueued before \(v\), then \(d(u) \leq d(v)\).
Base case. Only \(s\) is in the queue initially; the claim holds vacuously.
Inductive step. Suppose at some point every node currently in the queue satisfies the depth ordering (earlier-enqueued nodes have depth \(\leq\) later-enqueued nodes). Let \(u\) be dequeued next. Its unvisited neighbors \(w\) satisfy \(d(w) = d(u) + 1\). All remaining nodes already in the queue have depth \(\geq d(u)\) (by hypothesis), so the new nodes \(w\) at depth \(d(u)+1\) are enqueued after all nodes at depth \(d(u)\) and at depth \(\geq d(u)+1\). The ordering is preserved.
By induction, the queue is always ordered by non-decreasing depth, so nodes are dequeued in non-decreasing depth order. \(\square\)
Main result.
Let \(d^*\) be the minimum depth of any goal node. By the lemma, every node dequeued before any goal node has depth \(< d^*\), so no goal node is returned until depth \(d^*\) is reached. The first goal node dequeued therefore has depth \(d^*\). \(\square\)
Corollary (optimality for uniform-cost graphs). If every edge has cost 1, then depth equals path cost. BFS therefore returns an optimal-cost solution.