Previous Next 
DepthFirst SearchOur 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 depthfirst 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 graphprocessing 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 pathsearch 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 adjacencymatrix graph implementation of is used. Screenshot depicts the mazeexploration process using standard graph drawings. Screenshot DFS traceThis trace shows the order in which DFS checks the edges and vertices for the adjacencymatrix 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 Depthfirst searchThese diagrams are a graphical view of the process depicted in Screenshot, showing the DFS recursivecall 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 vertexindexed 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).
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 vw, 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 wv, 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 recursivecall 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 adjacencylists implementation of is used. For the adjacencymatrix representation, we examine the edges incident on each vertex in numerical order; for the adjacencylists 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 adjacencylists 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 DFSbased 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

Previous Next 