O'Reilly logo

Algorithms in a Nutshell by Gary Pollice, Stanley Selkow, George T. Heineman

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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.

Breadth-First Search fact sheet

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required