Follow a queue to prove fewest-edge distances and compare it with depth-first exploration.
By the end: explain why breadth-first search minimizes edge count and why search order is not a unique graph property.
The frontier records unfinished work
Breadth-first search, or BFS, starts with the source at distance zero. It marks the source discovered and places it in a first-in, first-out queue. Remove the front vertex, inspect its neighbors, and enqueue each undiscovered neighbor with a distance one greater. Mark it when enqueued, not later, to prevent duplicate discoveries.
The queue holds discovered vertices whose outgoing edges have not yet been inspected. The discovery edge for each new vertex records a parent. These parent edges form a search tree over the reachable vertices. Vertices outside that reachable set have no finite distance and are absent from the tree.
Discovery is a promise to inspect a vertex once
Imagine a station map on which every connection counts as one transfer, regardless of its drawn length. Searching that map requires two separate records. One says which stations you have already found. The other says which found stations still need their connections inspected. Without the first record, a triangle can send the search around indefinitely. Without the second, finding a station does not ensure that you will inspect its onward connections. Breadth-first search keeps both records and chooses the oldest unfinished station next. The queue is therefore an ordered record of unfinished work, not the route a passenger follows.
Use the six vertices A, B, C, D, E, and F with undirected edges AB, AC, BC, BD, CE, DE, and EF. There are no other edges, and every edge contributes one to route length. Starting at A, the initial queue contains only A. Inspect A's neighbors alphabetically. B enters first and C enters second, each with distance one and parent A. After removing A, the queue is B followed by C. Both vertices are discovered, although neither has yet had its own neighbors inspected. That distinction explains what a highlighted vertex can mean before processing finishes.
Discovered does not mean processed
After processing A, B and C are discovered and queued. The thick edges AB and AC record their parents. Every other original edge remains available; geometry is schematic, not a transfer-time scale.
Now remove B from the front. Its neighbors are A, C, and D. A and C already have discovery marks, so neither enters again. D is new, so record its distance as two, its parent as B, and append it behind C. The queue becomes C followed by D. Processing C then inspects A, B, and E. Only E is new, so it enters behind D with distance two. Notice that the edge BC exists even though it discovers neither endpoint. A search tree records discoveries; it does not claim that all other edges have disappeared from the graph.
Marking at discovery matters precisely when several inspected vertices share a neighbor. In this graph D and E are adjacent. After C discovers E, processing D finds E already marked and leaves its existing parent unchanged. If the search waited to mark E until removing it from the queue, D could add E a second time while the first copy was still waiting. Such duplicate entries obscure the meaning of one event per vertex. Marking immediately prevents that problem without assuming that each vertex has only one possible route from A. Several routes may exist while only one discovery record is needed.
Continue the trace. Processing D adds nothing, leaving E in the queue. Processing E finds F for the first time, gives it distance three, and appends it. Processing F adds nothing and empties the queue. The processed order is A, B, C, D, E, F. The queues after those events are B C, C D, D E, E, F, and empty. Reconstruct the selected route to F by following parents backward from F to E, C, and A, then reversing that sequence. The result is A, C, E, F, not the entire processed order.
One inspection can discover several vertices or none
Processed
New discoveries
Queue after event
Initial
A at distance 0
A
A
B and C at distance 1
B, C
B
D at distance 2
C, D
C
E at distance 2
D, E
D
None
E
E
F at distance 3
F
F
None
Empty
These are the complete queue states from A for the seven-edge undirected graph. A parent route follows discovery edges backward; the processed column is not itself a route instruction.
The parent relation cannot contain a cycle. Each parent was discovered before its child, so following parents repeatedly moves toward earlier discoveries and eventually reaches the source. Each discovered vertex other than A contributes exactly one parent edge. Here six discovered vertices produce five tree edges, although the original graph has seven edges. This explains why the display can show a tree without claiming the station network itself is a tree. The tree supplies one route to each reachable vertex. The original edge set still determines every alternative route, including routes that the tree leaves out.
Why layers give shortest routes
BFS processes all distance-zero work before distance-one work, then all distance-one work before distance-two work. If a vertex first appears at distance three, a route of two edges would have exposed it while processing distance-one vertices. That would contradict its first discovery at three. This is the invariant behind the shortest-edge-count guarantee.
Depth-first search, or DFS, instead pursues an undiscovered neighbor recursively and returns when that branch has no new neighbor. It finds reachability and a search tree, but its first route to a target need not use the fewest edges. Both methods depend on tie-breaking for their particular trees. Here neighbors are visited alphabetically.
The queue order rules out a shorter unseen route
A useful statement about an algorithm is one that stays true after every step. Such a statement is called an invariant. For BFS, queue entries appear in nondecreasing distance order. Smaller distance labels never wait behind larger ones. Initially this holds because the queue contains only distance zero. Suppose the front has distance two. Its newly discovered neighbors receive distance three and go at the back. Any remaining distance-two entries keep their place ahead of them. This mechanism prevents the search from processing a distance-three vertex while a distance-two vertex still waits for inspection.
More specifically, a nonempty BFS queue contains vertices from at most two consecutive distance layers. While processing the distance-one layer, the queue may mix remaining distance-one vertices with newly found distance-two vertices. It cannot yet contain a distance-three vertex, because finding one requires processing a distance-two parent, which is still behind all the distance-one work. In the base graph, C and D briefly share the queue even though C has distance one and D has distance two. They need not have identical labels. The required property is that the older, smaller layer stays ahead.
Two layers can share the queue
State after
Queue, front first
Distance labels in queue
A
B, C
1, 1
B
C, D
1, 2
C
D, E
2, 2
D
E
2
E
F
3
The queue fronts progress through distance layers, not through sorted vertex names. After B, the distance-one entry C must leave before the distance-two entry D. New entries always join at the back.
Why does first discovery give the minimum edge count? Suppose a vertex receives label three, but a two-edge route to it exists. On that hypothetical route, the station immediately before the destination is at most one edge from A. BFS must process that predecessor before any distance-two vertex. Inspecting its edge to the destination would discover the destination with label at most two. That contradicts the supposed first discovery at three. The same reasoning works for any claimed shorter route. It connects the ordering of unfinished work to a statement about all routes, including ones never selected as parents.
In the base graph, put A in layer zero, B and C in layer one, D and E in layer two, and F in layer three. Every listed undirected edge joins either the same layer or consecutive layers. For example, BC stays within layer one, while EF joins layers two and three. An edge from A directly to F would violate these labels, since it would supply a one-edge route. Checking all edges this way tests whether a proposed set of layer numbers is consistent with the graph. It does not depend on the drawing's horizontal or vertical distances.
There is a second way to certify these particular distances without replaying BFS. The parent routes establish that every finite label is achievable. Separately, every edge changes the displayed layer number by at most one. Starting from label zero, a walk of two edges therefore cannot end at label three. F needs at least three steps, and its parent route supplies exactly three. Both parts matter. Labels that are all zero satisfy the edge-difference restriction but fail to provide zero-edge routes to other vertices. Parent routes alone provide achievable lengths but do not rule out shorter alternatives.
Achievable routes and an edge-by-edge lower bound
The labels give distances from A. Solid thick edges supply parent routes of those lengths. Every original edge changes the label by at most one, so a two-edge walk cannot reach F at label three. Positions are schematic; the printed labels carry the quantities.
Alphabetical neighbor order chooses a reproducible parent when equal-length alternatives compete, but alternatives are not always ties. From A, the route A, B, D, E, F has four edges, compared with three on A, C, E, F. From F, however, B has two shortest routes, F, E, C, B and F, E, D, B. Both have three edges. Alphabetical processing gives C the first chance to discover B, selecting C as its parent. Count the edges rather than judging visual similarity. A deterministic parent choice does not establish that the selected route is uniquely shortest.
Inspect the graph and its result
Process the breadth-first queue
Fixed graph
Breadth-first discoveries
Event 0 of 6. Source queued. Queue: A.
Distances A–F: 0, ∞, ∞, ∞, ∞, ∞. ∞ means not yet discovered.
Step 0 / 6
Complete BFS trace and DFS comparison
Processed
Queue after event
Distances A–F
Initial
A
0, ∞, ∞, ∞, ∞, ∞
A
B, C
0, 1, 1, ∞, ∞, ∞
B
C, D
0, 1, 1, 2, ∞, ∞
C
D, E
0, 1, 1, 2, 2, ∞
D
E
0, 1, 1, 2, 2, ∞
E
F
0, 1, 1, 2, 2, 3
F
None
0, 1, 1, 2, 2, 3
This full trace does not require playback.
DFS preorder: A, B, C, E, D, F. Its discovery edges are A–B, B–C, C–E, D–E, E–F. DFS is not a fewest-edge-route guarantee.
Changing the source resets playback. Reset retains the source. Alphabetical neighbors determine ties. Blue edges are discovery-tree edges; marked vertices have been discovered. Each event processes one queued vertex, not one second of real computation.
Source A in the base graph
Fewest edges
A
0
B and C
1
D and E
2
F
3
Alphabetical discovery chooses A-B, A-C, B-D, C-E, E-F. Thick blue edges are the named selection; all original connections remain visible.
Read the player as a sequence of graph states
Use the existing player to separate the state before any inspection from the state after one inspection. With source A, event zero already marks A and places it in the queue. It does not yet mark B or C. One step processes A and can discover both of them at once. An event therefore does not mean one discovered vertex or one traversed edge. It means one complete inspection of a queued vertex's neighbors. Several discoveries may happen in that inspection, or none may happen. The total sequence has an initial state followed by six processed-vertex events.
Before advancing from the state with queue C followed by D, predict which entry must leave and where a new entry can go. C leaves first. E joins at the back, so the next queue is D followed by E. E cannot move ahead of D merely because its letter is earlier in a different arrangement of the drawing. Alphabetical order applies when inspecting a vertex's neighbors. The queue then preserves arrival order across processing events. These two rules cooperate, but they are not interchangeable. Sorting the entire queue alphabetically after every discovery would be a different procedure.
Changing the source changes the tree
Vertex
Parent from A
Distance from A
Parent from F
Distance from F
A
None, source
0
C
3
B
A
1
C
3
C
A
1
E
2
D
B
2
E
2
E
C
2
F
1
F
E
3
None, source
0
Both searches use exactly AB, AC, BC, BD, CE, DE, EF. From F, C reaches B before D is processed, selecting BC rather than BD as B's parent edge. Reset repeats the selected source rather than changing it.
Selecting source F keeps every graph edge unchanged but changes the question being asked. F first discovers E. E then discovers C and D, in that order, each at distance two. C next discovers A and B at distance three. D sees B already marked and does not replace its parent. The resulting processed order is F, E, C, D, A, B. Distances in A-through-F order are three, three, two, two, one, zero. A connected graph still reaches all six vertices, but neither the tree nor the distance labels must match the A-rooted result.
Compare the A-rooted and F-rooted trees rather than treating one as the network's permanent tree. From A, B discovers D. From F, E discovers D. The same undirected edge can exist without belonging to either chosen tree, while another edge can belong to both. Reset restarts the current source's playback; it does not select A for you. Choosing a source is a change to the starting condition, whereas Reset repeats the selected condition. The static trace gives the same queue and distance states without requiring you to catch a change while it is moving.
The DFS comparison follows a different rule on the same edges. From A, alphabetical recursive exploration visits A, then B, then C, then E, then D, and finally F. At E it explores D before F. After D has no undiscovered neighbor, the procedure returns to E and continues with F. Its parent route to D is A, B, C, E, D, of length four. The original edge BD supplies the shorter route A, B, D. DFS has not made an invalid route. It has answered reachability with a route that need not minimize the number of edges.
DFS must return to E before discovering F
Solid edges are the alphabetical DFS discovery tree from A. Its route to D has four edges, although the dashed original edge BD supplies a two-edge route from A. Preorder D followed by F does not mean an edge DF exists.
A DFS return is a change in the search's unfinished work, not necessarily an instruction to a traveler. The preorder lists vertices when first visited, so its consecutive entries do not always form a walk. In the A-rooted preorder above, D is followed by F, but DF is not an edge. The procedure returned to E between those first visits. Parent edges retain that missing structure. Read a preorder as an order of first discoveries, a parent chain as a route, and a BFS queue as pending inspections. Confusing these records can produce a sequence that the graph never permits.
What the guarantee excludes
BFS minimizes edge count, not varying travel times, costs, or risk. Two expensive edges may cost more than three cheap ones. For equal positive edge weights, minimizing count also minimizes total weight. With unequal weights, use a method whose assumptions address them.
A standard adjacency-list implementation of BFS or DFS takes work proportional to vertices plus edges. That bound describes an implementation strategy, not this small visualizer's measured speed. Its one-second teaching events are processed vertices, not seconds of graph computation. The complete trace remains below the player.
Count search work without inventing travel or timing evidence
BFS answers a minimum-transfer question only when one edge is the unit being minimized. On the base graph, imagine assigning every edge the same positive travel time of five minutes. A route with three edges then costs fifteen minutes, so minimizing edge count also minimizes that additive time. If each connection instead has its own time, the implication fails. The queue does not inspect those times and cannot distinguish a slow direct connection from a fast indirect one. An edge-count optimum remains mathematically correct even when it is the wrong answer to a travel-time question.
A second limitation concerns what reaching a vertex establishes. A complete search from A in this undirected graph proves that every listed vertex is connected to A by permitted edges. It does not prove that one vehicle can execute all the selected routes together, that the connections operate at compatible times, or that the system survives an outage. The previous connectivity lesson supplies the relevant edge-loss question. Search can be a component of that analysis, but a successful search on the unchanged graph says nothing about which edges remain after a failure. The input conditions must change before that question changes.
Equal edge times preserve the edge-count objective
Route from A to F
Edges
Time with 5 minutes per edge
A, C, E, F
3
15 minutes
A, B, D, E, F
4
20 minutes
A, B, C, E, F
4
20 minutes
On the unchanged base graph, assume each edge takes five minutes and route times add with no waiting. Then time is five times edge count. This assumption is a paper comparison, not travel data supplied by the player.
The familiar vertices-plus-edges work bound comes from counting inspections, not watching the player. In a standard adjacency-list implementation, each reachable vertex enters and leaves the queue once. Inspecting its stored neighbor list touches each outgoing incidence once. For this connected undirected example there are six vertex removals and fourteen neighbor incidences, because every one of seven edges appears at both endpoints. Those are different kinds of work, so adding them does not produce a measured number of processor instructions. It does explain why doubling isolated graph data need not require checking every possible pair of vertices.
Representation changes that accounting. A full adjacency matrix has a row for each vertex and a column for each possible neighbor. To inspect one vertex's neighbors, a basic matrix search checks all six entries in its row, including zeros. Across all six vertices that means thirty-six entry checks. An adjacency list instead contains the fourteen actual incidences. The routes and discovery rule can agree while the inspected storage differs. This is why an algorithm's reasoning and an implementation's data access should be described separately. The small lesson model is not a benchmark comparing matrix and list performance.
Stopping early also changes what the evidence supports. If the only question is the edge-count distance to F, BFS may stop when F is first discovered and still know that distance. The layer argument already rules out a shorter route. It would not then have a complete processed-vertex trace for the entire reachable set. Conversely, an infinity symbol during playback means only that a vertex has not yet been discovered. Only a finished search with an empty queue supports interpreting its remaining infinity labels as unreachable. In this connected base graph, all six final distances are finite.
Seven edges appear as fourteen neighbor incidences
Vertex
Neighbor list inspected
List entries / matrix entries
A
B, C
2 / 6
B
A, C, D
3 / 6
C
A, B, E
3 / 6
D
B, E
2 / 6
E
C, D, F
3 / 6
F
E
1 / 6
Total
Seven edges, two ends each
14 / 36
Each undirected edge appears at both endpoints. A standard list-based search inspects fourteen stored incidences here; a basic full-matrix scan checks thirty-six entries. These are storage inspections, not measured execution times or player durations.
When moving this method to an everyday map, audit the relation before trusting the route. A line might mean a direct service, a walkable connection, or a transfer allowed only under some ticket. Those are different graphs even when the station names match. Repositioning the same labeled vertices changes none of the computed edge counts. Changing a permission can change them. The queue and layer proof establish a result conditional on the supplied edges and equal-step objective. Observations of actual service, waiting time, and accessibility determine whether that conditional result answers the practical question you intended to ask.
Exercises
Correct a search claim
An algorithm explores A-B-C-D before noticing a direct A-D edge. It returns length three as the shortest route. What failed?
Hint
A depth-first branch may be long even when a short branch exists.
Worked answer
Candidate
Edge count
A-B-C-D
3
A-D
1
A single valid shorter route refutes the optimality claim. Thick blue edges are the named selection; all original connections remain visible.
Finding one route proves reachability, not optimality. The direct edge gives a route of length one, so the returned route is not shortest. BFS would discover D while inspecting A. DFS can still find a shortest route in some cases, but has no general first-route guarantee.
Two equally short routes
A connects to B and C; both B and C connect to D. If BFS changes the neighbor order, what may change and what must stay the same?
Hint
Separate the parent choice from the distance.
Worked answer
Neighbor order at A
One possible route to D
Distance
B then C
A-B-D
2
C then B
A-C-D
2
Tie-breaking chooses an answer among equal optima.
D may receive B or C as its parent, changing the selected shortest-path tree and reconstructed route. Its distance from A remains two. Neither ordering makes one route uniquely shortest.
Sources and further reading
Selected reference passages support the definitions and algorithms below. The networks, explanations, and implementations are original. Terminology and assumptions are stated within each lesson; source review is not an independent audit of this course. Optional links are not runtime dependencies.
Graph representations, degree, trees, BFS and DFS. This course explicitly reserves path for a walk without repeated vertices; the reference uses a different path convention.
Directed reachability, strong components, DAGs, and topological orders. The lesson uses zero-indegree removal rather than the reference implementation's reverse-postorder method.