chap23.htm

介绍算法的书籍

The main part of the proof is for vertices reachable from <I>s</I>. Let <I>V<SUB>k</I></SUB> denote the set of vertices at distance <I>k</I> from <I>s</I>; that is, <I>V<SUB>k</I></SUB> = {<I>v</I> <img src="../images/memof12.gif"> <I>V </I>: <img src="../images/delta12.gif">(<I>s</I>, <I>v</I>) = <I>k</I>}. The proof proceeds by induction on <I>k</I>. As an inductive hypothesis, we assume that for each vertex <I>v </I><img src="../images/memof12.gif"> <I>V<SUB>k</I></SUB>, there is exactly one point during the execution of BFS at which<P>
<img src="../images/dot12.gif">     <I>v</I> is grayed,<P>
<img src="../images/dot12.gif">     <I>d</I>[<I>v</I>] is set to <I>k</I>,<P>
<img src="../images/dot12.gif">     if <I>v</I> <img src="../images/noteq.gif"> <I>s</I>, then <img src="../images/piuc.gif">[<I>v</I>] is set to <I>u</I> for some <I>u</I> <img src="../images/memof12.gif"> <I>V<SUB>k</I> - 1</SUB>, and<P>
<img src="../images/dot12.gif">     <I>v</I> is inserted into the queue <I>Q</I>.<P>
As we have noted before, there is certainly at most one such point.<P>
The basis is for <I>k</I> = 0. We have <I>V</I><SUB>0</SUB> = {<I>s</I>}, since the source <I>s</I> is the only vertex at distance 0 from <I>s</I>. During the initialization, <I>s</I> is grayed, <I>d</I>[<I>s</I>] is set to 0, and <I>s</I> is placed into <I>Q</I>, so the inductive hypothesis holds.<P>
For the inductive step, we start by noting that the queue <I>Q</I> is never empty until the algorithm terminates and that, once a vertex <I>u</I> is inserted into the queue, neither <I>d</I>[<I>u</I>] nor <img src="../images/piuc.gif">[<I>u</I>] ever changes. By Lemma 23.3, therefore, if vertices are inserted into the queue over the course of the algorithm in the order <I>v</I><SUB>1</SUB>, <I>v</I><SUB>2, . . . , </SUB><I>v<SUB>r</I></SUB>, then the sequence of distances is monotonically increasing: <I>d</I>[<I>v<SUB>i</I></SUB>] <img src="../images/lteq12.gif"> <I>d</I>[<I>v<SUB>i + </I>1</SUB>] for <I>i</I> = 1, 2, . . . , <I>r</I> - 1.<P>
Now let us consider an arbitrary vertex <I>v </I><img src="../images/memof12.gif"><I> V<SUB>k</I></SUB>, where <I>k</I> <img src="../images/gteq.gif"> 1. The monotonicity property, combined with <I>d</I>[<I>v</I>] <img src="../images/gteq.gif"> <I>k</I> (by Lemma 23.2) and the inductive hypothesis, implies that <I>v</I> must be discovered after all vertices in <I>V<SUB>k </I>- 1</SUB> are enqueued, if it is discovered at all.<P>
Since <img src="../images/delta12.gif">(<I>s</I>, <I>v</I>) = <I>k</I>, there is a path of <I>k</I> edges from <I>s</I> to <I>v</I>, and thus there exists a vertex <I>u</I> <img src="../images/memof12.gif"> <I>V<SUB>k-</I>1</SUB> such that (<I>u</I>,<I>v</I>) <img src="../images/memof12.gif"><I> </I>E<I></I>. Without loss of generality, let <I>u</I> be the first such vertex grayed, which must happen since, by induction, all vertices in <I>V<SUB>k </I>- 1</SUB> are grayed. The code for BFS enqueues every grayed vertex, and hence <I>u</I> must ultimately appear as the head of the queue in line 10. When <I>u</I> appears as the head, its adjacency list is scanned and <I>v</I> is discovered. (The vertex <I>v</I> could not have been discovered earlier, since it is not adjacent to any vertex in <I>V<SUB>j</I></SUB> for <I>j</I> &lt; <I>k</I> - 1--otherwise, <I>v</I> could not belong to <I>V<SUB>k</SUB></I>--and by assumption, <I>u</I> is the first vertex discovered in <I>V<SUB>k -</I> 1</SUB> to which <I>v</I> is adjacent.) Line 13 grays <I>v</I>, line 14 establishes <I>d</I>[<I>v</I>] = <I>d</I>[<I>u</I>] + 1 = <I>k</I>, line 15 sets <img src="../images/piuc.gif">[<I>v</I>] to <I>u</I>, and line 16 inserts <I>v</I> into the queue. Since <I>v</I> is an arbitrary vertex in <I>V<SUB>k</I></SUB>, the inductive hypothesis is proved.<P>
To conclude the proof of the lemma, observe that if <I>v</I> <img src="../images/memof12.gif"> <I>V<SUB>k</I></SUB>, then by what we have just seen, <img src="../images/piuc.gif"><I>[</I>v<I>] <img src="../images/memof12.gif"> </I><I>V<SUB>k - </I>1</SUB>. Thus, we can obtain a shortest path from <I>s</I> to <I>v</I> by taking a shortest path from <I>s</I> to <img src="../images/piuc.gif"><I></I>[<I>v</I>] and then traversing the edge (<img src="../images/piuc.gif"><I></I>[<I>v</I>], <I>v</I>).      <P>
<P>







