Algorithms in a Nutshell

Breadth-First Search

Breadth-First Search (shown in Figure 6-11) takes a different approach from Depth-First Search when searching a graph. Breadth-First Search systematically visits all vertices in the graph G=(V, E) that are k edges away from the source vertex s before visiting any vertex that is k+1 edges away. This process repeats until no more vertices are reachable from s. Breadth-First Search does not visit vertices in G that are not reachable from s.

Figure 6-11. Breadth-First Search fact sheet

Breadth-First Search makes its progress without requiring any backtracking. It records its progress by coloring vertices white, gray, and black, as Depth-First Search did. Indeed, the same colors and definitions apply. To compare directly with Depth-First Search, we can construct a similar notion of a counter that increments when a vertex is first visited (and colored gray) and when the vertex is last visited (and colored black). Given the graph used earlier in Figure 6-8, in the same amount of time (i.e., when the counter reaches 18), Breadth-First Search is able to progress to the state shown in Figure 6-12, where vertex 12 has just been colored gray. Note that Breadth-First Search is done with vertices {1,6,8}, which are one edge away from s, and vertices {2,3}, which are two edges away from s.

The remaining vertices two edges away from s, vertices {7,14,5}, are all in the queue waiting ...