BREADTH-FIRST SEARCH explore in rings — the shortest path when every step counts the same
Breadth-first search explores a graph in rings: all nodes one step from the source, then two steps, then three — using a queue instead of DFS’s recursion. Because it reaches nodes in order of distance, it finds the shortest path in an unweighted graph for free: the first time BFS touches a node, it has arrived by a fewest-edges route. It is how you find the shortest maze solution, the degrees of separation in a social graph, and the fewest moves in a puzzle. From node 0 the ring distances are 0, 1, 1, 2, 3 — node 4 is three hops away.
THE TECHNIQUE queue, explore by rings — first arrival = shortest unweighted path
The demo computes BFS hop-distances from node 0 — 0,1,1,2,3 — the fewest-edges distance to each node: live demo
HISTORY & CREDIT Moore 1959 · Zuse 1945
“Finding the shortest path needs weights and priorities.” — in an unweighted graph, BFS gives it directly: first arrival is shortest. cited
the rings · a queue explores distance 1, then 2, then 3 — level by level. the shortest path · first time a node is reached, it is by the fewest edges — unweighted shortest path. 1959 · Edward Moore (maze routing); Zuse had it in 1945.
A graph explored outward in even rings — and the first touch of each node is its shortest route. traversal
RECOMMEND FOR I-13 the hop-distances, on the compiler
On the canonical compiler, BFS hop-distances from node 0 are 0,1,1,2,3 — node 3 is 2 hops, node 4 is 3:
$ i13 run nw_breadthfirstsearch.i13 # shortest hop-distances
RUN OK · 4935 step(s) · peak stack 25 · call depth 16
dist[3] = 2 dist[4] = 3
ok = 1 -- 0,1,1,2,3
Recommend as a NULL — a traversal giving shortest unweighted paths. BFS computes the fewest-edges distances — forall-pinned by the graph (B39) — in linear time via a queue (B40). No new invariant. NULL — the ring-by-ring twin of DFS, and free shortest paths when steps are equal.