chap23.htm

介绍算法的书籍

<h2>Classification of edges</h2><P>
<a name="08ab_1770"><a name="08ab_1771">Another interesting property of depth-first search is that the search can be used to classify the edges of the input graph <I>G</I> = (<I>V, E</I>). This edge classification can be used to glean important information about a graph. For example, in the next section, we shall see that a directed graph is acyclic if and only if a depth-first search yields no &quot;back&quot; edges (Lemma 23.10).<P>
We can define four edge types in terms of the depth-first forest <I>G</I><img src="../images/piuc.gif"> <SUB></SUB>produced by a depth-first search on <I>G</I>.<P>
<a name="08ab_1772"><a name="08ab_1773">1.     <I><B>Tree edges</I></B> are edges in the depth-first forest <I>G</I><img src="../images/piuc.gif"><SUB></SUB>. <B>Edge</B> (<I>u, v</I>) is a tree edge if <I>v</I> was first discovered by exploring edge (<I>u, v</I>).<P>
<a name="08ab_1774"><a name="08ab_1775">2.     <I><B>Back edges</I></B> are those edges (<I>u, v</I>) connecting a vertex <I>u</I> to an ancestor <I>v </I>in a depth-first tree. Self-loops are considered to be back edges.<P>
<a name="08ab_1776"><a name="08ab_1777">3.     <I><B>Forward edges</I></B> are those nontree edges (<I>u, v</I>) connecting a vertex <I>u</I> to a descendant <I>v</I> in a depth-first tree.<P>
<a name="08ab_1778"><a name="08ab_1779">4.     <I><B>Cross edges</I></B> are all other edges. They can go between vertices in the same depth-first tree, as long as one vertex is not an ancestor of the other, or they can go between vertices in different depth-first trees.<P>
In Figures 23.4 and 23.5, edges are labeled to indicate their type. Figure 23.5(c) also shows how the graph of Figure 23.5(a) can be redrawn so that all tree and forward edges head downward in a depth-first tree and all back edges go up. Any graph can be redrawn in this fashion.<P>
The DFS algorithm can be modified to classify edges as it encounters them. The key idea is that each edge (<I>u, v</I>) can be classified by the color of the vertex <I>v</I> that is reached when the edge is first explored (except that forward and cross edges are not distinguished):<P>
1.     <FONT FACE="Courier New" SIZE=2>WHITE</FONT> indicates a tree edge,<P>
2.     <FONT FACE="Courier New" SIZE=2>GRAY </FONT>indicates a back edge, and<P>
3.     <FONT FACE="Courier New" SIZE=2>BLACK</FONT> indicates a forward or cross edge.<P>
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 the stack of active DFS-<FONT FACE="Courier New" SIZE=2>VISIT</FONT> invocations; the number of gray vertices is one more than the depth in the depth-first forest of the vertex most recently discovered. Exploration always proceeds from the deepest gray vertex, so an edge that reaches another gray vertex reaches an ancestor. The third case handles the remaining possibility; it can be shown that such an edge (<I>u, v</I>) is a forward edge if <I>d</I>[<I>u</I>]<I> &lt; d</I>[<I>v</I>] and a cross edge if <I>d</I>[<I>u</I>] <I>&gt; d</I>[<I>v</I>]. (See Exercise 23.3-4.)<P>
In an undirected graph, there may be some ambiguity in the type classification, since (<I>u, v</I>) and (<I>v, u</I>) are really the same edge. In such a case, the edge is classified as the<I> first</I> type in the classification list that applies. Equivalently (see Exercise 23.3-5), the edge is classified according to whichever of (<I>u, v</I>) or (<I>v, u</I>) is encountered first during the execution of the algorithm.<P>
We now show that forward and cross edges never occur in a depth-first search of an undirected graph.<P>
<a name="08ab_177a">Theorem 23.9<a name="08ab_177a"><P>
In a depth-first search of an undirected graph <I>G,</I> every edge of <I>G</I> is either a tree edge or a back edge.<P>
<I><B>Proof</I></B>     Let (<I>u, v</I>) be an arbitrary edge of <I>G,</I> and suppose without loss of generality that <I>d</I>[<I>u</I>]<I> &lt; d</I>[<I>v</I>]. Then, <I>v</I> must be discovered and finished before we finish <I>u,</I> since <I>v</I> is on <I>u</I>'s adjacency list. If the edge (<I>u, v</I>) is explored first in the direction from <I>u</I> to <I>v,</I> then (<I>u, v</I>) becomes a tree edge. If (<I>u, v</I>) is explored first in the direction from <I>v</I> to <I>u,</I> then (<I>u, v</I>) is a back edge, since <I>u</I> is still gray at the time the edge is first explored.      <P>
We shall see many applications of these theorems in the following sections.<P>
<P>