<h2>Breadth-first trees</h2><P>
<a name="08a7_1753"><a name="08a7_1754">The procedure BFS builds a breadth-first tree as it searches the graph, as illustrated in Figure 23.3. The tree is represented by the <img src="../images/piuc.gif"><I></I> field in each vertex. More formally, for a graph <I>G</I> = (<I>V, E</I>) with source <I>s</I>, we define the <I><B>predecessor subgraph</I></B> of <I>G</I> as <I>G</I><img src="../images/piuc.gif"> = (<I>V</I><SUB><FONT FACE="Courier New" SIZE=2></SUB><img src="../images/piuc.gif"></FONT><SUB>,<I></SUB> E</I><img src="../images/piuc.gif"><SUB></SUB>), where<P>
<pre><I>V</I><SUB></SUB><img src="../images/piuc.gif"><SUB> = {<I>v</I> <img src="../images/memof12.gif"> <I>V </I>: <img src="../images/piuc.gif">[<I>v</I>] <img src="../images/noteq.gif"> NIL} <img src="../images/wideu.gif"> {<I>s</I>}</sub></sup></pre><P>
and<P>
<pre><I>E</I><SUB></SUB><img src="../images/piuc.gif"><SUB> = {(<img src="../images/piuc.gif">[<I>v</I>],<I>v</I>) <img src="../images/memof12.gif"> <I>E</I> : <I>v</I> <img src="../images/memof12.gif"> <I>V</SUB></I><SUB><img src="../images/piuc.gif"> <I></SUB>- {</I>s<I>}} .</I></sub></sup></pre><P>
<a name="08a7_1755"><a name="08a7_1756"><a name="08a7_1757">The predecessor subgraph <I>G</I><img src="../images/piuc.gif"><SUB></SUB> is a <I><B>breadth-first tree</I></B> if <I>V</I><SUB><FONT FACE="Courier New" SIZE=2></SUB><img src="../images/piuc.gif"><SUB></FONT></SUB> consists of the vertices reachable from <I>s</I> and, for all <I>v</I> <img src="../images/memof12.gif"> <I>V</I><img src="../images/piuc.gif"><SUB></SUB>, there is a unique simple path from <I>s</I> to <I>v</I> in <I>G</I><SUB><FONT FACE="Courier New" SIZE=2></SUB><img src="../images/piuc.gif"></FONT><SUB></SUB> that is also a shortest path from <I>s</I> to <I>v</I> in <I>G</I>. A breadth-first tree is in fact a tree, since it is connected and |<I>E</I><img src="../images/piuc.gif"><SUB>| = |<I>V</I></SUB><FONT FACE="Courier New" SIZE=2><SUB><img src="../images/piuc.gif"></FONT></SUB>|<I> </I>- 1 (see Theorem 5.2). The edges in <I>E</I><img src="../images/pi14.gif"><SUB></SUB> are called <I><B>tree edges.</I></B><P>
After BFS has been run from a source <I>s</I> on a graph <I>G</I>, the following lemma shows that the predecessor subgraph is a breadth-first tree.<P>
<a name="08a7_1759">Lemma 23.5<a name="08a7_1759"><P>
When applied to a directed or undirected graph <I>G</I> = (<I>V, E</I>), procedure BFS constructs <img src="../images/piuc.gif"> so that the predecessor subgraph <I>G</I><img src="../images/piuc.gif"><I><SUB></SUB> = (</I>V<SUB><FONT FACE="Courier New" SIZE=2><I></SUB><img src="../images/piuc.gif"></I><SUB>,</SUB> E<I><img src="../images/piuc.gif"><SUB></I></FONT></SUB>) is a breadth-first tree.<P>
<I><B>Proof</I></B><I>     </I>Line 15 of BFS only sets <img src="../images/piuc.gif">[<I>v</I>] = <I>u</I> if (<I>u, v</I>) <img src="../images/memof12.gif"><I>E</I> and <img src="../images/delta12.gif">(<I>s, v</I>) &lt; <FONT FACE="Times New Roman" SIZE=3><img src="../images/infin.gif"></FONT>--that is, if <I>v</I> is reachable from <I>s</I>--and thus <I>V</I><img src="../images/piuc.gif"><I><SUB></SUB> </I>consists of the vertices in <I>V </I>reachable from <I>v</I>. Since <I>G<SUB><FONT FACE="Courier New" SIZE=2></I></SUB><img src="../images/piuc.gif"><SUB></SUB><I> </I></FONT>forms a tree, it contains a unique path from <I>s </I>to each vertex in <I>V</I><img src="../images/piuc.gif"><SUB></SUB>. By applying Theorem 23.4 inductively, we conclude that every such path is a shortest path.      <P>
The following procedure prints out the vertices on a shortest path from <I>s </I>to <I>v</I>, assuming that BFS has already been run to compute the shortest-path tree.<P>
<pre><a name="08a7_1758">PRINT-PATH(<I>G,s,v</I>)</sub></sup></pre><P>
<pre>1<B>  if</B> <I>v</I> = <I>s</I></sub></sup></pre><P>
<pre>2<B>     then</B> print <I>s</I></sub></sup></pre><P>
<pre>3<B>     else if</B> <img src="../images/piuc.gif">[<I>v</I>] = NIL</sub></sup></pre><P>
<pre>4<B>             then</B> print &quot;no path from&quot; <I>s</I> &quot;to&quot; <I>v</I> &quot;exists&quot;</sub></sup></pre><P>
<pre>5<B>             else</B> PRINT-PATH(<I>G,s,</I><img src="../images/piuc.gif">[<I>v</I>])</sub></sup></pre><P>
<pre>6                  print <I>v</I></sub></sup></pre><P>
This procedure runs in time linear in the number of vertices in the path printed, since each recursive call is for a path one vertex shorter.<P>
<P>







