Why Breadth-First Search Cannot Discover Vertices Out of Distance Order

Breadth-first search computes, for every vertex reachable from a source, the smallest number of edges on a path from that source. The algorithm is short enough to write from memory, and most of its correctness lives in one invariant about the queue: at any moment the queue holds vertices of at most two consecutive distance values, in nondecreasing order, with all vertices of the smaller value ahead of all vertices of the larger one. Everything else — the distance labels, the parent pointers, the linear running time — follows from that invariant. The interesting failures happen when an implementation violates one of its preconditions, usually by marking a vertex visited at the wrong moment.

The queue state the proof depends on

Let d(v) be the number of edges on the shortest path from the source s to v, with d(s) = 0. BFS labels each vertex with a tentative distance when it is first discovered and never revises it. Correctness rests on two claims proved together by induction over the algorithm’s steps: every vertex is assigned its true d(v) on discovery, and the queue is ordered by d.

The ordering claim is stronger than it first appears. Suppose the queue contains vertices with distances k and k+1 only, in that order. Dequeuing a vertex at distance k appends its undiscovered neighbours, each at distance k+1, to the tail. Those new entries sit behind any existing k+1 entries, so the order holds. When the last k vertex is dequeued, the queue contains only k+1 vertices, and the next layer begins. The queue never holds vertices at distance k and k+2 simultaneously, because a k+2 vertex can only be discovered from a k+1 vertex, and no k+1 vertex is dequeued until the k layer is exhausted.

This is why the algorithm can stop thinking about a vertex once it is dequeued. There is no relaxation step, no re-checking of distances, no priority queue. The FIFO discipline is the correctness argument.

The induction also fixes the running time. Each vertex is enqueued exactly once, so each adjacency list is scanned exactly once, and the cost is O(n + m) for a graph stored as adjacency lists or compressed sparse rows. On an adjacency matrix the same code scans full rows and becomes O(n²), which is a property of the encoding rather than of the search.

The visited mark belongs on enqueue

The most common defect in hand-written BFS is marking a vertex when it is dequeued rather than when it is enqueued. It produces correct distances on many graphs, which is why it often passes inspection, and it fails on graphs with cycles by doing asymptotically more work.

from collections import deque

def bfs(adj, s):
    dist = [-1] * len(adj)
    parent = [-1] * len(adj)
    dist[s] = 0
    q = deque([s])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:          # test-and-mark happen together
                dist[v] = dist[u] + 1
                parent[v] = u
                q.append(v)
    return dist, parent

The test and the mark are one step: the sentinel -1 in dist doubles as the unvisited flag, and assigning the distance is what removes the vertex from the unvisited set. Splitting them — pushing v, then marking it when it comes off the queue — lets a vertex be pushed once per incident edge. In a complete graph the queue then holds Θ(n²) entries instead of n, and memory grows accordingly even though the resulting distances are still right.

There is a subtler variant in which a vertex is marked visited when it is dequeued but its distance and parent are written when it is pushed. With the correct enqueue-time marking, the first discovery is also the earliest possible discovery, so the parent recorded is a valid predecessor on a shortest path. With dequeue-time marking, a vertex can be pushed several times before it is first dequeued, and a later push from a vertex at a greater distance overwrites the parent recorded earlier, so the reconstructed path can be longer than the true shortest path.

Multi-source starts and early termination

BFS generalizes to several sources by seeding the queue with all of them at distance 0. The layer invariant is unchanged; layer k now means “k edges from the nearest source”. This is the standard way to compute distance to a set — nearest facility, distance from a coastline in a grid, multi-source flood fill — and it costs one pass, not one pass per source.

Early termination needs care. If the goal is a single target vertex, the search may return as soon as the target is dequeued, because the layer invariant guarantees that no later dequeued vertex has a smaller distance. Returning when the target is discovered is also valid, since discovery assigns the final distance, but the parent chain is only complete if the parent was itself finalized, which it was: parents are dequeued vertices, and their distances never change. Returning early from inside the neighbour loop is where implementations go wrong, because the target’s own neighbours have not been expanded and any caller expecting a complete distance map gets a partial one.

Bidirectional BFS, which expands from both endpoints and stops when the frontiers meet, relies on the same invariant from both directions. The meeting test is not “the two visited sets intersect” but “the sum of the two distances at the intersection is minimal”, and the stopping condition must account for the current layer boundaries rather than for the first shared vertex found. Getting this wrong yields paths that are one or two edges longer than optimal, and the error is invisible on trees.

When the layer argument stops holding

The invariant assumes every edge costs the same. Add weights and the queue order no longer tracks path cost: a vertex reached by three cheap edges may be dequeued after one reached by a single expensive edge, and the algorithm returns a path that is short in edge count but not in weight. Weighted graphs need the priority-queue relaxation described under shortest-path methods, where the frontier is ordered by tentative cost rather than by discovery order.

The invariant also assumes the graph is static during the search. If edges are inserted while BFS runs, a vertex already labelled can acquire a shorter path through a later-inserted edge, and the no-revision property fails. Concurrent mutation needs either a snapshot of the edge set or an algorithm designed for dynamic graphs.

Memory is the third limit. BFS on a graph of n vertices holds a frontier that can be Θ(n) wide, and the visited set is Θ(n) regardless. On graphs too large for memory, the frontier must be spilled and re-read, which changes the cost model entirely; the direction-optimizing variants described in frontier-based traversal across memory hierarchies exist for exactly that regime.

Ordering within a layer is also unspecified, and that matters more than it looks. Two correct implementations can dequeue the same layer in different orders, because the order depends on the order neighbours were appended and therefore on the adjacency layout. Any output that groups vertices by distance is stable; any output that lists them within a layer is not. Test suites that compare full traversal sequences across implementations are comparing a property the algorithm never promised, and the discrepancy is usually resolved by sorting each layer before comparison rather than by fixing either implementation.

Direction, transposes, and what distance means

On a directed graph the traversal follows edges only forward, so the labels it writes are distances along directed paths from the source. A vertex that reaches the source without being reachable from it stays unlabelled, and the count of labelled vertices is the size of the source’s out-component — not the size of the weakly connected component that contains it. Answering “how far is this vertex from the source” when the paths may run against the arrows requires the transpose graph and a second search, which doubles both passes and edge storage unless the transpose is built once and kept.

The distinction shows up in error when a caller interprets an unreachable label as a large distance. The sentinel must be distinct from every legitimate distance, and using a large positive number instead of -1 makes “unreachable” compare as farther than any real vertex, so a minimum-over-neighbours computation silently prefers a genuine path and a maximum prefers the sentinel. Either convention works if applied consistently; mixing them produces answers that look plausible on connected inputs.

One degenerate input catches both mistakes at once: a self-loop at the source. The loop’s target is already marked at distance 0, so it is skipped, and the loop contributes nothing to the distance map. That is correct for unweighted distance but wrong for any algorithm that counts paths, where the self-loop multiplies the count. The same distinction — distance versus enumeration — separates BFS from the exhaustive walks that DFS with explicit stacks makes convenient.