Breadth-first search
Start at one node and explore in rings: first everything one hop away, then everything two hops away, and so on. A queue keeps the order, so the first time a node is reached is always by the fewest possible hops.
queue: front on the left, distance in each box
Find the fewest hops from A to every other node.
1function bfs(adj, start) {2 const dist = new Array(adj.length).fill(-1);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] === -1) {9 dist[v] = dist[u] + 1;10 queue.push(v);11 }12 }13 }14 return dist;15}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | V + E | every reachable node and edge is looked at once |
| average | V + E | any graph |
| worst | V + E | the same for every graph |
| space | V | a distance per node, plus the queue |
Where it breaks
- Edges with different lengths. BFS counts hops, not distance. If one road is 1 km and another 50 km, the fewest hops is not the shortest route. Use Dijkstra's algorithm for weighted edges.
- Marking nodes too late. Set a node's distance when it joins the queue, not when it leaves. Otherwise the same node can be queued many times over.
- Unconnected parts. Pick Two islands: D, E and F are never reached from A, so they keep no distance. To cover every part, start a new search from each node still unvisited.