chap23.htm

介绍算法的书籍

<h1><a name="08a9_176e">23.3 Depth-first search<a name="08a9_176e"></h1><P>
<a name="08a9_175c"><a name="08a9_175d">The strategy followed by depth-first search is, as its name implies, to search &quot;deeper&quot; in the graph whenever possible. In depth-first search, edges are explored out of the most recently discovered vertex <I>v</I> that still has unexplored edges leaving it. When all of <I>v</I>'s edges have been explored, the search &quot;backtracks&quot; to explore edges leaving the vertex from which <I>v</I> was discovered. This process continues until we have discovered all the vertices that are reachable from the original source vertex. If any undiscovered vertices remain, then one of them is selected as a new source and the search is repeated from that source. This entire process is repeated until all vertices are discovered.<P>
<a name="08a9_175e">As in breadth-first search, whenever a vertex <I>v</I> is discovered during a scan of the adjacency list of an already discovered vertex <I>u</I>, depth-first search records this event by setting <I>v</I>'s predecessor field <img src="../images/piuc.gif">[<I>v</I>] to <I>u</I>. Unlike breadth-first search, whose predecessor subgraph forms a tree, the predecessor subgraph produced by a depth-first search may be composed of several trees, because the search may be repeated from multiple sources. The <I><B>predecessor subgraph</I></B> of a depth-first search is therefore defined slightly differently from that of a breadth-first search: we let <I>G</I><img src="../images/piuc.gif"><SUB> = (<I>V</I>, <I>E</I></SUB><FONT FACE="Courier New" SIZE=2><SUB><img src="../images/piuc.gif"></FONT></SUB>), where<P>
<pre><I>E</I><SUB></SUB><img src="../images/piuc.gif"><SUB> = {(<img src="../images/piuc.gif">[<I>v</I>], <I>v</I>) : <I>v</I> <img src="../images/memof12.gif"> <I>V</I> and <img src="../images/piuc.gif">[<I>v</I>] <img src="../images/noteq.gif"> NIL} .</sub></sup></pre><P>
<a name="08a9_175f"><a name="08a9_1760"><a name="08a9_1761"><a name="08a9_1762"><a name="08a9_1763"><a name="08a9_1764">The predecessor subgraph of a depth-first search forms a <I><B>depth-first forest</I></B> composed of several <I><B>depth-first trees.</I></B> The edges in <I>E</I><img src="../images/piuc.gif"> are called <I><B>tree edges</I></B>.<P>
<a name="08a9_1765"><a name="08a9_1766"><a name="08a9_1767"><a name="08a9_1768"><a name="08a9_1769">As in breadth-first search, vertices are colored during the search to indicate their state. Each vertex is initially white, is grayed when it is <I><B>discovered</I></B> in the search, and is blackened when it is <I><B>finished</I></B>, that is, when its adjacency list has been examined completely. This technique guarantees that each vertex ends up in exactly one depth-first tree, so that these trees are disjoint.<P>
<a name="08a9_176a">Besides creating a depth-first forest, depth-first search also <I><B>timestamps </I></B>each vertex. Each vertex <I>v</I> has two timestamps: the first timestamp <I>d</I>[<I>v</I>] records when <I>v</I> is first discovered (and grayed), and the second timestamp <I>f</I>[<I>v</I>] records when the search finishes examining <I>v</I>'s adjacency list (and blackens <I>v</I>). These timestamps are used in many graph algorithms and are generally helpful in reasoning about the behavior of depth-first search.<P>
The procedure DFS below records when it discovers vertex <I>u</I> in the variable <I>d</I>[<I>u</I>] and when it finishes vertex <I>u</I> in the variable <I>f</I>[<I>u</I>]. These timestamps are integers between 1 and 2 |<I>V|, since there is one discovery event and one finishing event for each of the |</I>V| vertices. For every vertex <I>u</I>,<P>
<pre><I>d</I>[<I>u</I>] &lt; <I>f</I>[<I>u</I>] .</sub></sup></pre><P>
<h4><a name="08a9_176f">(23.1)<a name="08a9_176f"></sub></sup></h4><P>
Vertex <I>u</I> is <FONT FACE="Courier New" SIZE=2>WHITE</FONT> before time <I>d</I>[<I>u</I>], <FONT FACE="Courier New" SIZE=2>GRAY</FONT> between time <I>d</I>[<I>u</I>] and time <I>f</I>[<I>u</I>], and <FONT FACE="Courier New" SIZE=2>BLACK</FONT> thereafter.<P>
The following pseudocode is the basic depth-first-search algorithm. The input graph <I>G</I> may be undirected or directed. The variable <I>time</I> is a global variable that we use for timestamping.<P>
<pre><a name="08a9_176b"><a name="08a9_176c">DFS(<I>G</I>)</sub></sup></pre><P>
<pre>1  <B>for</B> each vertex <I>u</I> <img src="../images/memof12.gif"> <I>V</I>[<I>G</I>]</sub></sup></pre><P>
<pre>2       <B>do</B> <I>color</I>[<I>u</I>] <img src="../images/arrlt12.gif"> WHITE</sub></sup></pre><P>
<pre>3          <img src="../images/piuc.gif">[<I>u</I>] <img src="../images/arrlt12.gif"> NIL</sub></sup></pre><P>
<pre>4  <I>time </I><img src="../images/arrlt12.gif"> 0</sub></sup></pre><P>
<pre>5  <B>for</B> each vertex <I>u</I> <img src="../images/memof12.gif"> <I>V</I>[<I>G</I>]</sub></sup></pre><P>
<pre>6       <B>do if</B> <I>color</I>[<I>u</I>] = WHITE</sub></sup></pre><P>
<pre>7             <B>then</B> DFS-VISIT(<I>u</I>)</sub></sup></pre><P>
<img src="478_a.gif"><P>
Figure 23.4 illustrates the progress of DFS on the graph shown in Figure 23.2.<P>
Procedure DFS works as follows. Lines 1-3 paint all vertices white and initialize their <img src="../images/piuc.gif"> fields to <FONT FACE="Courier New" SIZE=2>NIL</FONT>. Line 4 resets the global time counter. Lines 5-7 check each vertex in <I>V</I> in turn and, when a white vertex is found, visit it using DFS-<FONT FACE="Courier New" SIZE=2>VISIT</FONT>. Every time DFS-<FONT FACE="Courier New" SIZE=2>VISIT</FONT>(<I>u</I>) is called in line 7, vertex <I>u</I> becomes the root of a new tree in the depth-first forest. When DFS returns, every vertex <I>u</I> has been assigned a discovery time <I>d</I>[<I>u</I>] and a finishing time &acirc;[<I>u</I>].<P>
<a name="08a9_176d">In each call DFS-<FONT FACE="Courier New" SIZE=2>VISIT</FONT>(<I>u</I>), vertex <I>u</I> is initially white. Line 1 paints <I>u </I>gray, and line 2 records the discovery time <I>d</I>[<I>u</I>] by incrementing and saving the global variable <I>time</I>. Lines 3-6 examine each vertex <I>v</I> adjacent to <I>u</I> and recursively visit <I>v</I> if it is white. As each vertex <I>v</I> <img src="../images/memof12.gif"> <I>Adj</I>[<I>u</I>] is considered in line 3, we say that edge (<I>u, v</I>) is <I><B>explored</I></B> by the depth-first search. Finally, after every edge leaving <I>u</I> has been explored, lines 7-8 paint <I>u</I> black and record the finishing time in &acirc;[<I>u</I>].<P>
<img src="479_a.gif"><P>
<h4><a name="08a9_1770">Figure 23.4 The progress of the depth-first-search algorithm DFS on a directed graph. As edges 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 are back, cross, or forward edges. Vertices are timestamped by discovery time/finishing time.<a name="08a9_1770"></sub></sup></h4><P>
What is the running time of DFS? The loops on lines 1-2 and lines 5-7 of DFS take time <img src="../images/bound.gif">(<I>V</I>), exclusive of the time to execute the calls to DFS-<FONT FACE="Courier New" SIZE=2>VISIT</FONT>. The procedure DFS-<FONT FACE="Courier New" SIZE=2>VISIT</FONT> is called exactly once for each vertex the <I>v</I> <img src="../images/memof12.gif"> <I>V</I>, since DFS-<FONT FACE="Courier New" SIZE=2>VISIT</FONT> is invoked only on white vertices and the first thing it does is paint the vertex gray. During an execution of DFS-<FONT FACE="Courier New" SIZE=2>VISIT</FONT>(<I>v</I>), the loop on lines 3-6 is executed |<I>Adj</I>[<I>v</I>]<B>| times. Since</B><P>
<img src="479_b.gif"><P>
the total cost of executing lines 2-5 of DFS-<FONT FACE="Courier New" SIZE=2>VISIT</FONT> is <img src="../images/bound.gif">(<I>E</I>). The running time of DFS is therefore <img src="../images/bound.gif">(<I>V</I> + <I>E</I>).<P>





