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 , 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 , 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. Screenshot 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 Screenshot), when the adjacency-matrix graph implementation of is used. Screenshot depicts the maze-exploration process using standard graph drawings.
Screenshot 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.
Screenshot Depth-first search
These diagrams are a graphical view of the process depicted in Screenshot, 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 0, 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).
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. Screenshot also depicts the tree corresponding to the recursive calls as it evolves, in correspondence with Screenshot. This recursive-call tree, which is known as the DFS tree, is a structural description of the search process. As we see in , 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, Screenshot shows the search dynamic when the adjacency-lists implementation of 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.
Screenshot 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 Screenshot.
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.
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 .
Draw the corresponding DFS recursive-call tree.
Show, in the style of Screenshot, the progress of the search for the example in Exercise 18.6.