function bfs(graph: Graph, start: Node) {const queue = [start];
const dist = new Map([[start, 0]]);
while (queue.length > 0) {const node = queue.shift()!;
for (const neighbor of graph.neighbors(node)) {if (dist.has(neighbor)) continue;
dist.set(neighbor, dist.get(node)! + 1);
queue.push(neighbor);
}
}
return dist;
}
Start at A: distance 0, the queue holds only A.
Understanding BFS
The idea
Breadth-first search on a graph is the same idea as on a grid: keep a queue, take the oldest node, and put its unseen neighbours at the back. Nodes come out in order of distance from the source, so the queue holds at most two consecutive levels at any time.
The tree edges, the edge through which each node was first reached, form the BFS tree, and the distance labels are the shortest path lengths in hops. Everything else about the graph, weights included, is ignored.
The four stages
Complexity
Versus its siblings
Pseudocode
BFS(graph, source)
queue ← [source]; dist[source] ← 0
while queue not empty
node ← dequeue
for each neighbour of node with no dist yet
dist[neighbour] ← dist[node] + 1; enqueue neighbour
When to use
Pitfalls
History
Breadth-first search was written down by Konrad Zuse in 1945 and rediscovered by Edward Moore in 1959 for finding the way out of a maze. Its linear running time makes it the first tool reached for on any unweighted graph, and the layering it produces is the backbone of Hopcroft–Karp matching and Dinic's max-flow.