Breadth-First Search

A traversal of a graph is a systematic way of visiting every vertex reachable from a chosen source, following edges. Breadth-first search is a traversal strategy that explores the graph in layers (also called levels): layer $0$ contains only the source $s$; layer $1$ contains every vertex adjacent to $s$ that has not already been placed in a lower layer; layer $2$ contains every unvisited vertex adjacent to some vertex in layer $1$; and so on. Formally, layer $k$ consists of exactly the vertices whose shortest-path distance (in number of edges) from $s$ equals $k$. The mechanism that produces this layering is a queue with First-In-First-Out (FIFO) discipline. When BFS discovers a vertex, it appends that vertex to the back of the queue; when BFS is ready to explore further, it removes a vertex from the front of the queue. Because vertices are removed in the same order they were added, and because every vertex adjacent to the vertex at the front of layer $k$'s scan gets added while layer $k$ is still being processed, all of layer $k$'s vertices are dequeued — and hence all of layer $k+1$'s vertices are discovered — before any vertex of layer $k+1$ is dequeued. This ordering is the entire reason BFS behaves correctly; if you replaced the queue with a stack (LIFO), you would get depth-first search instead, with a completely different (non-layered) visiting order. To reason about BFS precisely, CLRS-style presentations track a color for each vertex during the search:

• White: undiscovered — the algorithm has not yet encountered this vertex.
• Gray: discovered but not finished — the vertex is in the queue (the "frontier"), and some of its neighbors may still be white.
• Black: finished — the vertex has been dequeued and all of its neighbors have been examined.

The gray vertices at any moment form a "wavefront" separating the black interior (fully explored) from the white exterior (unexplored). Each vertex also receives a distance label $d[v]$, the number of edges on the shortest path from $s$, and a predecessor pointer $\pi[v]$, the vertex from which $v$ was first discovered. The collection of predecessor pointers defines the BFS tree, rooted at $s$, whose tree edges are exactly the edges along which vertices were first discovered.

BFS begins by initializing every vertex to white, with distance $\infty$ and no predecessor, except the source, which is colored gray, given distance $0$, and enqueued. The algorithm then repeatedly dequeues the front vertex $u$, scans all of $u$'s neighbors, and for every neighbor that is still white, discovers it: colors it gray, sets its distance to $d[u]+1$, sets its predecessor to $u$, and enqueues it. Once all neighbors of $u$ have been scanned, $u$ is colored black. The process ends when the queue is empty, at which point every vertex reachable from $s$ has been assigned a correct distance and predecessor. ``` BFS(Graph G, Vertex s): for each vertex v in G.V: color[v] = WHITE dist[v] = INFINITY pred[v] = NIL color[s] = GRAY dist[s] = 0 pred[s] = NIL Q = empty FIFO queue ENQUEUE(Q, s) while Q is not empty: u = DEQUEUE(Q) for each v in Adj[u]: // scan neighbors via adjacency list if color[v] == WHITE: color[v] = GRAY dist[v] = dist[u] + 1 pred[v] = u ENQUEUE(Q, v) color[u] = BLACK // u is fully processed return dist[], pred[] // dist[]=INFINITY means unreachable ``` Two design points deserve emphasis. First, the coloring test `color[v] == WHITE` is what prevents a vertex from being enqueued twice; without it the algorithm could loop forever on a graph with cycles, or at least do redundant work. Second, the check happens at discovery time (when scanning $u$'s neighbor list), not at dequeue time — this is precisely what makes the distance and predecessor values correct, since the first vertex to discover $v$ is guaranteed to be at the smallest possible distance from $s$ (this is proved below). Reconstructing the shortest path from $s$ to any reachable vertex $t$ is a simple walk backward along predecessor pointers: ``` PRINT-PATH(pred[], s, t): if t == s: print s else if pred[t] == NIL: print "no path from s to t exists" else: PRINT-PATH(pred[], s, pred[t]) print t ```

Time complexity. BFS runs in $O(V+E)$ time, where $V$ is the number of vertices and $E$ the number of edges. Justification: the initialization loop touches every vertex once, costing $O(V)$. Every vertex is enqueued at most once — the white-check guarantees this — so the main loop body (a dequeue) executes at most $V$ times. When a vertex $u$ is dequeued, the algorithm scans `Adj[u]`, whose total length summed over all vertices is $\Theta(E)$ for a directed graph and $\Theta(2E)$ for an undirected graph (each edge appears in two adjacency lists). Since each adjacency-list entry is examined exactly once over the whole run, the total work spent scanning neighbors is $O(E)$. Adding the two contributions gives $O(V+E)$, which is linear in the size of the graph's standard representation. If the graph is instead given as an adjacency matrix, scanning neighbors of a single vertex costs $O(V)$ regardless of actual degree, and the total time becomes $O(V^2)$ — a good reminder that BFS's linear-time guarantee depends on using Graph Representations: Adjacency Lists and Matrices with adjacency lists, not matrices.

Space complexity. BFS uses $O(V)$ space: the color, distance, and predecessor arrays are each of size $V$, and the queue holds at most $V$ vertices at any time (it can never contain a vertex twice, by the white-check invariant).

Correctness — the coloring invariant. The proof rests on a loop invariant maintained by the queue's FIFO property. At any point during execution, order the vertices currently in the queue as $v_1, v_2, \ldots, v_k$ from front to back. The invariant is:

