Breadth-First Search (BFS) Algorithm

Key Insight

Breadth-First Search (BFS) is a fundamental graph-searching algorithm that systematically explores the edges of a graph from a designated source vertex `s`. Its primary purpose is to 'discover' every vertex reachable from `s`, computing the shortest-path distance (minimum number of edges) from `s` to each reachable vertex. BFS operates by uniformly expanding the frontier of discovered vertices, ensuring all vertices at distance `k` from `s` are processed before any at distance `k+1`. It constructs a 'breadth-first tree' rooted at `s`, where paths from `s` to any reachable vertex `v` are shortest paths in terms of edges.

The algorithm manages its progress using vertex colors: `WHITE` for undiscovered vertices, `GRAY` for discovered but not fully explored vertices (those whose adjacency lists are being scanned), and `BLACK` for fully explored vertices. Initially, all vertices are `WHITE`, except for the source `s`, which is `GRAY` and enqueued. A first-in, first-out (FIFO) queue `Q` stores `GRAY` vertices. When a `WHITE` vertex `v` is encountered during the scan of a `GRAY` vertex `u`'s adjacency list, `v` is colored `GRAY`, its distance `v:d` is set to `u:d + 1`, `u` is recorded as `v`'s predecessor `v:π`, and `v` is enqueued. Once all `u`'s neighbors are processed, `u` is colored `BLACK` and dequeued.

BFS, when implemented with an adjacency-list representation, runs in `O(V+E)` time. This efficiency stems from each vertex being enqueued and dequeued at most once, and each adjacency list being scanned at most once. The algorithm's correctness guarantees that upon termination, `v:d` equals `δ(s,v)`, the true shortest-path distance from `s` to `v`. The predecessor subgraph `G_π` formed by the `v:π` attributes constitutes a breadth-first tree, containing all vertices reachable from `s`, and all paths from `s` to any `v` in this tree are unique simple shortest paths in the original graph `G`.