Analysis of Algorithms : An Active Learning Approach

6.3 DEPTH-FIRST AND BREADTH-FIRST TRAVERSAL ALGORITHMS 151

Consider the graph in Fig. 6.4. If we begin the depth-first traversal at node

1, we then visit, in order, the nodes 2, 3, 4, 7, 5, and 6 before we reach a dead

end. We would then back up to node 7 to find that node 8 hasn’t been visited,

but that immediately leads to a dead end. We next back up to node 4 and find

that node 9 hasn’t been visited, but again we have an immediate dead end. We

then continue to back up until we reach the starting node, and because all

nodes adjacent to it have been visited, we are done.

The recursive algorithm for depth-first traversal is

DepthFirstTraversal(G, v)

G is the graph

v is the current node

Visit( v )

Mark( v )

for every edge vw in G do

if w is not marked then

DepthFirstTraversal(G, w)

end if

end for

This recursive algorithm relies on the system stack of the computer to keep

track of where it has been in the graph so that it can properly back up when it

reaches dead ends. We could create a similar nonrecursive algorithm by using a

stack data structure and pushing and popping graph vertices ourselves.

■ 6.3.2 Breadth-First Traversal

In a breadth-first traversal, we visit the starting node and then on the first

pass visit all of the nodes directly connected to it. In the second pass, we visit

nodes that are two edges “away” from the starting node. With each new pass,

we visit nodes that are one more edge away. Because there might be cycles in

1 2

6 5

7 8 9

3

■FIGURE 6.4A graph 4