Chapter 7: Graph Algorithms

Section 7.4 Traversal Algorithms

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

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.

In the recursive step, the algorithm is invoked with a new node specified as the starting point.

Practice

Reference

saylor academy