Breadth-first search
Overview
Breadth-first search (BFS) visits every vertex one edge away from the start before moving on to vertices two edges away. Like checking all subway stations reachable in one hop before looking at two-hop trips, expanding layer by layer guarantees that the first time a vertex is reached in an unweighted graph, the path uses the minimum possible number of edges.
History
Edward F. Moore formulated layer-by-layer shortest-path search in his 1959 paper “The Shortest Path Through a Maze,” labeling cells at distance from the origin.1 In 1961, C. Y. Lee built on Moore’s method in “An Algorithm for Path Connections and Its Applications,” describing equidistant grid cells expanding like a wavefront to route printed-circuit-board connections.2 Independently, Konrad Zuse had written an equivalent component-labeling procedure in his 1945 *Plankalkül* manuscript, though it remained unpublished for decades.
FIFO queues and the two-layer invariant
A first-in, first-out (FIFO) queue removes vertices in the exact order they were added. Discovering and from the source appends both at distance ; discovering from places behind at distance . At any point during execution, the queue holds vertices from at most two consecutive distance layers, satisfying the monotonicity invariant:
A vertex must be marked as visited the moment it is enqueued, not when it is dequeued. In the diagram below, both and have edges to . Delaying the mark until dequeue would let enqueue a second time while is still waiting behind , inflating both queue size and running time. Marking on enqueue ensures every reachable vertex enters the queue at most once, even in graphs with self-loops or cycles.
Executable example
Represent vertices A through E by indices 0..4 in an adjacency list. Because both B and C point to D, this small graph tests duplicate suppression alongside distance layers. All vertex indices and start must lie in 0..graph.length-1.
function breadthFirst(graph: readonly (readonly number[])[], start: number) {
const distance = new Array<number>(graph.length).fill(-1);
const order: number[] = [];
const queue = [start];
distance[start] = 0;
for (let head = 0; head < queue.length; head++) {
const from = queue[head]!;
order.push(from);
for (const to of graph[from]!) {
if (distance[to] !== -1) continue;
// Mark on enqueue—not on dequeue—so shared neighbors are never queued twice.
distance[to] = distance[from]! + 1;
queue.push(to);
}
}
return { order, distance };
}
const names = ['A', 'B', 'C', 'D', 'E'];
const graph = [[1, 2], [3], [3, 4], [], []];
const result = breadthFirst(graph, 0);
console.log(result.order.map(index => names[index]).join(','));
console.log(result.distance.join(','));Output:
A,B,C,D,E
0,1,1,2,2Vertices B and C are one edge from A; D and E are two edges away. Any unreachable vertex retains distance -1. Advancing a head index instead of calling Array.prototype.shift() keeps each dequeue rather than shifting remaining array elements in time.
C++ example
In C++, while std::queue<int> (backed by std::deque<int>) is standard, pairing a contiguous std::vector<int> with a advancing head index avoids chunked deque allocations when the vertex count is bounded.
#include <cstddef>
#include <iostream>
#include <utility>
#include <vector>
struct BfsResult {
std::vector<int> order;
std::vector<int> distance;
};
BfsResult breadthFirst(const std::vector<std::vector<int>>& graph, int start) {
std::vector<int> distance(graph.size(), -1);
std::vector<int> order;
std::vector<int> queue{start};
distance[start] = 0;
for (std::size_t head = 0; head < queue.size(); ++head) {
int from = queue[head];
order.push_back(from);
for (int to : graph[from]) {
if (distance[to] != -1) continue;
// Mark on enqueue so shared neighbors are never queued twice.
distance[to] = distance[from] + 1;
queue.push_back(to);
}
}
return {std::move(order), std::move(distance)};
}
int main() {
const char names[] = {'A', 'B', 'C', 'D', 'E'};
const std::vector<std::vector<int>> graph{{1, 2}, {3}, {3, 4}, {}, {}};
const auto result = breadthFirst(graph, 0);
for (std::size_t i = 0; i < result.order.size(); ++i) {
if (i > 0) std::cout << ',';
std::cout << names[result.order[i]];
}
std::cout << '\n';
for (std::size_t i = 0; i < result.distance.size(); ++i) {
if (i > 0) std::cout << ',';
std::cout << result.distance[i];
}
std::cout << '\n';
return 0;
}Output:
A,B,C,D,E
0,1,1,2,2Cost and scope
With vertices and directed adjacency entries, array setup and traversal take time and auxiliary space beyond the input graph.
BFS computes shortest paths only when all edges share the same unit cost. If edge weights are restricted to , 0-1 BFS with a double-ended queue preserves time; for general nonnegative edge weights, use Dijkstra’s algorithm to order candidates by accumulated cost instead of hop count. When you need to follow a path to completion before backtracking or classify cycle edges, use Depth-first search.
See also
Footnotes
- Edward F. Moore, “The Shortest Path Through a Maze,” Proceedings of an International Symposium on the Theory of Switching (1957), Part II, Harvard University Press, 1959, pp.285–292. ↩
- C. Y. Lee, “An Algorithm for Path Connections and Its Applications,” IRE Transactions on Electronic Computers EC-10(3), 1961, pp.346–365. Introduction and §VI. Paper, DOI. ↩