Why Small BFS Choices Matter
Breadth-first search (BFS) is often presented as a short loop, but its correctness depends on how that loop handles discovery, queue order, and distances. A small change can leave reachability correct but create duplicate work, or it can produce a plausible-looking distance that is not shortest. This tutorial diagnoses those failures through explicit traces.
All examples use finite, simple directed graphs: edges have a direction, and there are no loops or multiple edges. A directed path from \(s\) to \(v\) follows edge directions; its length is its number of edges. The distance \(d(s,v)\) is the length of a shortest such path, or is undefined as a finite integer if no such path exists. A vertex is reachable from \(s\) if a directed path from \(s\) to it exists.
Use a special marker \(\bot\) for “not yet discovered.” It is not an integer and is never used in arithmetic. Initialize \(d[v]=\bot\) for every vertex \(v\), then set \(d[s]=0\) and enqueue \(s\). When removing \(u\), inspect each outgoing neighbor \(v\). If \(d[v]=\bot\), set \(d[v]=d[u]+1\) and enqueue \(v\). The key is that the label is set at the same time as the enqueue.
Mark on Enqueue, Not on Removal
A common variant keeps a separate visited set but adds a vertex to it only when the vertex is removed from the queue. Until then, two different predecessors can both treat that vertex as undiscovered and enqueue it. The following trace shows the issue. In the table, the leftmost queue entry is removed first.
Worked Example: The Same Vertex Enqueued Twice
Let the directed graph have \(V=\{s,a,b,x\}\) and \(E=\{(s,a),(s,b),(a,x),(b,x)\}\). Consider the faulty rule “when removing a vertex, mark it visited; enqueue each neighbor not yet visited.” The visited set initially is empty.
| Action | Queue after action | Visited set |
|---|---|---|
| Initialize with \(s\) | \([s]\) | \(\varnothing\) |
| Remove \(s\); mark \(s\); enqueue \(a,b\) | \([a,b]\) | \(\{s\}\) |
| Remove \(a\); mark \(a\); enqueue \(x\) | \([b,x]\) | \(\{s,a\}\) |
| Remove \(b\); mark \(b\); \(x\) is not yet visited, so enqueue \(x\) | \([x,x]\) | \(\{s,a,b\}\) |
| Remove the first \(x\); mark \(x\) | \([x]\) | \(\{s,a,b,x\}\) |
| Remove the second \(x\); it is already visited, so skip it | \([]\) | \(\{s,a,b,x\}\) |
There are two copies of \(x\) in the queue because \(x\) was still absent from the visited set when \(b\) was processed. Skipping the second copy prevents a second scan of \(x\)'s outgoing edges, but the duplicate queue entry was unnecessary. The correction is to mark \(x\) as discovered as soon as it is enqueued. Then \(b\) sees that \(x\) is already discovered and does not add it again.
Check: The paths \(s,a,x\) and \(s,b,x\) both have length \(2\), so \(x\)'s correct distance is \(2\). Marking on enqueue records that value on its first discovery and leaves only one copy of \(x\) in the queue.
Proof. The source is enqueued once at initialization, and its label is immediately set to \(0\). Any other vertex is enqueued only in the step that changes its label from \(\bot\) to an integer. After that step, its label is not \(\bot\). Every later scan of an edge into that vertex therefore fails the test \(d[v]=\bot\), so cannot enqueue it again. These cases cover the source and every other vertex, proving the claim. \(\square\)
Do Not Overwrite a Discovered Distance
With a FIFO queue and marking on enqueue, the first discovery gives the shortest-path distance. A different bug is to assign \(d[v]=d[u]+1\) every time an edge \(uv\) is scanned, even if \(v\) already has a label. A later, longer route can then overwrite a correct earlier label.
Worked Example: A Longer Route Overwrites the Label
Let the directed graph have \(V=\{s,a,b,c,x\}\) and \(E=\{(s,a),(s,b),(a,x),(b,c),(c,x)\}\). Use a FIFO queue, but incorrectly overwrite a neighbor’s label on every scan. Initialize \(d[s]=0\) and all other labels to \(\bot\).
| Action | Queue | Labels changed |
|---|---|---|
| Initialize | \([s]\) | \(d[s]=0\) |
| Remove \(s\); scan \(s\to a,s\to b\) | \([a,b]\) | \(d[a]=1,\ d[b]=1\) |
| Remove \(a\); scan \(a\to x\) | \([b,x]\) | \(d[x]=2\) |
| Remove \(b\); scan \(b\to c\) | \([x,c]\) | \(d[c]=2\) |
| Remove \(x\) | \([c]\) | No change |
| Remove \(c\); scan \(c\to x\) | \([]\) | Faulty overwrite: \(d[x]=d[c]+1=3\) |
The final label \(3\) is wrong: the path \(s,a,x\) has length \(2\), while \(s,b,c,x\) has length \(3\). The correction is to assign a label only when \(d[v]=\bot\). On the final scan, \(x\) already has label \(2\), so it stays \(2\).
Check: The two displayed paths have lengths \(1+1=2\) and \(1+1+1=3\). There is no path of length \(1\), because \(s\) has no edge to \(x\); therefore the shortest distance is \(2\), not \(3\).
A Queue Is Not a Stack
BFS relies on processing vertices in order of their distance from the source. A stack removes the most recently added vertex instead of the least recently added one. Replacing the queue with a stack, while keeping the same mark-on-discovery rule, can let a longer route discover a vertex before a shorter route does.
Worked Example: LIFO Order Finds a Longer Route First
Let \(V=\{s,a,b,c,x\}\) and \(E=\{(s,a),(s,b),(b,c),(c,x),(a,x)\}\). Suppose a stack is used, with its top shown at the right. When processing \(s\), push its neighbors in the listed order \(a,b\), marking each as discovered immediately. The same mark-on-discovery rule is used for later vertices.
| Action | Stack after action | New label |
|---|---|---|
| Initialize with \(s\) | \([s]\) | \(d[s]=0\) |
| Pop \(s\); push \(a\), then \(b\) | \([a,b]\) | \(d[a]=1,\ d[b]=1\) |
| Pop \(b\); push \(c\) | \([a,c]\) | \(d[c]=2\) |
| Pop \(c\); push \(x\) | \([a,x]\) | \(d[x]=3\) |
| Pop \(x\) | \([a]\) | No change |
| Pop \(a\); \(x\) is already discovered | \([]\) | Label remains \(d[x]=3\) |
The stack discovers \(x\) along \(s,b,c,x\), of length \(3\), before it processes \(a\). The shorter path \(s,a,x\) has length \(2\), but the discovered mark prevents its label from being corrected. With a FIFO queue, \(a\) is removed before \(b\), so \(x\) is first discovered from \(a\) with label \(2\).
Check: The path lengths are \(1+1+1=3\) and \(1+1=2\). Thus the stack's label \(3\) is not the shortest distance. BFS requires removal from the front and insertion at the rear.
Use an Unambiguous Unreachable Marker
Distances of reachable vertices are nonnegative integers, including \(0\) for the source. An implementation must distinguish every such value from “unreachable” or “not yet discovered.” A separate Boolean discovery array is one option; a distinct marker such as \(\bot\) is another. Do not use \(0\) as “unvisited” if \(0\) is also a valid distance.
Worked Example: Zero Cannot Mean Both Source and Unvisited
Let \(V=\{s,a,z\}\) and \(E=\{(s,a),(a,s)\}\). The vertex \(z\) is isolated. Suppose all labels are initialized to \(0\), and the algorithm treats \(d[v]=0\) as “unvisited.” It starts with \(d[s]=0\) and queue \([s]\), using the rule “if a neighbor has label \(0\), set its label to the current label plus \(1\) and enqueue it.”
| Action | Queue | Labels \((d[s],d[a],d[z])\) |
|---|---|---|
| Initialize | \([s]\) | \((0,0,0)\) |
| Remove \(s\); \(a\) has label \(0\), so set \(d[a]=1\) | \([a]\) | \((0,1,0)\) |
| Remove \(a\); \(s\) has label \(0\), so set \(d[s]=2\) | \([s]\) | \((2,1,0)\) |
| Remove \(s\); \(a\) has label \(1\), so do not enqueue it | \([]\) | \((2,1,0)\) |
The algorithm has overwritten the source’s true distance \(0\) with \(2\), and the label of \(z\) still cannot distinguish “unreachable” from “not yet discovered.” Use \(\bot\), a distinct value such as \(-1\) when labels are integers, or a separate discovery flag. In this graph, the correct distances from \(s\) are \(d(s,s)=0\) and \(d(s,a)=1\); \(z\) is unreachable.
Check: The directed cycle gives the path \(s,a,s\) of length \(2\), but a path returning to the source does not change the shortest distance from \(s\) to itself: the length-zero path has length \(0\). A correct discovery test never overwrites the source label.
Why the Correct Rules Give Correct Distances
Proof. For each integer \(k\ge 0\), let \(L_k\) be the set of vertices whose true distance from \(s\) is \(k\). We justify the search in increasing distance levels. Initially, \(s\) is the only vertex discovered, it has label \(0\), and it is the only vertex in the queue; thus \(L_0=\{s\}\) is discovered with its correct label.
Suppose the vertices in levels \(L_0,\ldots,L_{k-1}\) have been discovered with correct labels, and their queue processing scans their outgoing edges before any vertex in \(L_k\) is processed. This order follows from FIFO: vertices are enqueued only while scanning a vertex, and an edge from a vertex labelled \(j\) can enqueue only a vertex labelled \(j+1\). Thus entries created while scanning level \(j\) go behind entries already waiting from that level, and ahead of entries created by later levels. In particular, all entries from level \(k-1\) are processed before entries from level \(k\).
For \(k\ge1\), take any \(v\in L_k\). A shortest path to \(v\) has a predecessor \(u\in L_{k-1}\), since removing its last edge leaves a path of length \(k-1\), and a shorter path to \(u\) would give a path to \(v\) shorter than \(k\). When the already correctly labelled \(u\) is processed, the edge \(uv\) is scanned. If \(v\) has not yet been discovered, it receives label \(d[u]+1=(k-1)+1=k\) and is enqueued. If it was discovered earlier, its first discovery was from a vertex at some level \(j\le k-1\), so its assigned label was \(j+1\le k\). A label less than \(k\) would give a path to \(v\) shorter than its true distance \(k\); hence its label is \(k\).
Conversely, a vertex first discovered while scanning a vertex with label \(j\) is assigned \(j+1\), and the path certified by that predecessor has length \(j+1\). Its true distance is therefore at most \(j+1\). The preceding level argument shows that a vertex at true distance \(k\) is discovered while level \(k-1\) is scanned, before level \(k\) is processed; it cannot first receive a label from a later level. Hence every discovered vertex has its true distance. Induction over the finite reachable distance levels proves the claim for all reachable vertices. An unreachable vertex cannot be discovered, since each enqueue follows an edge from an already reachable vertex; so it retains \(\bot\). \(\square\)
This proof explains why the rules work together: FIFO order makes the search advance by distance levels, and marking at first discovery preserves the label assigned from the earliest level that can reach the vertex. A separate visited test at removal, repeated distance assignments, a LIFO stack, or a colliding sentinel breaks one of those guarantees.
Common Pitfalls to Check in Code
- Marking too late: Set the discovery state and distance before enqueueing, not when removing.
- Updating without a condition: Assign a distance only when the vertex is undiscovered; do not overwrite an existing BFS label on every scanned edge.
- Using the wrong container: A stack gives LIFO order. BFS needs FIFO order.
- Reusing a valid label as a sentinel: The source distance is \(0\), so zero cannot also mean “unvisited” unless a separate flag disambiguates the states.
- Doing arithmetic on “unreachable”: Check for the sentinel before computing \(d[u]+1\).
Check Your Understanding
For each question, state the queue or stack rule being used and justify the distance or discovery conclusion.
- In the first worked example, what changes if \(x\) is marked as discovered at the moment it is first enqueued?
- For the graph in the distance-overwrite example, list the true distances from \(s\) to every vertex.
- Why does changing the FIFO queue to a stack invalidate the first-discovery shortest-distance argument?
- Give one valid sentinel choice for integer distance labels and explain why it cannot equal a reachable distance.
- In the correct algorithm, why can an unreachable vertex never be enqueued?