Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 103
Текст из файла (страница 103)
Using Figure 22.3 as an example,show that the breadth-first tree computed by BFS can depend on the ordering withinadjacency lists.Exercises 22.2-5Give an example of a directed graph G = (V, E), a source vertex s V , and a set of tree edgesEπ E such that for each vertex v V, the unique path in the graph (V, Eπ) from s to v is ashortest path in G, yet the set of edges Eπ cannot be produced by running BFS on G, no matterhow the vertices are ordered in each adjacency list.Exercises 22.2-6There are two types of professional wrestlers: "good guys" and "bad guys." Between any pairof professional wrestlers, there may or may not be a rivalry.
Suppose we have n professionalwrestlers and we have a list of r pairs of wrestlers for which there are rivalries. Give an O(n +r)-time algorithm that determines whether it is possible to designate some of the wrestlers asgood guys and the remainder as bad guys such that each rivalry is between a good guy and abad guy. If is it possible to perform such a designation, your algorithm should produce it.Exercises 22.2-7: ⋆The diameter of a tree T =(V, E) is given bythat is, the diameter is the largest of all shortest-path distances in the tree.
Give an efficientalgorithm to compute the diameter of a tree, and analyze the running time of your algorithm.Exercises 22.2-8Let G = (V, E) be a connected, undirected graph. Give an O(V + E)-time algorithm to computea path in G that traverses each edge in E exactly once in each direction. Describe how you canfind your way out of a maze if you are given a large supply of pennies.[1]In Chapters 24 and 25, we shall generalize our study of shortest paths to weighted graphs, inwhich every edge has a real-valued weight and the weight of a path is the sum of the weightsof its constituent edges. The graphs considered in the present chapter are unweighted or,equivalently, all edges have unit weight.22.3 Depth-first searchThe strategy followed by depth-first search is, as its name implies, to search "deeper" in thegraph whenever possible. In depth-first search, edges are explored out of the most recentlydiscovered vertex v that still has unexplored edges leaving it.
When all of v's edges have beenexplored, the search "backtracks" to explore edges leaving the vertex from which v wasdiscovered. This process continues until we have discovered all the vertices that are reachablefrom the original source vertex. If any undiscovered vertices remain, then one of them isselected as a new source and the search is repeated from that source.
This entire process isrepeated until all vertices are discovered.As in breadth-first search, whenever a vertex v is discovered during a scan of the adjacencylist of an already discovered vertex u, depth-first search records this event by setting v'spredecessor field π[v] to u. Unlike breadth-first search, whose predecessor subgraph forms atree, the predecessor subgraph produced by a depth-first search may be composed of severaltrees, because the search may be repeated from multiple sources.[2] The predecessor subgraphof a depth-first search is therefore defined slightly differently from that of a breadth-firstsearch: we let Gπ = (V, Eπ), whereEπ = {(π[v], v) : vV and π[v] ≠ NIL}.The predecessor subgraph of a depth-first search forms a depth-first forest composed ofseveral depth-first trees.
The edges in Eπ are called tree edges.As in breadth-first search, vertices are colored during the search to indicate their state. Eachvertex is initially white, is grayed when it is discovered in the search, and is blackened when itis finished, that is, when its adjacency list has been examined completely. This techniqueguarantees that each vertex ends up in exactly one depth-first tree, so that these trees aredisjoint.Besides creating a depth-first forest, depth-first search also timestamps each vertex. Eachvertex v has two timestamps: the first timestamp d[v] records when v is first discovered (andgrayed), and the second timestamp f [v] records when the search finishes examining v'sadjacency list (and blackens v). These timestamps are used in many graph algorithms and aregenerally helpful in reasoning about the behavior of depth-first search.The procedure DFS below records when it discovers vertex u in the variable d[u] and when itfinishes vertex u in the variable f [u].
These timestamps are integers between 1 and 2 |V|, sincethere is one discovery event and one finishing event for each of the |V| vertices. For everyvertex u,(22.2)Vertex u is WHITE before time d[u], GRAY between time d[u] and time f [u], and BLACKthereafter.The following pseudocode is the basic depth-first-search algorithm. The input graph G maybe undirected or directed. The variable time is a global variable that we use for timestamping.DFS(G)1 for each vertex uV [G]2do color[u] ← WHITE3π[u] ← NIL4 time ← 05 for each vertex uV [G]6do if color[u] = WHITE7then DFS-VISIT(u)DFS-VISIT(u)▹White vertex u has just been discovered.123color[u] ← GRAYtime ← time +1d[u] time4567for each vAdj[u] ▹Explore edge(u, v).do if color[v] = WHITEthen π[v] ← uDFS-VISIT(v)8color[u] BLACK9f [u] ▹ time ← time +1▹ Blacken u; it is finished.Figure 22.4 illustrates the progress of DFS on the graph shown in Figure 22.2.Figure 22.4: The progress of the depth-first-search algorithm DFS on a directed graph.
Asedges are explored by the algorithm, they are shown as either shaded (if they are tree edges)or dashed (otherwise). Nontree edges are labeled B, C, or F according to whether they areback, cross, or forward edges. Vertices are timestamped by discovery time/finishing time.Procedure DFS works as follows.
Lines 1-3 paint all vertices white and initialize their π fieldsto NIL. Line 4 resets the global time counter. Lines 5-7 check each vertex in V in turn and,when a white vertex is found, visit it using DFS-VISIT. Every time DFS-VISIT(u) is called inline 7, vertex u becomes the root of a new tree in the depth-first forest. When DFS returns,every vertex u has been assigned a discovery time d[u] and a finishing time f [u].In each call DFS-VISIT(u), vertex u is initially white.
Line 1 paints u gray, line 2 incrementsthe global variable time, and line 3 records the new value of time as the discovery time d[u].Lines 4-7 examine each vertex v adjacent to u and recursively visit v if it is white. As eachvertex v Adj[u] is considered in line 4, we say that edge (u, v) is explored by the depth-firstsearch. Finally, after every edge leaving u has been explored, lines 8-9 paint u black andrecord the finishing time in f [u].Note that the results of depth-first search may depend upon the order in which the vertices areexamined in line 5 of DFS, and upon the order in which the neighbors of a vertex are visitedin line 4 of DFS-VISIT. These different visitation orders tend not to cause problems inpractice, as any depth-first search result can usually be used effectively, with essentiallyequivalent results.What is the running time of DFS? The loops on lines 1-3 and lines 5-7 of DFS take time Θ(V),exclusive of the time to execute the calls to DFS-VISIT.
As we did for breadth-first search,we use aggregate analysis. The procedure DFS-VISIT is called exactly once for each vertex vV , since DFS-VISIT is invoked only on white vertices and the first thing it does is paint thevertex gray. During an execution of DFS-VISIT(v), the loop on lines 4-7 is executed |Adj[v]|times. Sincethe total cost of executing lines 4-7 of DFS-VISIT is Θ(E). The running time of DFS istherefore Θ(V + E).Properties of depth-first searchDepth-first search yields valuable information about the structure of a graph.
Perhaps the mostbasic property of depth-first search is that the predecessor subgraph Gπ does indeed form aforest of trees, since the structure of the depth-first trees exactly mirrors the structure ofrecursive calls of DFS-VISIT. That is, u = π[v] if and only if DFS-VISIT(v) was called duringa search of u's adjacency list. Additionally, vertex v is a descendant of vertex u in the depthfirst forest if and only if v is discovered during the time in which u is gray.Another important property of depth-first search is that discovery and finishing times haveparenthesis structure. If we represent the discovery of vertex u with a left parenthesis "(u"and represent its finishing by a right parenthesis "u)", then the history of discoveries andfinishings makes a well-formed expression in the sense that the parentheses are properlynested.
For example, the depth-first search of Figure 22.5(a) corresponds to theparenthesization shown in Figure 22.5(b). Another way of stating the condition of parenthesisstructure is given in the following theorem.Figure 22.5: Properties of depth-first search. (a) The result of a depth-first search of a directedgraph. Vertices are timestamped and edge types are indicated as in Figure 22.4.
(b) Intervalsfor the discovery time and finishing time of each vertex correspond to the parenthesizationshown. Each rectangle spans the interval given by the discovery and finishing times of thecorresponding vertex. Tree edges are shown. If two intervals overlap, then one is nestedwithin the other, and the vertex corresponding to the smaller interval is a descendant of thevertex corresponding to the larger. (c) The graph of part (a) redrawn with all tree and forwardedges going down within a depth-first tree and all back edges going up from a descendant toan ancestor.Theorem 22.7: (Parenthesis theorem)In any depth-first search of a (directed or undirected) graph G = (V, E), for any two vertices uand v, exactly one of the following three conditions holds:•••the intervals [d[u], f[u]] and [d[v], f[v]] are entirely disjoint, and neither u nor v is adescendant of the other in the depth-first forest,the interval [d[u], f[u]] is contained entirely within the interval [d[v], f[v]], and u is adescendant of v in a depth-first tree, orthe interval [d[v], f[v]] is contained entirely within the interval [d[u], f[u]], and v is adescendant of u in a depth-first tree.Proof We begin with the case in which d[u] < d[v].
There are two subcases to consider,according to whether d[v] < f[u] or not. The first subcase occurs when d[v] < f[u], so v wasdiscovered while u was still gray. This implies that v is a descendant of u. Moreover, since vwas discovered more recently than u, all of its outgoing edges are explored, and v is finished,before the search returns to and finishes u.
In this case, therefore, the interval [d[v], f[v]] isentirely contained within the interval [d[u], f[u]]. In the other subcase, f[u] < d[v], andinequality (22.2) implies that the intervals [d[u], f[u]] and [d[v], f[v]] are disjoint. Because theintervals are disjoint, neither vertex was discovered while the other was gray, and so neithervertex is a descendant of the other.The case in which d[v] < d[u] is similar, with the roles of u and v reversed in the aboveargument.Corollary 22.8: (Nesting of Descendants' Intervals)Vertex v is a proper descendant of vertex u in the depth-first forest for a (directed orundirected) graph G if and only if d[u] < d[v] < f[v] < f[u].Proof Immediate from Theorem 22.7.The next theorem gives another important characterization of when one vertex is a descendantof another in the depth-first forest.Theorem 22.9: (White-path theorem)In a depth-first forest of a (directed or undirected) graph G = (V, E), vertex v is a descendantof vertex u if and only if at the time d[u] that the search discovers u, vertex v can be reachedfrom u along a path consisting entirely of white vertices.Proof : Assume that v is a descendant of u.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