<h2><a name="08a8_175c">Exercises<a name="08a8_175c"></h2><P>
<a name="08a8_175d">23.2-1<a name="08a8_175d"><P>
Show the result of running breadth-first search on the directed graph of Figure 23.2(a), using vertex 3 as the source.<P>
<a name="08a8_175e">23.2-2<a name="08a8_175e"><P>
Show the result of running breadth-first search on the undirected graph of Figure 23.3, using vertex <I>u</I> as the source.<P>
<a name="08a8_175f">23.2-3<a name="08a8_175f"><P>
What is the running time of BFS if its input graph is represented by an adjacency matrix and the algorithm is modified to handle this form of input?<P>
<a name="08a8_1760">23.2-4<a name="08a8_1760"><P>
Argue that in a breadth-first search, the value <I>d</I>[<I>u</I>] assigned to a vertex <I>u </I>is independent of the order in which the vertices in each adjacency list are given.<P>
<a name="08a8_1761">23.2-5<a name="08a8_1761"><P>
Give an example of a directed graph <I>G</I> = (<I>V, E</I>), a source vertex <I>s</I> <img src="../images/memof12.gif"> <I>V, </I>and a set of tree edges <I>E</I><img src="../images/piuc.gif"><I><SUB></SUB> <img src="../images/rgtubar.gif"></I> <I>E</I> such that for each vertex <I>v</I> <img src="../images/memof12.gif"> <I>V</I>, the unique path in <I>E<SUB><FONT FACE="Courier New" SIZE=2></I></SUB><img src="../images/piuc.gif"><SUB></FONT><I></SUB></I> from <I>s</I> to <I>v</I> is a shortest path in <I>G</I>, yet the set of edges <I>E</I><img src="../images/piuc.gif"><I><SUB></SUB> </I>cannot be produced by running BFS on <I>G</I>, no matter how the vertices are ordered in each adjacency list.<P>
<a name="08a8_1762">23.2-6<a name="08a8_1762"><P>
<a name="08a8_1759">Give an efficient algorithm to determine if an undirected graph is bipartite.<P>
<a name="08a8_1763">23.2-7<a name="08a8_1763"><P>
<a name="08a8_175a"><a name="08a8_175b">The <I><B>diameter</I></B> of a tree <I>T</I> = (<I>V, E</I>) is given by<P>
<img src="476_a.gif"><P>
that is, the diameter is the largest of all shortest-path distances in the tree. Give an efficient algorithm to compute the diameter of a tree, and analyze the running time of your algorithm.<P>
<a name="08a8_1764">23.2-8<a name="08a8_1764"><P>
Let <I>G</I> = (<I>V, E</I>) be an undirected graph. Give an <I>O</I>(<I>V</I> + <I>E</I>)-time algorithm to compute a path in <I>G</I> that traverses each edge in <I>E</I> exactly once in each direction. Describe how you can find your way out of a maze if you are given a large supply of pennies.<P>
<P>


<P>