Graphs

Breadth-first search · source
1function bfs(adj: number[][], start: number) {
2 const dist = new Array(adj.length).fill(Infinity);
3 dist[start] = 0;
4 const queue = [start];
5 while (queue.length > 0) {
6 const u = queue.shift()!;
7 for (const v of adj[u]) {
8 if (dist[v] === Infinity) {
9 dist[v] = dist[u] + 1;
10 queue.push(v);
11 }
12 }
13 }
14 return dist;
15}
Breadth-first search · liveThe frontier expands one ring at a time — a queue makes it fair.
queue · front → back0

Start at node 0 with distance 0. Everyone else is ∞ — undiscovered.

1 / 32

How breadth-first search works

BFS explores in rings: first everything one edge from the start, then everything two edges away, and so on. The queue is what enforces the fairness — nodes are processed in the order they were discovered, so no node at distance 3 is touched before every node at distance 2 is done. Watch the dist labels: they only ever come out in non-decreasing order.

That ring discipline is the proof of BFS's headline guarantee: in an unweighted graph, the first time you reach a node is via a fewest-edges path. The moment a node gets a distance, it is final — no later discovery can beat it. This is why every “minimum number of moves/steps/transformations” problem (word ladder, knight moves, sliding puzzle) is secretly a BFS.

The check that guards everything: only enqueue a node if it has never been seen (dist still ∞). Mark it seen when you enqueue, not when you dequeue — the classic bug is marking late, which lets the same node enter the queue twice. Swap the queue for a stack and this exact code becomes DFS; the data structure is the strategy.

space play / pause · ←→ step

Complexity

timeO(V + E)
spaceO(V)
findsfewest-edge paths
frontierFIFO queue