Previous Next 
DFS AlgorithmsRegardless of the graph structure or the representation, any DFS forest allows us to identify edges as tree or back edges and gives us dependable insights into graph structure that allow us to use DFS as a basis for solving numerous graphprocessing problems. We have already seen, in , basic examples related to finding paths. In this section, we consider DFSbased ADT method implementations for these and other typical problems; in the remainder of this chapter and in the next several chapters, we look at numerous solutions to much more difficult problems. Cycle detection Does a given graph have any cycles? (Is the graph a forest?) This problem is easy to solve with DFS because any back edge in a DFS tree belongs to a cycle consisting of the edge plus the tree path connecting the two nodes (see Screenshot). Thus, we can use DFS immediately to check for cycles: A graph is acyclic if and only if we encounter no back (or down!) edges during a DFS. For example, to test this condition in Program 18.1, we simply add an else clause to the if statement to test whether t is equal to v. If it is, we have just encountered the parent link wv (the second representation of the edge vw that led us to w). If it is not, wt completes a cycle with the edges from t down to w in the DFS tree. Moreover, we do not need to examine all the edges: We know that we must find a cycle or finish the search without finding one before examining V edges, because any graph with V or more edges must have a cycle. Thus, we can test whether a graph is acyclic in time proportional to V with the adjacencylists representation, although we may need time proportional to V^{2} (to find the edges) with the adjacencymatrix representation. Simple path Given two vertices, is there a path in the graph that connects them? We saw in that a DFS class that can solve this problem in linear time is easy to devise. Simple connectivity As discussed in , we determine whether or not a graph is connected whenever we use DFS, in linear time. Indeed, our graphsearch strategy is based upon calling a search method for each connected component. In a DFS, the graph is connected if and only if the graphsearch method calls the recursive DFS method just once (see Program 18.2). The number of connected components in the graph is precisely the number of times that the recursive method is called from GraphDFS, so we can find the number of connected components by simply keeping track of the number of such calls. More generally, Program 18.3 illustrates a DFS class that supports constanttime connectivity queries after a lineartime preprocessing step in the constructor. It visits vertices in the same order as does Program 18.2. The recursive method uses a vertex as its second parameter instead of an edge, since it does not need to know the identity of the parent. Each tree in the DFS forest identifies a connected component, so we arrange to decide quickly whether two vertices are in the same component by including a vertexindexed array in the graph representation, to be filled in by a DFS and accessed for connectivity queries. In the recursive DFS method, we assign the current value of the component counter to the entry corresponding to each vertex visited. Then, we know that two vertices are in the same component if and only if their entries in this array are equal. Again, note that this array reflects structural properties of the graph, rather than artifacts of the graph representation or of the search dynamics. Program 18.3 typifies the basic approach that we shall use in addressing numerous graphprocessing tasks. We develop a taskspecific class so that clients can create objects to perform the task. Typically, we invest preprocessing time in the constructor to compute private data about relevant structural graph properties that help us to provide efficient implementations of public query methods. In this case, the constructor preprocesses with a (lineartime) DFS and keeps a private data field (the vertexindexed array id) that allows it to answer connectivity queries in constant time. For other graphprocessing problems, our constructors might use more space, preprocessing time, or query time. As usual, our focus is on minimizing such costs, although doing so is often challenging. For example, much of is devoted to solving the connectivity problem for digraphs, where achieving linear time preprocessing and constant query time, as in Program 18.3, is an elusive goal.
How does the DFSbased solution for graph connectivity in Program 18.3 compare with the unionfind approach that we considered in Chapter 1 for the problem of determining whether a graph is connected, given an edge list? In theory, DFS is faster than unionfind because it provides a constanttime guarantee, which unionfind does not; in practice, this difference is negligible, and unionfind is faster because it does not have to build a full representation of the graph. More important, unionfind is an online algorithm (we can check whether two vertices are connected in nearconstant time at any point), whereas the DFS solution preprocesses the graph to answer connectivity queries in constant time. Therefore, for example, we prefer unionfind when determining connectivity is our only task or when we have a large number of queries intermixed with edge insertions but may find the DFS solution more appropriate for use in a graph ADT because it makes efficient use of existing infrastructure. Neither approach handles efficiently huge numbers of intermixed edge insertions, edge deletions, and connectivity queries; both require a separate DFS to compute the path. These considerations illustrate the complications that we face when analyzing graph algorithms; we explore them in detail in .
Twoway Euler tour Program 18.4 is a DFSbased class for finding a path that uses all the edges in a graph exactly twice—once in each direction (see ). The path corresponds to a Trémaux exploration in which we take our string with us everywhere that we go, check for the string instead of using lights (so we have to go down the passages that lead to intersections that we have already visited), and first arrange to go back and forth on each back link (the first time that we encounter each back edge), then ignore down links (the second time that we encounter each back edge). We might also choose to ignore the back links (first encounter) and to go back and forth on down links (second encounter) (see Exercise 18.25). Spanning forest Given a connected graph with V vertices, find a set of V – 1 edges that connects the vertices. If the graph has C connected components, find a spanning forest (with V – C edges). We have already seen a DFS class that solves this problem: Program 18.2. Vertex search How many vertices are in the same connected component as a given vertex? We can solve this problem easily by starting a DFS at the vertex and counting the number of vertices marked. In a dense graph, we can speed up the process considerably by stopping the DFS after we have marked V vertices—at that point, we know that no edge will take us to a vertex that we have not yet seen, so we will be ignoring all the rest of the edges. This improvement is likely to allow us to visit all vertices in time proportional to V log V, not E (see ). Twocolorability, bipartiteness, odd cycle Is there a way to assign one of two colors to each vertex of a graph such that no edge connects two vertices of the same color? Is a given graph bipartite (see )? Does a given graph have a cycle of odd length? These three problems are all equivalent: The first two are different nomenclature for the same problem; any graph with an odd cycle is clearly not twocolorable, and Program 18.5 demonstrates that any graph that is free of odd cycles can be twocolored. The program is a DFSbased implementation that tests whether a graph is bipartite, twocolorable, and free of odd cycles. The recursive method is an outline for a proof by induction that the program twocolors any graph with no odd cycles (or finds an odd cycle as evidence that a graph that is not free of odd cycles cannot be twocolored). To twocolor a graph with a given color assigned to a vertex v, twocolor the remaining graph, assigning the other color to each vertex adjacent to v. This process is equivalent to assigning alternate colors on levels as we proceed down the DFS tree, checking back edges for consistency in the coloring, as illustrated in Screenshot. Any back edge connecting two vertices of the same color is evidence of an odd cycle. Screenshot Twocoloring a DFS treeTo twocolor a graph, we alternate colors as we move down the DFS tree, then check the back edges for inconsistencies. In the tree at the top, a DFS tree for the sample graph illustrated in Screenshot, the back edges 54 and 70 prove that the graph is not twocolorable because of the oddlength cycles 4354 and 026470, respectively. In the tree at the bottom, a DFS tree for the bipartite graph illustrated in Screenshot, there are no such inconsistencies, and the indicated shading is a twocoloring of the graph. These basic examples illustrate ways in which DFS can give us insight into the structure of a graph. They also demonstrate that we can learn various important graph properties in a single lineartime sweep through the graph, where we examine every edge twice, once in each direction. Next, we consider an example that shows the utility of DFS in discovering more intricate details about the graph structure, still in linear time. Exercises

Previous Next 