Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 104
Текст из файла (страница 104)
Let w be any vertex on the path between u and vin the depth-first tree, so that w is a descendant of u. By Corollary 22.8, d[u] < d[w], and so wis white at time d[u].⇐: Suppose that vertex v is reachable from u along a path of white vertices at time d[u], but vdoes not become a descendant of u in the depth-first tree. Without loss of generality, assumethat every other vertex along the path becomes a descendant of u. (Otherwise, let v be theclosest vertex to u along the path that doesn't become a descendant of u.) Let w be thepredecessor of v in the path, so that w is a descendant of u (w and u may in fact be the samevertex) and, by Corollary 22.8, f[w] ≤ f[u].
Note that v must be discovered after u isdiscovered, but before w is finished. Therefore, d[u] < d[v] < f[w] ≤ f[u]. Theorem 22.7 thenimplies that the interval [d[v], f[v]] is contained entirely within the interval [d[u], f[u]]. ByCorollary 22.8, v must after all be a descendant of u.Classification of edgesAnother interesting property of depth-first search is that the search can be used to classify theedges of the input graph G = (V, E).
This edge classification can be used to glean importantinformation about a graph. For example, in the next section, we shall see that a directed graphis acyclic if and only if a depth-first search yields no "back" edges (Lemma 22.11).We can define four edge types in terms of the depth-first forest Gπ produced by a depth-firstsearch on G.1. Tree edges are edges in the depth-first forest Gπ. Edge (u, v) is a tree edge if v was firstdiscovered by exploring edge (u, v).2.
Back edges are those edges (u, v) connecting a vertex u to an ancestor v in a depthfirst tree. Self-loops, which may occur in directed graphs, are considered to be backedges.3. Forward edges are those nontree edges (u, v) connecting a vertex u to a descendant vin a depth-first tree.4. Cross edges are all other edges. They can go between vertices in the same depth-firsttree, as long as one vertex is not an ancestor of the other, or they can go betweenvertices in different depth-first trees.In Figures 22.4 and 22.5, edges are labeled to indicate their type.
Figure 22.5(c) also showshow the graph of Figure 22.5(a) can be redrawn so that all tree and forward edges headdownward in a depth-first tree and all back edges go up. Any graph can be redrawn in thisfashion.The DFS algorithm can be modified to classify edges as it encounters them. The key idea isthat each edge (u, v) can be classified by the color of the vertex v that is reached when theedge is first explored (except that forward and cross edges are not distinguished):1.
WHITE indicates a tree edge,2. GRAY indicates a back edge, and3. BLACK indicates a forward or cross edge.The first case is immediate from the specification of the algorithm. For the second case,observe that the gray vertices always form a linear chain of descendants corresponding to thestack of active DFS-VISIT invocations; the number of gray vertices is one more than thedepth in the depth-first forest of the vertex most recently discovered. Exploration alwaysproceeds from the deepest gray vertex, so an edge that reaches another gray vertex reaches anancestor. The third case handles the remaining possibility; it can be shown that such an edge(u, v) is a forward edge if d[u] < d[v] and a cross edge if d[u] > d[v].
(See Exercise 22.3-4.)In an undirected graph, there may be some ambiguity in the type classification, since (u, v)and (v, u) are really the same edge. In such a case, the edge is classified as the first type in theclassification list that applies. Equivalently (see Exercise 22.3-5), the edge is classifiedaccording to whichever of (u, v) or (v, u) is encountered first during the execution of thealgorithm.We now show that forward and cross edges never occur in a depth-first search of anundirected graph.Theorem 22.10In a depth-first search of an undirected graph G, every edge of G is either a tree edge or aback edge.Proof Let (u, v) be an arbitrary edge of G, and suppose without loss of generality that d[u] <d[v]. Then, v must be discovered and finished before we finish u (while u is gray), since v ison u's adjacency list.
If the edge (u, v) is explored first in the direction from u to v, then v isundiscovered (white) until that time, for otherwise we would have explored this edge alreadyin the direction from v to u. Thus, (u, v) becomes a tree edge. If (u, v) is explored first in thedirection from v to u, then (u, v) is a back edge, since u is still gray at the time the edge is firstexplored.We shall see several applications of these theorems in the following sections.Exercises 22.3-1Make a 3-by-3 chart with row and column labels WHITE, GRAY, and BLACK.
In each cell(i, j), indicate whether, at any point during a depth-first search of a directed graph, there canbe an edge from a vertex of color i to a vertex of color j. For each possible edge, indicate whatedge types it can be. Make a second such chart for depth-first search of an undirected graph.Exercises 22.3-2Show how depth-first search works on the graph of Figure 22.6. Assume that the for loop oflines 5-7 of the DFS procedure considers the vertices in alphabetical order, and assume thateach adjacency list is ordered alphabetically. Show the discovery and finishing times for eachvertex, and show the classification of each edge.Figure 22.6: A directed graph for use in Exercises 22.3-2 and 22.5-2.Exercises 22.3-3Show the parenthesis structure of the depth-first search shown in Figure 22.4.Exercises 22.3-4Show that edge (u, v) is1.
a tree edge or forward edge if and only if d[u] < d[v] < f[v] < f[u],2. a back edge if and only if d[v] < d[u] < f[u] < f[v], and3. a cross edge if and only if d[v] < f[v] < d[u] < f[u].Exercises 22.3-5Show that in an undirected graph, classifying an edge (u, v) as a tree edge or a back edgeaccording to whether (u, v) or (v, u) is encountered first during the depth-first search isequivalent to classifying it according to the priority of types in the classification scheme.Exercises 22.3-6Rewrite the procedure DFS, using a stack to eliminate recursion.Exercises 22.3-7Give a counterexample to the conjecture that if there is a path from u to v in a directed graphG, and if d[u] < d[v] in a depth-first search of G, then v is a descendant of u in the depth-firstforest produced.Exercises 22.3-8Give a counterexample to the conjecture that if there is a path from u to v in a directed graphG, then any depth-first search must result in d[v] ≤ f[u].Exercises 22.3-9Modify the pseudocode for depth-first search so that it prints out every edge in the directedgraph G, together with its type.
Show what modifications, if any, must be made if G isundirected.Exercises 22.3-10Explain how a vertex u of a directed graph can end up in a depth-first tree containing only u,even though u has both incoming and outgoing edges in G.Exercises 22.3-11Show that a depth-first search of an undirected graph G can be used to identify the connectedcomponents of G, and that the depth-first forest contains as many trees as G has connectedcomponents. More precisely, show how to modify depth-first search so that each vertex v isassigned an integer label cc[v] between 1 and k, where k is the number of connectedcomponents of G, such that cc[u] = cc[v] if and only if u and v are in the same connectedcomponent.Exercises 22.3-12: ⋆A directed graph G = (V, E) is singly connected ifimplies that there is at most onesimple path from u to v for all vertices u, v V. Give an efficient algorithm to determinewhether or not a directed graph is singly connected.[2]It may seem arbitrary that breadth-first search is limited to only one source whereas depthfirst search may search from multiple sources.
Although conceptually, breadth-first searchcould proceed from multiple sources and depth-first search could be limited to one source, ourapproach reflects how the results of these searches are typically used. Breadth-first search isusually employed to find shortest-path distances (and the associated predecessor subgraph)from a given source. Depth-first search is often a subroutine in another algorithm, as we shallsee later in this chapter.22.4 Topological sortThis section shows how depth-first search can be used to perform a topological sort of adirected acyclic graph, or a "dag" as it is sometimes called.
A topological sort of a dag G =(V, E) is a linear ordering of all its vertices such that if G contains an edge (u, v), then uappears before v in the ordering. (If the graph is not acyclic, then no linear ordering ispossible.) A topological sort of a graph can be viewed as an ordering of its vertices along ahorizontal line so that all directed edges go from left to right. Topological sorting is thusdifferent from the usual kind of "sorting" studied in Part II.Directed acyclic graphs are used in many applications to indicate precedences among events.Figure 22.7 gives an example that arises when Professor Bumstead gets dressed in themorning. The professor must don certain garments before others (e.g., socks before shoes).Other items may be put on in any order (e.g., socks and pants).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
