Unweighted Graphs: Breadth-First Search

Learn about the breadth-first search algorithm and its applications in solving the shortest paths problem in unweighted graphs.

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 ss. At each iteration, the algorithm pulls a vertex uu from the front of the queue and examines each of its outgoing edges uvu\rightarrow v. Whenever the algorithm discovers an outgoing tense edge uvu\rightarrow v, it relaxes that edge and pushes vertex vv onto the queue. The algorithm ends when the queue becomes empty.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy