Why BFS Finds Unweighted Distances
In an unweighted graph, every edge has the same cost: one step. The distance from a source to a reachable vertex is therefore the minimum number of edges in a path to it. Breadth-first search (BFS) is designed to find these distances by processing vertices in the order in which they are reached: first the source, then its neighbors, then vertices one edge farther away, and so on. The FIFO queue is essential to that order.
We consider finite graphs. An undirected graph has edges between pairs of vertices; in a directed graph, a step from \(u\) to \(v\) is allowed only when the arc \((u,v)\) is present. The arguments below apply to both. For a source \(s\), \(d(s,v)\) is the minimum number of edges or arcs in a path from \(s\) to \(v\), if such a path exists. If no such path exists, we write \(d(s,v)=\infty\). We assume \(s\in V(G)\), so the source is defined.
The label is the distance estimate maintained by the algorithm. A vertex in the queue has already been labeled but has not yet been processed. Every newly assigned label is one greater than the label of the vertex that caused the assignment. That fact alone does not establish that labels are shortest distances: the queue order must also rule out a shorter route that would have been discovered later.
Queue Order and Layers
Proof. Initially the queue contains only \(s\), with label \(0\), so both claims hold. Suppose the queue is nonempty, its front has label \(k\), and the claims hold. Removing that front leaves a queue whose labels are \(k\) or \(k+1\), still in nondecreasing order. While processing the removed vertex, BFS adds only vertices labeled \(k+1\). They are placed at the back, after any remaining vertices labeled \(k\) or \(k+1\), so the queue remains nondecreasing. If it is nonempty afterward, its front label is either \(k\) or \(k+1\); in the latter case every remaining label is \(k+1\), or is a newly appended \(k+1\). Thus all labels are at most one greater than the new front label. This proves the claims after each iteration. In particular, the sequence of removed labels is nondecreasing. \(\square\)
For each nonnegative integer \(i\), the distance layer \(L_i\) consists of the vertices at distance \(i\) from \(s\). The layers are not merely an interpretation added after BFS: the queue processes their vertices in order. The distance theorem below proves that the labels produced by the algorithm agree exactly with these layers.
Proof. First, every assigned label is the length of a path from \(s\). The source has label \(0\), corresponding to the path of length \(0\). Whenever processing a labeled vertex \(u\) assigns \(\ell(v)=\ell(u)+1\), there is an edge or arc from \(u\) to \(v\). Appending it to a path of length \(\ell(u)\) gives a path of length \(\ell(v)\). By induction over the assignments, every labeled vertex is reachable and \(d(s,v)\leq \ell(v)\).
For the other inequality, take any path \(v_0v_1\cdots v_q\) from \(s\) to a vertex \(v_q\), where \(v_0=s\) and \(q\) is its length. We show successively that every \(v_i\) is labeled with \(\ell(v_i)\leq i\). This holds for \(i=0\), since \(\ell(s)=0\). Suppose it holds for \(i\). The algorithm eventually processes \(v_i\): it is labeled, is enqueued once, and the finite queue process removes every enqueued vertex. Consider \(v_{i+1}\) when \(v_i\) is processed. If \(v_{i+1}\) has no label, the edge or arc from \(v_i\) makes BFS assign it \(\ell(v_i)+1\leq i+1\). If it already has a label, then, unless it is the initially labeled source, it was discovered while processing a vertex \(w\) removed earlier than \(v_i\). By the queue-order lemma, \(\ell(w)\leq\ell(v_i)\), so \(\ell(v_{i+1})=\ell(w)+1\leq\ell(v_i)+1\leq i+1\). If \(v_{i+1}=s\), its label is \(0\leq i+1\) directly. This completes the induction along the path.
If \(v\) is reachable, choose a shortest path of length \(d(s,v)\). The path argument shows that \(v\) is labeled and \(\ell(v)\leq d(s,v)\). The first part of the proof gives \(d(s,v)\leq\ell(v)\), hence equality. If \(v\) is labeled, the first part already gives a path to it, so it is reachable. These implications prove both claims, including that unreachable vertices remain unlabeled. \(\square\)
Tracing the Layers
Worked Example: Layers in an Undirected Graph
Let \(G\) be the undirected simple graph with \(V=\{s,a,b,c,d,e\}\) and \(E=\{sa,sb,ac,bc,bd,cd,de\}\). Start BFS at \(s\), examining neighbors in alphabetical order where a choice arises. The queue is written from front to back; each entry shows its label.
| Action | New labels | Queue afterward |
|---|---|---|
| Initialize | \(s:0\) | \([s:0]\) |
| Remove \(s:0\) | \(a:1,\ b:1\) | \([a:1,b:1]\) |
| Remove \(a:1\) | \(c:2\) | \([b:1,c:2]\) |
| Remove \(b:1\) | \(d:2\) | \([c:2,d:2]\) |
| Remove \(c:2\) | None | \([d:2]\) |
| Remove \(d:2\) | \(e:3\) | \([e:3]\) |
| Remove \(e:3\) | None | \([]\) |
Thus the layers are \(L_0=\{s\}\), \(L_1=\{a,b\}\), \(L_2=\{c,d\}\), and \(L_3=\{e\}\). For example, \(c\) is reached by \(s,a,c\), and \(d\) by \(s,b,d\), each using two edges. The theorem certifies that neither has a shorter path. The edge \(cd\) joins two vertices in the same layer; BFS does not require every edge to join consecutive layers.
Check: The labels are nondecreasing in removal order \(0,1,1,2,2,3\), as the queue-order lemma requires. The displayed paths to \(a,b,c,d,e\) have lengths \(1,1,2,2,3\), respectively, matching their assigned labels.
Worked Example: Directed Distances Need Not Be Symmetric
Let \(G\) be the directed graph with \(V=\{r,a,b,c,d,e\}\) and arc set \(\{(r,a),(r,b),(a,c),(b,c),(c,d),(a,d),(d,e)\}\). Start at \(r\), examining out-neighbors alphabetically. Only arcs in their stated direction may be followed.
| Action | New labels | Queue afterward |
|---|---|---|
| Initialize | \(r:0\) | \([r:0]\) |
| Remove \(r:0\) | \(a:1,\ b:1\) | \([a:1,b:1]\) |
| Remove \(a:1\) | \(c:2,\ d:2\) | \([b:1,c:2,d:2]\) |
| Remove \(b:1\) | None; \(c\) is labeled | \([c:2,d:2]\) |
| Remove \(c:2\) | None; \(d\) is labeled | \([d:2]\) |
| Remove \(d:2\) | \(e:3\) | \([e:3]\) |
| Remove \(e:3\) | None | \([]\) |
The directed distance layers are \(\{r\}\), \(\{a,b\}\), \(\{c,d\}\), and \(\{e\}\). In particular, \(d(r,d)=2\) using the arc sequence \(r,a,d\), and \(d(r,e)=3\) using \(r,a,d,e\). The reverse of an arc is not automatically available: for instance, this graph contains \((r,a)\), not \((a,r)\).
Check: The paths just listed have lengths \(2\) and \(3\). The theorem shows these lengths are minimal, and the table shows that every vertex reached from \(r\) has been assigned a label.
Worked Example: A Longer Route Can Be Discovered Later
Let \(G\) be the undirected graph with \(V=\{s,a,b,c,x,z\}\) and \(E=\{sa,sb,bc,cx,ax,xz\}\). Run BFS from \(s\), examining neighbors in the order \(a,b,c,x,z\).
| Action | New labels | Queue afterward |
|---|---|---|
| Initialize | \(s:0\) | \([s:0]\) |
| Remove \(s:0\) | \(a:1,\ b:1\) | \([a:1,b:1]\) |
| Remove \(a:1\) | \(x:2\) | \([b:1,x:2]\) |
| Remove \(b:1\) | \(c:2\) | \([x:2,c:2]\) |
| Remove \(x:2\) | \(z:3\) | \([c:2,z:3]\) |
| Remove \(c:2\) | None; \(x\) is labeled | \([z:3]\) |
| Remove \(z:3\) | None | \([]\) |
The layers are \(L_0=\{s\}\), \(L_1=\{a,b\}\), \(L_2=\{x,c\}\), and \(L_3=\{z\}\). There are two routes from \(s\) to \(x\): \(s,a,x\) has length \(2\), while \(s,b,c,x\) has length \(3\). BFS labels \(x\) through the shorter route before \(c\) is processed.
Check: The path \(s,a,x,z\) has length \(3\), so \(d(s,z)\leq3\). BFS assigns \(z:3\), and the distance theorem gives \(d(s,z)=3\).
Why the FIFO Rule Matters
A common mistake is to assume that the first route found to a vertex is shortest, regardless of how vertices are processed. That claim is false for a stack-based search. On the graph in the previous example, suppose a stack removes the most recently added vertex and neighbors of \(s\) are added in the order \(a,b\). The stack removes \(b\) first, then can discover \(c\), then \(x\). If the first discovery sets the label, this assigns \(x\) the value \(3\) along \(s,b,c,x\). But the route \(s,a,x\) has length \(2\). This is a concrete wrong distance, caused by processing a deeper route before a shallower one.
BFS avoids this error because its queue removes vertices in nondecreasing label order. When it processes a vertex of label \(k\), it can add vertices of label \(k+1\), but vertices with smaller labels already in the queue are processed first. In the correctness proof, this order is what bounds the label of a neighbor that was already discovered: the earlier-removed vertex that discovered it could not have had a larger label.
For an undirected edge \(uv\) whose endpoints are reachable from \(s\), the distance layers also satisfy \(|d(s,u)-d(s,v)|\leq1\). Indeed, a shortest path to \(u\) followed by \(uv\) is a path to \(v\), so \(d(s,v)\leq d(s,u)+1\); reversing the edge gives \(d(s,u)\leq d(s,v)+1\). In a directed graph, the corresponding statement for an arc \((u,v)\) is \(d(s,v)\leq d(s,u)+1\). These bounds are useful checks on computed layers, but the BFS theorem is stronger: it establishes the exact distance of every reachable vertex.
Check Your Understanding
Use the queue order and the distance theorem to justify each answer.
- In an undirected graph, why does a path of length \(q\) from \(s\) imply that every vertex on the path receives a label no greater than its position along that path?
- What property of FIFO queue removals is needed to handle a neighbor that is already labeled when its current vertex is processed?
- Can an undirected edge join two vertices in the same BFS layer? Explain using an example or a distance argument.
- For a directed arc \((u,v)\), which distance inequality must hold when \(u\) is reachable from \(s\)? Why does the reverse inequality not follow in general?
- Give a graph and a stack-based discovery order for which the first assigned distance is not shortest. What feature of BFS prevents the same mistake?