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 In the 1945 version of his Plankalkül manuscript, Konrad Zuse described P3.69, a procedure that groups connected elements and assigns group numbers. Its front-of-list processing and end-appending follow the queue discipline used in BFS. The manuscript was published in 1972.3
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: In the formula, contains only the pending vertices from onward, and denotes the distance of a discovered vertex. The code marks undiscovered vertices with .
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
C++20
The C++20 version uses the same adjacency list and keeps -1 for unreachable distances. The start and every neighbor must be valid indices into graph. Advancing head moves the read position without erasing the front of the vector.
#include <cstddef>
#include <iostream>
#include <vector>
using Graph = std::vector<std::vector<std::size_t>>;
struct SearchResult {
std::vector<std::size_t> order;
std::vector<std::ptrdiff_t> distance;
};
SearchResult breadthFirst(const Graph& graph, std::size_t start) {
SearchResult result{{}, std::vector<std::ptrdiff_t>(graph.size(), -1)};
std::vector<std::size_t> queue{start};
result.distance[start] = 0;
for (std::size_t head = 0; head < queue.size(); ++head) {
const auto from = queue[head];
result.order.push_back(from);
for (const auto to : graph[from]) {
if (result.distance[to] != -1) continue;
// Mark on enqueue to prevent another edge from queuing the same vertex.
result.distance[to] = result.distance[from] + 1;
queue.push_back(to);
}
}
return result;
}
int main() {
const std::vector<char> names{'A', 'B', 'C', 'D', 'E'};
const Graph 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;
}A,B,C,D,E
0,1,1,2,2TypeScript
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(','));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.
Cost 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. ↩
- Konrad Zuse, Der Plankalkül, 1945 version, Rojas et al. transcription: ch.1 II.6, p.30 (W6); ch.2 IV.1, p.78 (Lz), IV.2, pp.81–82 (P3.69). Archive, transcription. 1972 edition: GMD report 63, catalog. ↩