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 ...

Start Free Trial

No credit card required