Unweighted Graphs: Breadth-First Search

Implementation of breadth-first search

In the simplest special case of the shortest path problem, all edges have weight 1, and the length of a path is just the number of edges. This special case can be solved by a species of our generic graph-traversal algorithm called breadth-first search. Breadth-first search is often attributed to Edward Moore, who described it in 1957 (as “Algorithm A”) as the first published method to find the shortest path through a maze. Especially in the context of VLSI wiring and robot path planning, breadth-first search is sometimes attributed to Chin Yang Lee, who described several applications of Moore’s “Algorithm A” (with proper credit to Moore) in 1961. However, in 1945, more than a decade before Moore considered mazes, Konrad Zuse described an implementation of breadth-first search as a method to count and label the components of a disconnected graph.

Breadth-first search maintains a first-in-first-out queue of vertices, which initially contains only the source vertex s. At each iteration, the algorithm pulls a vertex $u$ from the front of the queue and examines each of its outgoing edges $u\rightarrow v$. Whenever the algorithm discovers an outgoing tense edge $u\rightarrow v$, it relaxes that edge and pushes vertex $v$ onto the queue. The algorithm ends when the queue becomes empty.