<h2><a name="08ac_177f">Exercises<a name="08ac_177f"></h2><P>
<a name="08ac_1780">23.3-1<a name="08ac_1780"><P>
Make a 3-by-3 chart with row and column labels <FONT FACE="Courier New" SIZE=2>WHITE, GRAY,</FONT> and <FONT FACE="Courier New" SIZE=2>BLACK</FONT>. In each cell (<I>i, j</I>)<I>,</I> indicate whether, at any point during a depth-first search of a directed graph, there can be an edge from a vertex of color <I>i</I> to a vertex of color <I>j</I>. For each possible edge, indicate what edge types it can be. Make a second such chart for depth-first search of an undirected graph.<P>
<img src="484_a.gif"><P>
<h4><a name="08ac_1781">Figure 23.6 A directed graph for use in Exercises 23.3-2 and 23.5-2.<a name="08ac_1781"></sub></sup></h4><P>
<a name="08ac_1782">23.3-2<a name="08ac_1782"><P>
<a name="08ac_177a">Show how depth-first search works on the graph of Figure 23.6. Assume that the <B>for</B> loop of lines 5-7 of the DFS procedure considers the vertices in alphabetical order, and assume that each adjacency list is ordered alphabetically. Show the discovery and finishing times for each vertex, and show the classification of each edge.<P>
<a name="08ac_1783">23.3-3<a name="08ac_1783"><P>
Show the parenthesis structure of the depth-first search shown in Figure 23.4.<P>
<a name="08ac_1784">23.3-4<a name="08ac_1784"><P>
Show that edge (<I>u,v</I>) is<P>
<I><B>a.     </I></B>a tree edge or forward edge if and only if <I>d</I>[<I>u</I>] &lt; <I>d</I>[<I>v</I>] &lt; <I>f</I>[<I>v</I>] &lt; <I>f</I>[<I>u</I>],<P>
<I><B>b.     </I></B>a back edge if and only if <I>d</I>[<I>v</I>] &lt; <I>d</I>[<I>u</I>] &lt; <I>f</I>[<I>u</I>] &lt; <I>f</I>[<I>v</I>], and<P>
<I><B>c.     </I></B>a cross edge if and only if <I>d</I>[<I>v</I>] &lt;<I> f</I>[<I>v</I>] &lt; <I>d</I>[<I>u</I>] &lt; <I>f</I>[<I>u</I>].<P>
<a name="08ac_1785">23.3-5<a name="08ac_1785"><P>
<a name="08ac_177b">Show that in an undirected graph, classifying an edge (<I>u, v</I>) as a tree edge or a back edge according to whether (<I>u,v</I>) or (<I>v,u</I>) is encountered first during the depth-first search is equivalent to classifying it according to the priority of types in the classification scheme.<P>
<a name="08ac_1786">23.3-6<a name="08ac_1786"><P>
Give a counterexample to the conjecture that if there is a path from <I>u to v </I>in a directed graph <I>G,</I> and if <I>d</I>[<I>u</I>]<I> &lt; d</I>[<I>v</I>] in a depth-first search of <I>G,</I> then <I>v</I> is a descendant of <I>u</I> in the depth-first forest produced.<P>
<a name="08ac_1787">23.3-7<a name="08ac_1787"><P>
Modify the pseudocode for depth-first search so that it prints out every edge in the directed graph <I>G,</I> together with its type. Show what modifications, if any, must be made if <I>G</I> is undirected.<P>
<a name="08ac_1788">23.3-8<a name="08ac_1788"><P>
Explain how a vertex <I>u</I> of a directed graph can end up in a depth-first tree containing only <I>u,</I> even though <I>u</I> has both incoming and outgoing edges in <I>G.</I><P>
<a name="08ac_1789">23.3-9<a name="08ac_1789"><P>
<a name="08ac_177c">Show that a depth-first search of an undirected graph <I>G</I> can be used to identify the connected components of <I>G,</I> and that the depth-first forest contains as many trees as <I>G </I>has connected components. More precisely, show how to modify depth-first search so that each vertex<I> v</I> is assigned an integer label <I>cc</I>[<I>v</I>] between 1 and <I>k,</I> where <I>k</I> is the number of connected components of <I>G,</I> such that <I>cc</I>[<I>u</I>]<I> = cc</I>[<I>v</I>] if and only if <I>u</I> and <I>v</I> are in the same connected component.<P>
<a name="08ac_178a">23.3-10<a name="08ac_178a"><P>
<a name="08ac_177d"><a name="08ac_177e">A directed graph <I>G = </I>(<I>V, E</I>) is <I><B>singly connected</I></B> if <img src="485_a.gif"> implies that there is at most one simple path from <I>u</I> to <I>v</I> for all vertices <I>u, v </I><img src="../images/memof12.gif"><I> V.</I> Give an efficient algorithm to determine whether or not a directed graph is singly connected.<P>
<P>


<P>







<h1><a name="08ad_1787">23.4 Topological sort<a name="08ad_1787"></h1><P>
<a name="08ad_177f"><a name="08ad_1780"><a name="08ad_1781"><a name="08ad_1782">This section shows how depth-first search can be used to perform topological sorts of directed acyclic graphs, or &quot;dags&quot; as they are sometimes