A First Taste of Algorithms · Maps, Mazes, and Networks

Ripples: breadth-first search

Drop a stone in a pond and watch the rings: everything one hop away gets wet first, then everything two hops away, then three. Breadth-first search (BFS) is that ripple, run on a graph: starting somewhere, visit all vertices 1 edge away, then all at 2 edges, then 3 — never touching a far vertex before every nearer one is done.

The discipline that enforces ripple-order is a waiting line. Keep a queue of vertices to process; always serve the front of the line; when you serve a vertex, its not-yet-seen neighbors join the back. First in, first out — exactly a bakery line — and fairness of the line is what makes the rings expand evenly: everything at distance d entered the line before anything at distance d + 1, so it gets served first, so its discoveries (distance d + 1) enter before theirs (d + 2). The ripple is bureaucracy, perfectly administered. One more piece of bookkeeping makes it terminate: a visited set, so no vertex joins the line twice. (Chapter 1’s lesson about structure: the visited set is what makes “have I seen this?” cheap.)

Figure 5.2 — The school as a graph, and the ripple from the gym: ring numbers are hop distances.

What you get for this discipline is the chapter’s central theorem: BFS finds shortest paths — when BFS first reaches a vertex, it has reached it by a fewest-possible-edges route, and the ring number is the distance in hops. The proof is an induction on the rings, and it is the Diamond: ring d is correct because ring d − 1 was, true at the floor (the start is its own ring zero), preserved ring to ring. Fourth appearance of the only trick.

And note what BFS says when the ripple dies out with some vertex never wetted: that vertex is unreachable — not “probably not connected,” but provably, because the ripple visited everything touchable. Chapter 1’s expensive certainty of absence, again purchased by exhaustiveness, again organized by structure.

A human moment

Nobody invented breadth-first search; at least three people did, separately. Konrad Zuse — who built programmable computers in his parents’ Berlin living room during the war — described it in his 1945 thesis, which sat unpublished until 1972. E. F. Moore at Bell Labs reinvented it in 1959 as “the shortest path through a maze,” wanting to route telephone calls through switching networks. C. Y. Lee reinvented it again in 1961 to route wires across circuit boards — chip designers call grid-BFS the “Lee algorithm” to this day, and some version of it has helped lay out nearly every chip in every device you own. Triple invention is not embarrassment; it is evidence. When the world builds networks — telephone, electronic, social — the ripple gets discovered by whoever is standing closest to the need. Ideas have infrastructure the way plants have seasons.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses