18.2 Depth-First Search

Our interest in Tr maux exploration is that this technique leads us immediately to the classic recursive method for traversing graphs: To visit a vertex, we mark it as having been visited, then (recursively) visit all the vertices that are adjacent to it and that have not yet been marked . This method, which we considered briefly in Chapters 3 and 5 and used to solve path problems in Section 17.7, is called depth-first search (DFS) . It is one of the most important algorithms that we shall encounter. DFS is deceptively simple because it is based on a familiar concept and is easy to implement; in fact, it is a subtle and powerful algorithm that we put to use for numerous difficult graph-processing tasks .

Program 18.1 is a DFS class that visits all the vertices and examines all the edges in a connected graph. Like the simple path-search methods that we considered in Section 17.7, it is based on a recursive method that keeps a private array to mark vertices as having been visited. In this implementation, ord is an array of integers that records the order in which vertices are visited. Figure 18.5 is a trace that shows the order in which Program 18.1 visits the edges and vertices for the example depicted in Figures 18.2 and 18.3 (see also Figure 18.17), when the adjacency -matrix graph implementation of Section 17.3 is used. Figure 18.6 depicts the maze-exploration process using standard graph drawings.

Figure 18.5. DFS trace

This trace shows the order in which DFS checks the edges and vertices for the adjacency-matrix representation of the graph corresponding to the example in Figures 18.2 and 18.3 (top) and traces the contents of the ord vector (right) as the search progresses ( asterisks represent -1 , for unseen vertices). There are two lines in the trace for every graph edge (once for each orientation). Indentation indicates the level of recursion .

Figure 18.6. Depth-first search

These diagrams are a graphical view of the process depicted in Figure 18.5, showing the DFS recursive-call tree as it evolves. Thick black edges in the graph correspond to edges in the DFS tree shown to the right of each graph diagram. Shaded edges are the candidates to be added to the tree next . In the early stages (left) the tree grows down in a straight line, as we make recursive calls for , 2 , 6 , and 4 (left). Then we make recursive calls for 3 , then 5 (right, top two diagrams), and return from those calls to make a recursive call for 7 from 4 (right, second from bottom) and to 1 from 7 (right, bottom).

These figures illustrate the dynamics of a recursive DFS and show the correspondence with Tr maux exploration of a maze. First, the vertex-indexed array corresponds to the lights in the intersections: When we encounter an edge to a vertex that we have already visited (see a light at the end of the passage), we do not make a recursive call to follow that edge (go down that passage). Second, the method call “return mechanism in the program corresponds to the string in the maze: When we have processed all the edges adjacent to a vertex (explored all the passages leaving an intersection), we "return" (in both senses of the word).

Program 18.1 Depth-first search of a connected component

This DFS class corresponds to Tr maux exploration. The constructor marks as visited all vertices in the same connected component as v by calling the recursive searchC , which visits all the vertices adjacent to v by checking them all and calling itself for each edge that leads from v to an unmarked vertex. Clients can use the count method to learn the number of vertices encountered and the order method to learn the order in which the search visited the vertices.

 class GraphDFSc { private Graph G; private int cnt; private int[] ord; private void searchC(int v) { ord[v] = cnt++; AdjList A = G.getAdjList(v); for (int t = A.beg(); !A.end(); t = A.nxt()) if (ord[t] == -1) searchC(t); } GraphDFSc(Graph G, int v) { this.G = G; cnt = 0; ord = new int[G.V()]; for (int t = 0; t < G.V(); t++) ord[t] = -1; searchC(v); } int count() { return cnt; } int order(int v) { return ord[v]; } } 

In the same way that we encounter each passage in the maze twice (once at each end), we encounter each edge in the graph twice (once at each of its vertices). In Tr maux exploration, we open the doors at each end of each passage; in DFS of an undirected graph, we check each of the two representations of each edge. If we encounter an edge v-w , we either do a recursive call (if w is not marked) or skip the edge (if w is marked). The second time that we encounter the edge, in the opposite orientation w-v , we always ignore it, because the destination vertex v has certainly already been visited (the first time that we encountered the edge).

One difference between DFS as implemented in Program 18.1 and Tr maux exploration as depicted in Figures 18.2 and 18.3, although it is inconsequential in many contexts, is worth taking the time to understand. When we move from vertex v to vertex w , we have not examined any of the entries in the adjacency list that correspond to edges from w to other vertices in the graph. In particular, we know that there is an edge from w to v and that we will ignore that edge when we get to it (because v is marked as visited). That decision happens at a time different from in the Tr maux exploration, where we open the doors corresponding to the edge from v to w when we go to w for the first time, from v . If we were to close those doors on the way in and open them on the way out (having identified the passage with the string), then we would have a precise correspondence between DFS and Tr maux exploration.

Figure 18.6 also depicts the tree corresponding to the recursive calls as it evolves, in correspondence with Figure 18.5. This recursive-call tree, which is known as the DFS tree , is a structural description of the search process. As we see in Section 18.4, the DFS tree, properly augmented, can provide a full description of the search dynamics, in addition to just the call structure.

The order in which vertices are visited depends not just on the graph but on its representation and ADT implementation. For example, Figure 18.7 shows the search dynamic when the adjacency-lists implementation of Section 17.4 is used. For the adjacency-matrix representation, we examine the edges incident on each vertex in numerical order; for the adjacency-lists representation, we examine them in the order that they appear on the lists. This difference leads to a completely different recursive search dynamic, as would differences in the order in which edges appear on the lists (which occur, for example, when the same graph is constructed by inserting edges in a different order). Note also that the existence of parallel edges is inconsequential for DFS because any edge that is parallel to an edge that has already been traversed is ignored, since its destination vertex has been visited.

Figure 18.7. DFS trace (adjacency lists)

This trace shows the order in which DFS checks the edges and vertices for the adjacency-lists representation of the same graph as in Figure 18.5 .

Despite all of these possibilities, the critical fact remains that DFS visits all the edges and all the vertices connected to the start vertex, regardless of in what order it examines the edges incident on each vertex. This fact is a direct consequence of Property 18.1, since the proof of that property does not depend on the order in which the doors are opened at any given intersection. All the DFS-based algorithms that we examine have this same essential property. Although the dynamics of their operation might vary substantially depending on the graph representation and details of the implementation of the search, the recursive structure gives us a way to make relevant inferences about the graph itself, no matter how it is represented and no matter which order we choose to examine the edges incident upon each vertex.

Exercises

18.4 Add a method to Program 18.1 that returns the size of the connected component searched by the constructor.

18.5 Write a client program like Program 17.6 that scans a graph from standard input, uses Program 18.1 to run a search starting at each vertex, and prints out the parent-link representation of each spanning forest. Use the DenseGRAPH graph ADT implementation from Section 17.3.

18.6 Show, in the style of Figure 18.5, a trace of the recursive method calls made when an adjacency-matrix representation is used, for the graph

Draw the corresponding DFS recursive-call tree.

18.7 Show, in the style of Figure 18.6, the progress of the search for the example in Exercise 18.6.