A graph search must answer two different questions: which vertices can be reached, and how many edges are needed to reach them? Breadth-first search (BFS) answers both for an unweighted graph. Its queue gives priority to earlier distance layers, and a parent pointer records one path witnessing the answer.
The timing of a small operation matters. If a vertex is marked only when removed from the queue, several neighbors may enqueue it first. Marking it when it is enqueued makes each vertex enter the queue once and fixes its first parent. We will prove why that first discovery is already a shortest path, rather than merely trusting a trace.
Define distances and the data structures
Definition 13.1.1
(Shortest-path distance)
Let be a finite directed graph with vertices , , and choose a source . Each listed arc counts as one step. The distance is the minimum number of arcs in a directed path from to , if one exists. Set otherwise. The source has distance zero via its length-zero path.
An undirected edge can be represented by one adjacency entry in each direction. Self-loops and repeated adjacency entries are permitted; they do not create a shorter path. The analysis below counts as the number of listed directed adjacency entries, including repetitions.
Definition 13.1.2
(The queue and the labels)
Maintain a FIFO queue, a distance array and a parent array. None in the distance array means not discovered yet. Initially the source has distance 0 and is in the queue; every other distance and every parent is None.
When removing a vertex , inspect each listed outgoing neighbor . If distance[v] is None, set it to distance[u] + 1, set parent[v] = u, and immediately enqueue . If is already discovered, leave its label and parent unchanged. The distance array serves as the discovery mark.
Once the algorithm finishes, None in the distance array means unreachable. During the algorithm, however, None only means not yet discovered; a later queue entry might still reach that vertex.
Common mistake
(Reading None as unreachable too early)
After removing 1 in the six-vertex example, distance[4] is still None, although 4 is reachable from 0. During the search, None means only that no removed vertex has discovered it yet; it means unreachable only after the queue is empty.
Trace a graph with two possible routes
Worked example 13.1.3
(A queue exposes one layer at a time)
Use the following adjacency lists in the displayed order, with source 0:
| Vertex | Outgoing neighbors |
|---|---|
| 0 | 1, 2 |
| 1 | 3 |
| 2 | 3, 4 |
| 3 | 4 |
| 4 | none |
| 5 | none |
The queue starts as [0]. Removing 0 discovers 1 and 2, giving [1, 2]. Removing 1 discovers 3, giving [2, 3]. Removing 2 sees that 3 is already discovered, then discovers 4, giving [3, 4]. The remaining removals add nothing.
The final distances are [0, 1, 1, 2, 2, None]. One possible parent array is [None, 0, 0, 1, 2, None]: following parents from 4 gives 4, 2, 0, so reversing gives the shortest path The route is also a directed path, but uses three edges. Vertex 5 is unreachable from 0.
If the adjacency list of 0 were [2, 1], vertex 3 could instead receive parent 2. BFS may choose a different shortest-path witness, but its distances do not depend on which shortest witness is chosen.
Worked example 13.1.4
(Self-loops and repeated entries change nothing but m)
Use the adjacency lists 0: [1, 1, 0], 1: [2, 0], 2: [1] with source 0. Removing 0 discovers 1 with distance 1 and parent 0; the repeated entry 1 and the self-loop 0 find labeled vertices and change nothing. Removing 1 discovers 2 with distance 2 and parent 1, and the entry 0 is skipped. Removing 2 inspects 1, already labeled. The result is distances [0, 1, 2] and parents [None, 0, 1]. Six adjacency entries were inspected, so , but each vertex was enqueued once.
Why the first discovery is shortest
Theorem 13.1.5
(BFS computes shortest distances)
Let be a finite directed graph and a vertex. When the queue is empty, distance[v] equals for every vertex reachable from , distance[v] is None exactly for the unreachable vertices, and following parents back from a reachable traces a path from whose length is that distance.
Proof
(FIFO order preserves nondecreasing layers)
The source is queued with label 0. Whenever a vertex with label is removed, every newly enqueued neighbor receives label . Queue labels are nondecreasing: initially there is one zero; removing the front cannot disrupt order, and every new label is at least every label still in the queue. More precisely, while processing a layer , the queue contains only remaining labels followed by labels . This property is preserved when a label- vertex appends label .
Every discovered vertex has a real source-to-vertex path of the recorded length: the source has the empty path, and each discovery appends one arc to its parent's witnessed path. Consequently a recorded label can never be smaller than the true shortest distance.
For the opposite inequality, let be reachable at shortest distance and choose a shortest path . Induct on . The source is labeled 0. If has label at most , it is eventually removed: there are only finitely many vertices and each is enqueued once. At that removal, either is already labeled, or the arc gives it label at most .
If it was already labeled earlier, FIFO layer order says its discoverer had label no greater than the label of at removal. Thus its label is also at most . Hence is labeled at most ; together with the witnessed-path inequality, its label equals .
After the queue empties, every reachable vertex has been discovered by this argument. An unreachable vertex cannot have been discovered, because every discovery has a real path from the source. Therefore the remaining None entries are exactly the unreachable vertices.
Proof X-ray
Where first-in, first-out is used
Only one step needs the queue discipline: the case where was labeled before was removed. Its discoverer was then removed earlier, and FIFO order makes the labels at removal nondecreasing, so the discoverer's label is at most that of and receives at most . The rest of the proof, namely witnessed paths and finite termination, does not depend on the order. A stack in place of the queue fails exactly at this step, as the example below shows.
A shorter equivalent proof uses induction on the order of removal: if a newly discovered vertex had a strictly shorter path, the preceding vertex on that path would belong to an earlier layer and would have been removed first, discovering it earlier. Both versions rely on FIFO order, not just on visiting every vertex eventually.
Counterexample mode
A stack with discovery marking gives wrong distances
Take arcs , , , , with adjacency lists in this order and source 0, and replace the queue by a stack, still marking vertices when they are pushed. Removing 0 pushes 1 and 2 with label 1; the top of the stack, 2, is removed first and pushes 3 with label 2; removing 3 pushes 4 with label 3. Vertex 1 is removed last and finds 4 already labeled. The algorithm reports distance 3 for vertex 4, although the path has length 2. Every vertex is still discovered once, so marking at discovery does not by itself give shortest paths; the first-in, first-out order does.
An implementation with explicit boundaries
The input is an indexable sequence of adjacency sequences of integer vertices. This version validates all neighbor indices, even in a component unreachable from the source, and does not mutate the input. A deque supports FIFO removal without shifting an entire array.
from collections import deque
def breadth_first_search(graph, source):
n = len(graph)
if not 0 <= source < n:
raise ValueError("source outside the vertex range")
for neighbors in graph:
for vertex in neighbors:
if not 0 <= vertex < n:
raise ValueError("neighbor outside the vertex range")
distance = [None] * n
parent = [None] * n
distance[source] = 0
queue = deque([source])
while queue:
u = queue.popleft()
for v in graph[u]:
if distance[v] is None:
distance[v] = distance[u] + 1
parent[v] = u
queue.append(v)
return distance, parent
def shortest_path(distance, parent, source, target):
if not 0 <= source < len(distance) or not 0 <= target < len(distance):
raise ValueError("endpoint outside the vertex range")
if distance[target] is None:
return None
path = []
v = target
while v != source:
path.append(v)
v = parent[v]
path.append(source)
path.reverse()
return path
shortest_path expects the arrays returned by breadth_first_search for this same source. The source itself returns [source]: its zero-edge path needs no parent. An unreachable target returns None. For a discovered non-source vertex, each parent has a distance exactly one less, so backtracking reaches the source after finitely many steps. Reversing the collected vertices gives a forward path of exactly the recorded length.
Concept lensStructural
The output as a layered tree
Let be the distance layers. Every arc out of a reachable satisfies , so it stays inside a layer, drops to an earlier one, or advances by exactly one layer. The parent arcs are the advancing ones that were used for discovery: each reachable non-source vertex has exactly one, so they form a tree rooted at with arcs. In the six-vertex example the layers are and the tree arcs are , , , ; the arc stays inside layer 2.
Worked example 13.1.6
(Reconstructing paths, including the source itself)
Use the arrays of the six-vertex example: distances [0, 1, 1, 2, 2, None] and parents [None, 0, 0, 1, 2, None]. For target 3 the loop collects 3 and then 1, appends the source 0, and the reversal gives [0, 1, 3], two edges, equal to distance[3]. For target 0 the loop body never runs and the result is [0]. For target 5 the distance is None, so the function returns None. On a graph with one vertex and no arcs, graph = [[]], the search returns distances [0] and parents [None].
The input contract promises integer vertices and well-formed adjacency sequences; the bounds checks do not validate every possible malformed Python object. A production interface may need stricter type and error handling according to its own contract.
Counting the work and avoiding weighted-graph mistakes
Proposition 13.1.7
(Running time of breadth-first search)
With the implementation above, a search takes time and additional cells, where counts the listed directed adjacency entries, repetitions included. Reconstructing a path with edges takes time.
Proof
(Counting vertices and adjacency entries)
Initialization and the validation scan take time. Each vertex is enqueued and removed at most once, and each outgoing adjacency entry of a reached vertex is inspected once, adding at most time. The distance array, parent array and queue use additional cells, excluding the input graph. Reconstructing a path with edges takes time and output cells.
Counterexample mode
Fewest edges need not mean least weight
Suppose a weighted directed graph has of weight 10 and edges , each of weight 1. BFS regards every edge as one step and chooses the direct one-edge route, whose weight is 10. The two-edge route has total weight 2. The BFS proof above optimizes edge count, not arbitrary total weight; even allowing a zero-weight edge does not make ordinary BFS a general weighted shortest-path algorithm.
BFS is one choice of search order, not a substitute for defining the objective. When edge weights matter, use an algorithm whose assumptions match them and prove the associated invariant. For the unweighted problem, the queue order and first-discovery parent together supply both the optimal distance and a checkable witness.
Exercises with solutions
Quick check
(1. In the six-vertex example, give the queue immediately after removing 1, and a shortest path to 4.)
Solution · Solution 1
After removing 1, the queue is [2, 3]. Vertex 2 then discovers 4, so parents give the shortest path of length 2. The vertex 4 remains undiscovered until 2 is removed; None before that moment does not imply it is unreachable.
Quick check
(2. What are the returned distance and path for the source itself? What is returned for vertex 5 in the example?)
Solution · Solution 2
The source has distance 0 and path [0], a length-zero path. Vertex 5 has distance None and no path from the source, so shortest_path returns None for it after the search.
Quick check
(3. Suppose , , and Why does marking 3 only when removed risk extra queue entries?)
Solution · Solution 3
Both 1 and 2 can inspect 3 before 3 reaches the front. If discovery is not recorded at enqueue time, each may enqueue it. Marking 3 when 1 first enqueues it makes the later inspection from 2 skip it; only one queue entry and one first parent are stored. Different adjacency order may select a different, equally short parent.
Quick check
(4. Why is the search rather than , and what does m count here?)
Solution · Solution 4
The arrays are initialized once, and every vertex is enqueued at most once. Scanning each removed vertex's list examines each listed outgoing entry at most once; the upfront validation also scans the lists once. Thus total work is , where counts directed adjacency entries, including repeats. An undirected edge stored in both directions contributes two entries.