Why the Queue Order Matters
Breadth-first search (BFS) explores outward from a chosen source, but its behavior depends on more than which vertices have been discovered. The order in which discovered vertices are processed matters: processing them in first-in, first-out order ensures that vertices assigned smaller levels are processed before those assigned larger levels. This tutorial makes that queue discipline precise and proves its invariant. It does not yet identify the assigned labels with shortest-path distances; that requires a separate correctness argument.
All graphs in this tutorial are finite and simple. The examples are directed graphs: an edge \(uv\) means an arc from \(u\) to \(v\), and only outgoing arcs are followed. Fix a source \(s\), and fix an order in which the outgoing neighbors of each vertex will be inspected. The chosen neighbor order can affect the order of discovery among vertices at the same level.
A queue is a list with two designated ends. In a first-in, first-out (FIFO) queue, a vertex is appended at the back and removed from the front. BFS processes the vertex removed from the front, examining its outgoing neighbors in the fixed order. Whenever it finds an undiscovered neighbor, it marks that neighbor discovered, assigns its label, and appends it at the back. Marking at discovery time is essential: a vertex already in the queue must not be enqueued again.
The Queue Procedure
Mark \(s\) discovered, set \(\ell(s)=0\), and make the queue \([s]\). All other vertices are initially undiscovered.
If the queue is nonempty, remove its front vertex \(u\). This is the next vertex to process.
For each outgoing neighbor \(v\) of \(u\), in the fixed order, do nothing if \(v\) is already discovered. Otherwise mark \(v\) discovered, assign \(\ell(v)=\ell(u)+1\), and append \(v\) at the back.
Repeat from Step 2 until the queue is empty.
The queue records discovered vertices that have not yet been processed. The source is the first entry. Each later entry is placed behind every vertex already waiting, so it cannot pass an earlier entry. The next result makes the consequence precise.
Proof. We prove the queue statement by induction over queue operations, including the inspection of individual neighbors. Initially the queue is \([s]\), whose only label is \(0\), so its labels are nondecreasing. Suppose the queue has nondecreasing labels and its front vertex \(u\) has label \(k\). Every vertex currently in the queue has label at least \(k\). We also need the upper bound that no queued label exceeds \(k+1\): this holds initially, and the following operation preserves it. After \(u\) is removed, the remaining labels are still in nondecreasing order. During the inspection of \(u\)'s outgoing neighbors, any newly discovered vertex is appended with label \(k+1\). Thus each appended label is at least every label already in the queue: the remaining labels were at least \(k\), and, by the induction bound, at most \(k+1\). Appending one or more labels equal to \(k+1\) therefore preserves nondecreasing order and the upper bound. If no vertex is appended, removal alone preserves the order. If removal leaves the queue empty, the first newly appended vertices, if any, all have the same label \(k+1\). This proves the queue statement and the two-consecutive-label bound at every stage. In particular, any newly assigned label \(k+1\) is at least every label assigned earlier: before \(u\) is processed the largest label that can have been assigned is at most \(k+1\). Finally, every removal takes the front entry of a nondecreasing queue; subsequent entries have label at least as large, and new entries are appended with label one greater than the label just removed. Hence dequeue labels are nondecreasing as well. \(\square\)
The theorem concerns labels produced by the procedure. It does not by itself prove that \(\ell(v)\) is the shortest-path distance from \(s\) to \(v\). That distinction is useful: first establish what the queue operations guarantee, then establish what those labels mean in the graph.
Worked Queue Traces
Worked Example: Branching and a Repeated Encounter
Let the directed graph have vertex set \(V=\{1,2,3,4,5,6,7\}\) and edge set \(E=\{12,13,24,25,35,36,47,57,67\}\). Use source \(1\), inspecting each vertex's outgoing neighbors in increasing numerical order. Run BFS and record the queue after each vertex is processed.
| Vertex removed | Neighbor inspection and action | Queue afterward |
|---|---|---|
| — | Initialize with \(1\), label \(0\). | \([1]\) |
| \(1\) | Discover \(2\), label \(1\); discover \(3\), label \(1\). | \([2,3]\) |
| \(2\) | Discover \(4\), label \(2\); discover \(5\), label \(2\). | \([3,4,5]\) |
| \(3\) | \(5\) is already discovered; discover \(6\), label \(2\). | \([4,5,6]\) |
| \(4\) | Discover \(7\), label \(3\). | \([5,6,7]\) |
| \(5\) | \(7\) is already discovered. | \([6,7]\) |
| \(6\) | \(7\) is already discovered. | \([7]\) |
| \(7\) | No outgoing neighbors. | \([]\) |
The labels assigned, in order, are \(0\) for \(1\), then \(1,1\) for \(2,3\), then \(2,2,2\) for \(4,5,6\), then \(3\) for \(7\). The queue labels, for example after processing \(3\), are \(2,2,2\); after processing \(4\), they are \(2,2,3\). Each is nondecreasing. The edge \(35\) does not cause another entry for \(5\): that vertex was marked discovered when it was first appended while processing \(2\).
Check: Every vertex is enqueued once: the queue receives \(1,2,3,4,5,6,7\), seven vertices in total, and removes those same seven in the displayed order. The final queue is empty. The edge set has nine arcs; the trace examines the outgoing arcs from \(1,2,3,4,5,6\), and vertex \(7\) has none. In particular, all arcs leading to a previously discovered vertex, \(35,57,67\), are accounted for without another enqueue.
Worked Example: Neighbor Order Can Change the Queue
Let \(V=\{s,a,b,c\}\) and \(E=\{sb,sa,bc,ba,ac\}\), with source \(s\). First inspect \(s\)'s outgoing neighbors in the order \(b,a\), then inspect all other outgoing neighbors in alphabetical order.
Initialize the queue as \([s]\) with \(\ell(s)=0\). Remove \(s\): discover \(b\), set \(\ell(b)=1\), and append it; then discover \(a\), set \(\ell(a)=1\), and append it. The queue is now \([b,a]\). Remove \(b\): its neighbors are \(a,c\); \(a\) is already discovered, while \(c\) is not, so set \(\ell(c)=2\) and append it. The queue becomes \([a,c]\). Remove \(a\): its neighbor \(c\) is already discovered, leaving \([c]\). Remove \(c\), which has no outgoing neighbors, leaving \([]\).
The assignment order is \(0,1,1,2\), and the queue changes from \([s]\) to \([b,a]\), \([a,c]\), \([c]\), and finally \([]\). The queue order between \(a\) and \(b\) reflects the chosen neighbor order, not a difference in their labels.
Check: The displayed sequence examines all five arcs: \(sb,sa\) while processing \(s\), \(ba,bc\) while processing \(b\), and \(ac\) while processing \(a\). Each vertex is enqueued once, so four vertices are enqueued and four are removed. The queue labels at the nonempty stages are respectively \(0\); \(1,1\); \(1,2\); and \(2\), all in nondecreasing order.
Worked Example: A Directed Cycle Returns to a Discovered Vertex
Let \(V=\{r,x,y\}\) and \(E=\{rx,xy,yx,xr\}\), with source \(r\). Use the listed outgoing-neighbor order: \(r\) has neighbor \(x\), \(x\) has neighbors \(y,r\), and \(y\) has neighbor \(x\).
Initialize with queue \([r]\) and label \(\ell(r)=0\). Remove \(r\), discover \(x\), assign \(\ell(x)=1\), and append \(x\); the queue is \([x]\). Remove \(x\): inspect \(y\) first, discover it with label \(2\), and append it. Then inspect \(r\), which is already discovered, so do not append it. The queue is \([y]\). Remove \(y\): its neighbor \(x\) is already discovered, so the queue becomes empty.
Check: The three vertices are enqueued in the order \(r,x,y\) and removed in the same order; their labels are \(0,1,2\). All four arcs are handled: \(rx\) discovers \(x\), \(xy\) discovers \(y\), \(xr\) reaches an already discovered vertex, and \(yx\) reaches an already discovered vertex. Thus the directed cycle creates no duplicate queue entries.
Why Each Queue Operation Is Necessary
FIFO is the feature that maintains the proved order. If an implementation removes the newest entry instead of the oldest, it behaves like a stack rather than a queue. Likewise, inserting a newly discovered vertex at the front lets it jump ahead of vertices that have been waiting longer. Either change removes the guarantee proved above.
A second essential rule is to mark a vertex discovered before appending it. In the first example, both \(2\) and \(3\) have arcs to \(5\). If \(5\) were left unmarked until it was removed from the queue, processing \(3\) could append a second copy of \(5\), despite the first copy still waiting. Mark-on-discovery makes the decision “already discovered” apply to vertices that are queued as well as vertices that have already been processed.
Common mistake: append at the front. In the graph with \(V=\{s,a,b,c\}\) and \(E=\{sb,sa,bc,ba,ac\}\), suppose the neighbors of \(s\) are inspected in the order \(b,a\), but new vertices are incorrectly inserted at the front. After processing \(s\), \(b\) is inserted and the list is \([b]\); then \(a\) is inserted at the front, giving \([a,b]\). Processing \(a\) discovers \(c\) with label \(2\) and inserts it at the front, producing \([c,b]\). This queue-like list has labels \(2,1\) from front to back, which decrease. The correction is to append \(c\) at the back, giving \([b,c]\) before \(b\) has been processed, or, under genuine FIFO operations, to process the earlier entries in their prescribed order. New entries must wait behind existing entries.
In a finite graph, the procedure terminates: each vertex is marked discovered at most once, hence is appended at most once and removed at most once. Each removal inspects the finite list of outgoing neighbors of that vertex. Once no queued vertices remain, no further processing step is possible. These facts justify the mechanics of the algorithm; the queue invariant explains the order in which that finite work is performed.
The key practical test is local: before processing a vertex, read the queue from front to back and compare its labels. They must be nondecreasing. When processing a vertex of label \(k\), newly discovered neighbors receive \(k+1\) and join the back. Encountering an already discovered vertex adds nothing. This accounts for branching, cycles, and multiple arcs arriving at the same vertex without changing the FIFO principle.
Check Your Understanding
Use the stated enqueue and dequeue rules, and distinguish assigned BFS labels from shortest-path distances.
- For \(V=\{s,p,q,r\}\) and \(E=\{sp,sq,pr,qr\}\), run BFS from \(s\), inspecting \(p\) before \(q\). Give the queue after each removal and the label assigned to each discovered vertex.
- State the queue invariant and explain why appending a vertex of label \(k+1\) cannot place it ahead of an already queued vertex of label \(k\).
- In a directed graph, what should BFS do when it inspects an outgoing arc to a vertex that has been discovered but not yet removed from the queue?
- Explain why the labels being nondecreasing in dequeue order does not, by itself, prove that they are shortest-path distances.
- Give a reason each vertex is enqueued at most once, and use it to explain why the procedure terminates on a finite graph.