Section 7.4 Traversal Algorithms
597
algoRitHm DEPthFirst
DepthFirst(simple, connected graph G; node a)
//Writes nodes in graph G in depth-first order from node a
mark a visited
write (a)
for each node n adjacent to a do
if n not visited then
DepthFirst(G, n)
end if
end for
end DepthFirst
In the recursive step, the algorithm is invoked with a new node specified as the
starting point. We have not indicated here how to mark visited nodes or how to
find those nodes n that are adjacent to a.
example 11
We will apply depth-first search to the graph of Figure 7.13, where a is the initial
node. We first mark that we have visited a (it’s helpful in tracing the execution of
the algorithm to circle a visited node), and then we write out a. Next we search the
nodes adjacent to a for an unvisited node. We have a choice here (b, e, h, and i); let us
select node b. (Just so we all get the same answers, let’s agree to choose the node
that is alphabetically first when we have a choice; in practice, the choice would
be determined by how the vertices were stored in the graph representation.) Then
we invoke the depth-first search algorithm beginning with node b.
We go back to the beginning of the algorithm, where the specified node is
now b rather than a. Thus we first mark b visited and write it out. Then we search
through nodes adjacent to b to find an unmarked node. Nodes a and c are adjacent
to b, but node a is marked as already visited. Node c will do, and we invoke the
depth-first search algorithm beginning with node c.
Node c is marked and written out, and we look for unmarked nodes adjacent to
c. By our alphabetical convention, we select node d from the set 5d, f 6. Continuing
in this fashion, after visiting node d we next visit node f and then node g. When we
get to node g, we have reached a dead end because there are no unvisited adjacent
nodes. Thus the for loop of the instance of the algorithm invoked with node g is
complete. (The graph at this point looks like Figure 7.13.)
We are therefore done with the algorithm for node g, but node g was (possibly
one of) the unmarked nodes adjacent to node f, and we are still in the for loop for the
instance of the algorithm invoked with node f. As it happens, g is the only unvisited
node when we are processing f; therefore we complete the for loop and thus the algorithm for node f. Similarly, backing up to node d, the algorithm finds no other adjacent
unmarked nodes, and it backs up again to the instance of the algorithm invoked with
node c. Thus, after processing node d and everything that came after it until the dead
end, we are still in the for loop for the algorithm applied to node c. We look for other
unmarked nodes adjacent to c and find one—node e. Therefore we apply depth-first
search to node e, which leads to nodes h, i, and k before another dead end is reached.
Backing up, we have a final new path to try from node h, which leads to node j. The
complete list of the nodes, in the order in which they would be written out, is
a, b, c, d, f, g, e, h, i, k, j
ReminDeR
In a depth-first search, go
as far as possible, then
back up, catching any
paths missed on the way
down.
597
algoRitHm DEPthFirst
DepthFirst(simple, connected graph G; node a)
//Writes nodes in graph G in depth-first order from node a
mark a visited
write (a)
for each node n adjacent to a do
if n not visited then
DepthFirst(G, n)
end if
end for
end DepthFirst
In the recursive step, the algorithm is invoked with a new node specified as the
starting point. We have not indicated here how to mark visited nodes or how to
find those nodes n that are adjacent to a.
example 11
We will apply depth-first search to the graph of Figure 7.13, where a is the initial
node. We first mark that we have visited a (it’s helpful in tracing the execution of
the algorithm to circle a visited node), and then we write out a. Next we search the
nodes adjacent to a for an unvisited node. We have a choice here (b, e, h, and i); let us
select node b. (Just so we all get the same answers, let’s agree to choose the node
that is alphabetically first when we have a choice; in practice, the choice would
be determined by how the vertices were stored in the graph representation.) Then
we invoke the depth-first search algorithm beginning with node b.
We go back to the beginning of the algorithm, where the specified node is
now b rather than a. Thus we first mark b visited and write it out. Then we search
through nodes adjacent to b to find an unmarked node. Nodes a and c are adjacent
to b, but node a is marked as already visited. Node c will do, and we invoke the
depth-first search algorithm beginning with node c.
Node c is marked and written out, and we look for unmarked nodes adjacent to
c. By our alphabetical convention, we select node d from the set 5d, f 6. Continuing
in this fashion, after visiting node d we next visit node f and then node g. When we
get to node g, we have reached a dead end because there are no unvisited adjacent
nodes. Thus the for loop of the instance of the algorithm invoked with node g is
complete. (The graph at this point looks like Figure 7.13.)
We are therefore done with the algorithm for node g, but node g was (possibly
one of) the unmarked nodes adjacent to node f, and we are still in the for loop for the
instance of the algorithm invoked with node f. As it happens, g is the only unvisited
node when we are processing f; therefore we complete the for loop and thus the algorithm for node f. Similarly, backing up to node d, the algorithm finds no other adjacent
unmarked nodes, and it backs up again to the instance of the algorithm invoked with
node c. Thus, after processing node d and everything that came after it until the dead
end, we are still in the for loop for the algorithm applied to node c. We look for other
unmarked nodes adjacent to c and find one—node e. Therefore we apply depth-first
search to node e, which leads to nodes h, i, and k before another dead end is reached.
Backing up, we have a final new path to try from node h, which leads to node j. The
complete list of the nodes, in the order in which they would be written out, is
a, b, c, d, f, g, e, h, i, k, j
ReminDeR
In a depth-first search, go
as far as possible, then
back up, catching any
paths missed on the way
down.