596
Graph Algorithms
S e c t i o n 7 . 4 tr aversal alGorithms
So far this chapter has considered various path questions about a graph G. Is there
a path in G from node x to node y? Is there a path through G that uses each arc
once? Is there a path through G that ends where we started and uses each node
once? What is the minimum-weight path between x and y? In this section we deal
with a simpler problem—we only want to write down all the nodes of a simple,
connected graph G in some orderly way. This means we must find a path that
visits each node at least once, but we can visit it more than once if we don’t write
it down again. We can also retrace arcs on the graph if necessary, and clearly this
would in general be necessary if we were to visit each node in a tree. This process
is called graph traversal. We already have several mechanisms for tree traversal
(Section 6.2). The two algorithms in this section generalize traversal to apply to
any simple, connected graph.
Depth-First search
In the depth-first search algorithm for graph traversal, we begin at an arbitrary
node a of the graph, mark it visited, and write it down. We then strike out on a
path away from a, visiting and writing down nodes, proceeding as far as possible until there are no more unvisited nodes on that path. We then back up the
path, at each node exploring any new side paths, until finally we retreat back to
a. We then explore any new paths remaining from a. Figure 7.13 shows a graph
after the first few nodes (marked by circles) have been visited using depth-first
search.
Figure 7.13
For a more formal description of the depth-first search algorithm we will use
recursion, where the algorithm invokes itself in the course of its execution. In the
following algorithm, the input is a simple, connected graph G and a specified node
a; the output is a list of all nodes in G in depth-first order from a.
Graph Algorithms
S e c t i o n 7 . 4 tr aversal alGorithms
So far this chapter has considered various path questions about a graph G. Is there
a path in G from node x to node y? Is there a path through G that uses each arc
once? Is there a path through G that ends where we started and uses each node
once? What is the minimum-weight path between x and y? In this section we deal
with a simpler problem—we only want to write down all the nodes of a simple,
connected graph G in some orderly way. This means we must find a path that
visits each node at least once, but we can visit it more than once if we don’t write
it down again. We can also retrace arcs on the graph if necessary, and clearly this
would in general be necessary if we were to visit each node in a tree. This process
is called graph traversal. We already have several mechanisms for tree traversal
(Section 6.2). The two algorithms in this section generalize traversal to apply to
any simple, connected graph.
Depth-First search
In the depth-first search algorithm for graph traversal, we begin at an arbitrary
node a of the graph, mark it visited, and write it down. We then strike out on a
path away from a, visiting and writing down nodes, proceeding as far as possible until there are no more unvisited nodes on that path. We then back up the
path, at each node exploring any new side paths, until finally we retreat back to
a. We then explore any new paths remaining from a. Figure 7.13 shows a graph
after the first few nodes (marked by circles) have been visited using depth-first
search.
Figure 7.13
For a more formal description of the depth-first search algorithm we will use
recursion, where the algorithm invokes itself in the course of its execution. In the
following algorithm, the input is a simple, connected graph G and a specified node
a; the output is a list of all nodes in G in depth-first order from a.