In words: distances in the queue are non-decreasing, and the spread between the smallest and largest distance currently queued is at most $1$. This invariant holds initially (only $s$, with $d[s]=0$, is queued). Suppose it holds just before dequeuing $v_1$. When $v_1$ is processed, every newly discovered neighbor $w$ is assigned $d[w] = d[v_1] + 1$ and appended to the back of the queue. Since $d[v_1] \le d[v_k]$ by the invariant, and $d[w] = d[v_1]+1 \le d[v_k] + 1$, appending $w$ preserves the non-decreasing order and the spread-at-most-one property for the new queue $v_2, \ldots, v_k, w, \ldots$. Because the invariant is preserved by every iteration and BFS never enqueues an already-colored (gray or black) vertex, each vertex's distance is set exactly once, at the moment it is first discovered — and it is discovered by a vertex whose own distance is the smallest possible, by the invariant. An induction on $d[v]$ then shows $d[v]$ computed by BFS equals $\delta(s,v)$, the true shortest-path distance (in edges) from $s$ to $v$: the base case $d[s]=0=\delta(s,s)$ holds trivially, and if every vertex at distance $< k$ is correct, any vertex $v$ at true distance $k$ has a neighbor $u$ at true distance $k-1$; $u$ is dequeued before any vertex at distance $\ge k$ (by the queue invariant), so $u$ discovers $v$ (or some other equal-or-earlier vertex does), forcing $d[v] \le k$; and $d[v]$ cannot be smaller than $k$ because a smaller BFS distance would imply a shorter true path, a contradiction. Hence $d[v] = k = \delta(s,v)$ exactly.

Correctness — the BFS tree. Because every non-source vertex $v$ receives $\pi[v] = u$ only when $u$ is the (a) vertex that first discovers $v$, and $d[v] = d[u]+1$, following predecessor pointers from any reachable $t$ back to $s$ traces a path of length exactly $d[t] = \delta(s,t)$ — necessarily a shortest path. The set of all such tree edges $(\pi[v], v)$ forms the BFS tree, a spanning tree of the vertices reachable from $s$; edges of the original graph not used in this tree are either "cross edges" between vertices at the same or adjacent layers, but never edges that would shortcut more than one layer, since a would-be shortcut is contradicted by the distance argument above.

Honest tradeoffs. BFS finds shortest paths measured in edge count, not in weighted cost; on a weighted graph it gives no guarantee whatsoever, and one needs Dijkstra's algorithm or Bellman–Ford instead. BFS also uses $O(V)$ auxiliary space for the queue and bookkeeping arrays, which can matter on graphs with billions of vertices, whereas depth-first search's implicit recursion stack sometimes affords different memory tradeoffs (though DFS does not give shortest paths). Finally, plain BFS explores the entire reachable component even if you only care about one destination; if you know a good heuristic estimate of distance to a specific target, informed search (A\*) can be faster in practice by exploring far fewer vertices.

Consider the small undirected graph in the figure above, with source $s$, and edges $s$–$a$, $s$–$b$, $a$–$c$, $a$–$d$, $b$–$d$, $b$–$e$. Assume adjacency lists list neighbors in alphabetical order. We trace BFS step by step.

The algorithm terminates with distances $d[s]=0$, $d[a]=d[b]=1$, $d[c]=d[d]=d[e]=2$, matching exactly the three layers in the diagram. Notice the edge $b$–$d$: when $b$ is dequeued at step 3, $d$ is already gray (discovered earlier by $a$), so this edge becomes a cross edge in the BFS tree rather than a tree edge — it connects two vertices in the same layer's boundary but does not change any distance, exactly as the invariant predicts (it links vertices whose distances differ by at most one). The BFS tree recorded by $\pi$ is: $s \to a$, $s \to b$, $a \to c$, $a \to d$, $b \to e$, matching the right panel of the figure. To find the shortest path from $s$ to $e$, we walk $\pi[e] = b$, $\pi[b] = s$, giving the path $s \to b \to e$ of length $2$, which indeed equals $d[e]$.

Breadth-first search's layered exploration idea predates modern computing; it appears implicitly in 19th-century work on maze-solving and graph connectivity, but its formalization as an algorithm for computers is tied closely to the development of graph theory and shortest-path computation in the mid-20th century. Edward F. Moore described a breadth-first procedure for finding paths through mazes in 1959, and Konrad Zuse had independently proposed a similar breadth-first solution for maze problems even earlier, though it remained largely unpublished at the time. The technique was subsequently absorbed into the broader toolkit of graph algorithms developed alongside network flow and shortest-path theory in the 1950s and 1960s, and formalized with the white/gray/black coloring scheme and rigorous complexity analysis in the algorithms-textbook tradition that crystallized in the late 20th century.

BFS's fingerprints are all over modern computing infrastructure. Web crawlers use BFS-like frontier expansion to prioritize discovering pages close to seed URLs before wandering deep into distant subgraphs of the web. Peer-to-peer and content-distribution networks use hop-count computations, conceptually BFS, to estimate proximity between nodes. Social networks compute "friends of friends" and shortest connection paths (the basis of "degrees of separation" features) using BFS from a query vertex. Puzzle-solving and game AI use BFS to find minimum-move solutions when all moves have equal cost — the 15-puzzle, Rubik's-Cube-adjacent search spaces, and pathfinding on unweighted grids all lean on it. In compilers and static analysis, BFS-style level-order traversal is used to process dependency graphs layer by layer. Networking protocols that build spanning trees for broadcast (such as certain multicast tree constructions) rely on the same layered-discovery principle. And BFS is the direct computational engine behind two important follow-on ideas: BFS Shortest Paths on Unweighted Graphs, which packages exactly the distance-and-predecessor machinery described here into a shortest-path subroutine, and augmenting-path methods for Bipartite Matching via Augmenting Paths, where repeated BFS-style searches for augmenting paths are the core loop of algorithms like Hopcroft–Karp.

Ask the tutor: How would you modify this BFS pseudocode to compute shortest paths from a set of multiple sources simultaneously, rather than a single vertex?