<h2>Properties of depth-first search</h2><P>
Depth-first search yields much information about the structure of a graph. Perhaps the most basic property of depth-first search is that the predecessor subgraph G<img src="../images/piuc.gif"><SUB> </SUB>does indeed form a forest of trees, since the structure of the depth-first trees exactly mirrors the structure of recursive calls of DFS-VISIT. That is, <I>u</I> = <img src="../images/piuc.gif">[<I>v</I>] if and only if DFS-VISIT (<I>v</I>) was called during a search of <I>u</I>'s adjacency list.<P>
Another important property of depth-first search is that discovery and finishing times have <I><B>parenthesis</I></B><I> <B>structure</I></B>. If we represent the discovery of vertex <I>u</I> with a left parenthesis &quot;(<I>u</I>&quot; and represent its finishing by a right parenthesis &quot;<I>u</I>),&quot; then the history of discoveries and finishings makes a well-formed expression in the sense that the parentheses are properly nested. For example, the depth-first search of Figure 23.5(a) corresponds to the parenthesization shown in Figure 23.5(b). Another way of stating the condition of parenthesis structure is given in the following theorem.<P>
<a name="08aa_1770">Theorem 23.6<a name="08aa_1770"><P>
<a name="08aa_176e">In any depth-first search of a (directed or undirected) graph <I>G</I> = (<I>V, E</I>), for any two vertices <I>u</I> and <I>v</I>, exactly one of the following three conditions holds:<P>
<FONT FACE="Courier New" SIZE=2><img src="../images/dot12.gif">     </FONT>the intervals [<I>d</I>[<I>u</I>], &acirc;[<I>u</I>]] and [<I>d</I>[<I>v</I>], &acirc;[<I>v</I>]] are entirely disjoint,<P>
<FONT FACE="Courier New" SIZE=2><img src="../images/dot12.gif">     </FONT>the interval [<I>d</I>[<I>u</I>], &acirc;[<I>u</I>]] is contained entirely within the interval [<I>d</I>[<I>v</I>], <FONT FACE="CG Times (W1)" SIZE=2>&acirc;</FONT>[<I>u</I>]], and <I>u</I> is a descendant of <I>v</I> in the depth-first tree, or<P>
<FONT FACE="Courier New" SIZE=2><img src="../images/dot12.gif">     </FONT>the interval [<I>d</I>[<I>v</I>], <FONT FACE="CG Times (W1)" SIZE=2>&acirc;</FONT>[<I>v</I>]] is contained entirely within the interval [<I>d</I>[<I>u</I>], <FONT FACE="CG Times (W1)" SIZE=2>&acirc;</FONT>[<I>u</I>]], and <I>v</I> is a descendant of <I>u</I> in the depth-first tree.<P>
<I><B>Proof     </I></B>We begin with the case in which <I>d</I>[<I>u</I>] &lt; <I>d</I>[<I>v</I>]. There are two subcases to consider, according to whether <I>d</I>[<I>v</I>] &lt; <I>&acirc;</I>[<I>u</I>] or not. In the first subcase, <I>d</I>[<I>v</I>] &lt; <I><FONT FACE="CG Times (W1)" SIZE=2>&acirc;</I></FONT>[<I>u</I>], so <I>v</I> was discovered while <I>u</I> was still gray. This implies that <I>v</I> is a descendant of <I>u</I>. Moreover, since <I>v</I> was discovered more recently than <I>u</I>, all of its outgoing edges are explored, and <I>v</I> is finished, before the search returns to and finishes <I>u</I>. In this case, therefore, the interval [<I>d</I>[<I>v</I>],&acirc;[<I>v</I>]] is entirely contained within the interval [<I>d</I>[<I>u</I>],<FONT FACE="CG Times (W1)" SIZE=2>&acirc;</FONT>[<I>u</I>]]. In the other subcase, &acirc;[<I>u</I>] &lt; <I>d</I>[<I>v</I>], and inequality (23.1) implies that the intervals [<I>d</I>[<I>u</I>],&acirc;[<I>u</I>]] and [<I>d</I>[<I>v</I>],<FONT FACE="CG Times (W1)" SIZE=2>&acirc;</FONT>[<I>v</I>]] are disjoint.<P>
The case in which <I>d</I>[<I>v</I>] &lt; <I>d</I>[<I>u</I>] is similar, with the roles of <I>u</I> and <I>v </I>reversed in the above argument.      <P>
<a name="08aa_1771">Corollary 23.7<a name="08aa_1771"><P>
Vertex <I>v</I> is a proper descendant of vertex <I>u</I> in the depth-first forest for a (directed or undirected) graph <I>G</I> if and only if <I>d</I>[<I>u</I>] &lt; <I>d</I>[<I>v</I>] &lt; &acirc;[<I>v</I>] &lt; <I>&acirc;</I>[<I>u</I>].<P>
<I><B>Proof</I></B>     Immediate from Theorem 23.6.      <P>
<img src="481_a.gif"><P>
<h4><a name="08aa_1772">Figure 23.5 Properties of depth-first search. (a) The result of a depth-first search of a directed graph. Vertices are timestamped and edge types are indicated as in Figure 23.4. (b) Intervals for the discovery time and finishing time of each vertex correspond to the parenthesization shown. Each rectangle spans the interval given by the discovery and finishing times of the corresponding vertex. Tree edges are shown. If two intervals overlap, then one is nested within the other, and the vertex corresponding to the smaller interval is a descendant of the vertex corresponding to the larger. (c) The graph of part (a) redrawn with all tree and forward edges going down within a depth-first tree and all back edges going up from a descendant to an ancestor.<a name="08aa_1772"></sub></sup></h4><P>
The next theorem gives another important characterization of when one vertex is a descendant of another in the depth-first forest.<P>
<a name="08aa_1773">Theorem 23.8<a name="08aa_1773"><P>
<a name="08aa_176f">In a depth-first forest of a (directed or undirected) graph <I>G</I> = (<I>V, E</I>), vertex <I>v</I> is a descendant of vertex <I>u</I> if and only if at the time <I>d</I>[<I>u</I>] that the search discovers <I>u</I>, vertex <I>v</I> can be reached from <I>u</I> along a path consisting entirely of white vertices.<P>
<I><B>Proof     </I></B><img src="../images/rtbigar.gif">: Assume that <I>v</I> is a descendant of <I>u</I>. Let <I>w</I> be any vertex on the path between <I>u</I> and <I>v</I> in the depth-first tree, so that <I>w</I> is a descendant of <I>u</I>. By Corollary 23.7, <I>d</I>[<I>u</I>] &lt; <I>d</I>[<I>w</I>], and so <I>w</I> is white at time <I>d</I>[<I>u</I>].<P>
<img src="../images/lftbigar.gif">: Suppose that vertex <I>v</I> is reachable from <I>u</I> along a path of white vertices at time <I>d</I>[<I>u</I>], but <I>v</I> does not become a descendant of <I>u</I> in the depth-first tree. Without loss of generality, assume that every other vertex along the path becomes a descendant of <I>u</I>. (Otherwise, let <I>v</I> be the closest vertex to <I>u</I> along the path that doesn't become a descendant of <I>u</I>.) Let <I>w </I>be the predecessor of <I>v</I> in the path, so that <I>w</I> is a descendant of <I>u</I> (<I>w</I> and <I>u </I>may in fact be the same vertex) and, by Corollary 23.7, &acirc;[<I>w</I>] <img src="../images/lteq12.gif"> <FONT FACE="CG Times (W1)" SIZE=2>&acirc;</FONT>[<I>u</I>]. Note that <I>v</I> must be discovered after <I>u</I> is discovered, but before <I>w</I> is finished. Therefore, <I>d</I>[<I>u</I>] &lt; <I>d</I>[<I>v</I>] &lt; &acirc;[<I>w</I>] &lt;<FONT FACE="CG Times (W1)" SIZE=2>&acirc;</FONT>[<I>u</I>]. Theorem 23.6 then implies that the interval [<I>d</I>[<I>v</I>], <FONT FACE="CG Times (W1)" SIZE=2>&acirc;</FONT>[<I>v</I>]] is contained entirely within the interval [<I>d</I>[<I>u</I>],<FONT FACE="CG Times (W1)" SIZE=2>&acirc;</FONT>[<I>u</I>]]. By Corollary 23.7, <I>v</I> must after all be a descendant of <I>u</I>.      <P>
<P>