Reading a BFS Trace
A breadth-first search is easiest to check when its queue and discoveries are written down explicitly. The queue records what is waiting to be processed; the distance label records the layer in which a vertex was first discovered; and a parent pointer records which edge first brought that vertex into the search. A careful trace keeps these three pieces of information distinct.
Throughout, graphs are finite and simple. An undirected edge \(uv\) can be traversed in either direction. In a directed graph, an arc \((u,v)\) can be traversed from \(u\) to \(v\), not from \(v\) to \(u\). A path from a source \(s\) to a vertex \(v\) follows edges in their permitted directions; its length is its number of edges. The distance from \(s\) to \(v\) is the length of a shortest such path. If no such path exists, the distance is \(\infty\), and \(v\) is unreachable from \(s\).
The order in which a vertex’s neighbors are inspected is part of a reproducible trace. It can affect which parent is recorded when there is more than one shortest path. It does not change the set of reachable vertices or their distances. In the examples, neighbor order is stated or follows the displayed order of the edge list. A parent pointer is written \(\operatorname{parent}(v)\); the source has no parent.
Why the Trace Gives Distances and Parents
Proof. Every vertex other than \(s\) is discovered while processing some vertex \(u\), and the algorithm records a traversable edge from \(u\) to \(v\) and sets the label of \(v\) to the label of \(u\) plus one. Thus every discovered vertex has a path from \(s\): follow parent pointers backwards, which decreases the label by one at each step until reaching \(s\). In particular, its label is the length of a path, so its shortest-path distance is no greater than its label.
It remains to show that no reachable vertex is missed or given a label larger than its shortest-path distance. The FIFO rule processes vertices in nondecreasing order of their labels: vertices already waiting at label \(k\) are processed before any vertex newly added with label \(k+1\). This follows because all label-\(k\) vertices are ahead of the label-\(k+1\) vertices in the queue, and processing a label-\(k\) vertex only adds vertices with label \(k+1\). Now take a shortest path \(s=v_0,v_1,\ldots,v_k\). Starting with \(v_0=s\), suppose \(v_i\) is discovered with label \(i\). When \(v_i\) is processed, either \(v_{i+1}\) has already been discovered or the edge to \(v_{i+1}\) discovers it with label \(i+1\). It cannot have been discovered with a smaller label, since that would give a path from \(s\) to \(v_{i+1}\) shorter than its shortest-path distance \(i+1\). Induction along the path shows that \(v_k\) is discovered with its shortest-path distance. Every reachable vertex has such a path, and every discovered vertex is reachable by the parent-path argument. Finally, the rule that first discovers \(v\) from \(u\) gives it a parent joined to \(v\) by the required traversable edge, with label one less. \(\square\)
This result gives a practical check: parent pointers must trace back to the source, and each parent edge must point in the direction of travel. A parent chain is a shortest-path certificate, not just a record of queue history.
Worked Traces
Worked Example: A Directed Graph with Two Shortest Routes
Let the directed graph have \(V=\{s,a,b,c,d,e,f\}\) and arcs \((s,a),(s,b),(a,c),(a,d),(b,c),(b,e),(c,f),(d,f),(e,f)\). Start at \(s\). Inspect each vertex’s out-neighbors in the order they appear in this list.
Initially, the queue is \([s]\), with \(d(s,s)=0\). The table shows the vertex removed, the new discoveries in inspection order, and the queue after that step.
| Removed | New discoveries (distance, parent) | Queue afterwards |
|---|---|---|
| \(s\) | \(a\ (1,s),\ b\ (1,s)\) | \([a,b]\) |
| \(a\) | \(c\ (2,a),\ d\ (2,a)\) | \([b,c,d]\) |
| \(b\) | \(e\ (2,b)\); \(c\) is already discovered | \([c,d,e]\) |
| \(c\) | \(f\ (3,c)\) | \([d,e,f]\) |
| \(d\) | None; \(f\) is already discovered | \([e,f]\) |
| \(e\) | None; \(f\) is already discovered | \([f]\) |
| \(f\) | None | \([]\) |
The layers are \(L_0=\{s\}\), \(L_1=\{a,b\}\), \(L_2=\{c,d,e\}\), and \(L_3=\{f\}\). The reachable set is \(\{s,a,b,c,d,e,f\}\). The recorded parents are \(\operatorname{parent}(a)=s\), \(\operatorname{parent}(b)=s\), \(\operatorname{parent}(c)=a\), \(\operatorname{parent}(d)=a\), \(\operatorname{parent}(e)=b\), and \(\operatorname{parent}(f)=c\).
Check: The parent chain to \(f\) is \(s,a,c,f\), which uses the arcs \((s,a),(a,c),(c,f)\) and has length \(3\). There is no arc directly from \(s\) to \(f\), and every route to \(f\) must pass through one of \(c,d,e\), all at distance \(2\); hence a route to \(f\) needs at least \(3\) arcs. The computed distance is therefore correct.
Now inspect \(s\)’s out-neighbors in the reverse order \(b,a\), leaving the other orders unchanged. The queue begins \([s]\); processing \(s\) gives \([b,a]\). Processing \(b\) discovers \(c,e\), giving \([a,c,e]\). Processing \(a\) finds \(c\) already discovered and discovers \(d\), giving \([c,e,d]\). Processing \(c\) discovers \(f\), giving \([e,d,f]\). The remaining vertices add nothing. The distance layers stay the same, but now \(\operatorname{parent}(c)=b\). Thus parents can depend on neighbor order even when the distances do not.
Worked Example: An Undirected Graph with an Unreachable Vertex
Let the undirected graph have \(V=\{1,2,3,4,5,6,7\}\) and \(E=\{12,13,24,34,45,56\}\). Start at vertex \(1\); inspect neighbors in increasing numerical order.
| Removed | New discoveries (distance, parent) | Queue afterwards |
|---|---|---|
| \(1\) | \(2\ (1,1),\ 3\ (1,1)\) | \([2,3]\) |
| \(2\) | \(4\ (2,2)\) | \([3,4]\) |
| \(3\) | None; \(4\) is already discovered | \([4]\) |
| \(4\) | \(5\ (3,4)\) | \([5]\) |
| \(5\) | \(6\ (4,5)\) | \([6]\) |
| \(6\) | None | \([]\) |
The layers are \(L_0=\{1\}\), \(L_1=\{2,3\}\), \(L_2=\{4\}\), \(L_3=\{5\}\), and \(L_4=\{6\}\). The reachable set is \(\{1,2,3,4,5,6\}\); vertex \(7\) is isolated and never enters the queue. In particular, the edge \(34\) does not make \(4\) a layer-1 vertex: an edge from \(3\) to \(4\) is considered when \(3\) is processed, after \(4\) has already been discovered from \(2\).
Check: The parent chain \(1,2,4,5,6\) uses the four edges \(12,24,45,56\), so it gives a path of length \(4\) to \(6\). Every path from \(1\) to \(6\) must reach \(5\) through \(4\), then use \(56\); reaching \(4\) requires at least two edges, since \(4\) is not adjacent to \(1\). Thus the path length cannot be less than \(4\), confirming \(d(1,6)=4\). No path from \(1\) reaches \(7\), since \(7\) has no incident edge.
Worked Example: Why Arc Direction Matters
Let the directed graph have \(V=\{r,a,b,c,d,e,g\}\) and arcs \((r,a),(r,b),(a,c),(b,c),(c,d),(d,b),(e,r),(g,e)\). Start at \(r\), inspecting out-neighbors in the order listed.
| Removed | New discoveries (distance, parent) | Queue afterwards |
|---|---|---|
| \(r\) | \(a\ (1,r),\ b\ (1,r)\) | \([a,b]\) |
| \(a\) | \(c\ (2,a)\) | \([b,c]\) |
| \(b\) | None; \(c\) is already discovered | \([c]\) |
| \(c\) | \(d\ (3,c)\) | \([d]\) |
| \(d\) | None; \(b\) is already discovered | \([]\) |
The layers are \(\{r\}\), \(\{a,b\}\), \(\{c\}\), and \(\{d\}\). The reachable set is \(\{r,a,b,c,d\}\). Vertices \(e\) and \(g\) are not reachable from \(r\): the arcs \((e,r)\) and \((g,e)\) point toward \(r\), not away from it. The arc \((d,b)\) is usable when processing \(d\), but it leads to \(b\), which has already been discovered.
Check: The recorded path to \(d\) is \(r,a,c,d\), using \((r,a),(a,c),(c,d)\), so its length is \(3\). The only arc entering \(d\) is \((c,d)\), and reaching \(c\) from \(r\) takes at least two arcs: its possible incoming arcs are \((a,c)\) and \((b,c)\), while reaching either \(a\) or \(b\) takes one arc. Hence no path to \(d\) has length less than \(3\).
What to Record and What Can Change
A useful handwritten trace has four columns: the removed vertex, its out-neighbors or neighbors in inspection order, the vertices newly discovered, and the queue afterwards. Keep distance and parent labels beside the queue rather than treating the queue itself as a list of layers. The queue can contain vertices from consecutive layers at the same time, as \([b,c,d]\) did in the first example.
| Trace feature | What to expect |
|---|---|
| Reachable set from a fixed source | Does not depend on neighbor inspection order |
| Shortest-distance labels | Do not depend on neighbor inspection order |
| Parent among tied shortest routes | Can depend on neighbor inspection order |
| Directed-graph reachability | Uses outgoing arcs only |
| Unreachable vertices | Never enter the queue; their distance is \(\infty\) |
Common mistake: treating a directed arc as undirected. In the third example, the arc \((e,r)\) does not allow BFS starting at \(r\) to discover \(e\). A mistaken trace might process \(r\), see that \(e\) is adjacent in the underlying undirected graph, and place \(e\) in layer \(1\). The correction is to inspect only the out-neighbors of \(r\), which are \(a\) and \(b\). The arc \((e,r)\) is considered only if \(e\) is processed, and \(e\) is not reachable from \(r\).
Another useful check is to follow every parent pointer backwards. The chain must end at the source, every parent edge must be traversable in the correct direction, and each step toward the source must decrease the distance by exactly \(1\). This verifies that the recorded parent data forms a shortest path. To verify that the search is complete, check that the queue is empty and that every vertex reached by a path from the source has appeared in the trace.
Check Your Understanding
For each question, specify any neighbor order you use when a trace depends on it.
- In the first worked example, what parent is assigned to \(c\) if \(b\) is processed before \(a\), and why does its distance remain \(2\)?
- For the undirected graph in the second example, list the parent chain from \(1\) to \(5\) and state its length.
- In the third example, which vertices are reachable from \(e\)? Give their distances from \(e\).
- Explain why a vertex can be in the queue while another vertex in the same distance layer has not yet been processed.
- Can changing neighbor order change the reachable set or a shortest-distance label? Give the reason from the BFS trace theorem.