598
Graph Algorithms
Example 11 makes the depth-first search process sound very complex, but it is
much easier to carry out than to write down, as you will see in Practice 14.
Breadth-First search
In breadth-first search, beginning at an arbitrary node a, we first fan out from node
a to visit nodes that are adjacent to a; then we fan out from those nodes, and so on,
almost like the concentric circles of ripples in a pond. Figure 7.15 shows the first few
nodes visited in the same graph as Figure 7.13, this time using breadth-first search.
Figure 7.15
praCtiCe 14 Write the nodes in a depth-first search of the graph in Figure 7.14. Begin with node a.
Figure 7.14
■
Graph Algorithms
Example 11 makes the depth-first search process sound very complex, but it is
much easier to carry out than to write down, as you will see in Practice 14.
Breadth-First search
In breadth-first search, beginning at an arbitrary node a, we first fan out from node
a to visit nodes that are adjacent to a; then we fan out from those nodes, and so on,
almost like the concentric circles of ripples in a pond. Figure 7.15 shows the first few
nodes visited in the same graph as Figure 7.13, this time using breadth-first search.
Figure 7.15
praCtiCe 14 Write the nodes in a depth-first search of the graph in Figure 7.14. Begin with node a.
Figure 7.14
■