chap23.htm

程序设计的艺术,此书是英文版的,经久不衰,非常的经典

Breadth-first search is so named because it expands the frontier between discovered and undiscovered vertices uniformly across the breadth of the frontier. That is, the algorithm discovers all vertices at distance <I>k</I> from <I>s</I> before discovering any vertices at distance <I>k</I> + 1.<P>
<a name="08a4_1745"><a name="08a4_1746"><a name="08a4_1747"><a name="08a4_1748">To keep track of progress, breadth-first search colors each vertex white, gray, or black. All vertices start out white and may later become gray and then black. A vertex is <I><B>discovered</I></B> the first time it is encountered during the search, at which time it becomes nonwhite. Gray and black vertices, therefore, have been discovered, but breadth-first search distinguishes between them to ensure that the search proceeds in a breadth-first manner. If (<I>u</I>, <I>v</I>) <img src="../images/memof12.gif"> <I>E</I> and vertex <I>u</I> is black, then vertex <I>v</I> is either gray or black; that is, all vertices adjacent to black vertices have been discovered. Gray vertices may have some adjacent white vertices; they represent the frontier between discovered and undiscovered vertices.<P>
<a name="08a4_1749"><a name="08a4_174a">Breadth-first search constructs a breadth-first tree, initially containing only its root, which is the source vertex <I>s</I>. Whenever a white vertex <I>v</I> is discovered in the course of scanning the adjacency list of an already discovered vertex <I>u</I>, the vertex <I>v</I> and the edge (<I>u</I>,<I>v</I>) are added to the tree. We say that <I>u</I> is the <I><B>predecessor</I></B> or <I><B>parent</I></B> of <I>v</I> in the breadth-first tree. Since a vertex is discovered at most once, it has at most one parent. Ancestor and descendant relationships in the breadth-first tree are defined relative to the root <I>s</I> as usual: if <I>u</I> is on a path in the tree from the root <I>s </I>to vertex <I>v</I>, then <I>u</I> is an ancestor of <I>v</I> and <I>v</I> is a descendant of <I>u.</I><P>
<a name="08a4_174b">The breadth-first-search procedure BFS below assumes that the input graph<I> G</I> = (<I>V, E</I>) is represented using adjacency lists. It maintains several additional data structures with each vertex in the graph. The color of each vertex <I>u</I> <img src="../images/memof12.gif"> <I>V</I> is stored in the variable <I>color</I>[<I>u</I>], and the predecessor of <I>u</I> is stored in the variable <img src="../images/piuc.gif">[<I>u</I>]. If <I>u</I> has no predecessor (for example, if <I>u</I> = <I>s</I> or <I>u</I> has not been discovered), then <img src="../images/piuc.gif">[<I>u</I>] = <FONT FACE="Courier New" SIZE=2>NIL</FONT>. The distance from the source s to vertex <I>u</I> computed by the algorithm is stored in <I>d</I>[<I>u</I>]<I>.</I> The algorithm also uses a first-in, first-out queue <I>Q</I> (see Section 11.1) to manage the set of gray vertices.<P>
<pre><a name="08a4_174c"><B>BFS</B>(<I>G,s</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>] - {<I>s</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          <I>d</I>[<I>u</I>] <img src="../images/arrlt12.gif"> <img src="../images/infin.gif"></sub></sup></pre><P>
<pre>4          <img src="../images/piuc.gif">[<I>u</I>] <img src="../images/arrlt12.gif"> NIL</sub></sup></pre><P>
<pre>5  <I>color</I>[<I>s</I>] <img src="../images/arrlt12.gif"> GRAY</sub></sup></pre><P>
<pre>6  <I>d</I>[<I>s</I>] <img src="../images/arrlt12.gif"> 0</sub></sup></pre><P>
<pre>7  <img src="../images/piuc.gif">[<I>s</I>] <img src="../images/arrlt12.gif"> NIL</sub></sup></pre><P>
<pre>8  <I>Q</I> <img src="../images/arrlt12.gif"> {<I>s</I>}</sub></sup></pre><P>
<pre>9  <B>while</B> <I>Q</I> <img src="../images/noteq.gif"> <img src="470_a.gif"></sub></sup></pre><P>
<pre>10      <B>do</B> <I>u</I> <img src="../images/arrlt12.gif"> <I>head</I>[<I>Q</I>]</sub></sup></pre><P>
<pre>11         <B>for</B> each <I>v</I> <img src="../images/memof12.gif"><B> </B><I>Adj</I>[<I>u</I>]</sub></sup></pre><P>
<pre>12             <B>do if</B> <I>color</I>[<I>v</I>] = WHITE</sub></sup></pre><P>
<pre>13                   <B>then</B> <I>color</I>[<I>v</I>] <img src="../images/arrlt12.gif"> GRAY</sub></sup></pre><P>
<pre>14                        <I>d</I>[<I>v</I>] <img src="../images/arrlt12.gif"> <I>d</I>[<I>u</I>] + 1</sub></sup></pre><P>
<pre>15                        <img src="../images/piuc.gif">[<I>v</I>] <img src="../images/arrlt12.gif"> <I>u</I></sub></sup></pre><P>
<pre>16                        ENQUEUE(<I>Q,v</I>)</sub></sup></pre><P>
<pre>17         DEQUEUE(<I>Q</I>)</sub></sup></pre><P>
<pre>18         <I>color</I>[<I>u</I>] <img src="../images/arrlt12.gif"> BLACK</sub></sup></pre><P>
Figure 23.3 illustrates the progress of BFS on a sample graph.<P>
The procedure BFS works as follows. Lines 1-4 paint every vertex white, set <I>d</I> [<I>u</I>] to be infinity for every vertex <I>u</I>, and set the parent of every vertex to be <FONT FACE="Courier New" SIZE=2>NIL</FONT>. Line 5 paints the source vertex <I>s</I> gray, since it is considered to be discovered when the procedure begins. Line 6 initializes <I>d</I>[<I>s</I>] to 0, and line 7 sets the predecessor of the source to be <FONT FACE="Courier New" SIZE=2>NIL</FONT>. Line 8 initializes <I>Q</I> to the queue containing just the vertex <I>s</I>; thereafter, <I>Q</I> always contains the set of gray vertices.<P>
The main loop of the program is contained in lines 9-18. The loop iterates as long as there remain gray vertices, which are discovered vertices that have not yet had their adjacency lists fully examined. Line 10 determines the gray vertex <I>u</I> at the head of the queue <I>Q</I>. The <B>for</B> loop of lines 11-16 considers each vertex <I>v</I> in the adjacency list of <I>u</I>. If <I>v</I> is white, then it has not yet been discovered, and the algorithm discovers it by executing lines 13-16. It is first grayed, and its distance <I>d</I>[<I>v</I>] is set to <I>d</I>[<I>u</I>] + 1. Then, <I>u</I> is recorded as its parent. Finally, it is placed at the tail of the queue <I>Q</I>. When all the vertices on <I>u</I>'s adjacency list have been examined, <I>u</I> is removed from <I>Q</I> and blackened in lines 17-18.<P>
<img src="471_a.gif"><P>
<h4><a name="08a4_174e">Figure 23.3 The operation of BFS on an undirected graph. Tree edges are shown shaded as they are produced by BFS. Within each vertex u is shown d[u]. The queue Q is shown at the beginning of each iteration of the while loop of lines 9-18. Vertex distances are shown next to vertices in the queue.<a name="08a4_174e"></sub></sup></h4><P>





<h2>Analysis</h2><P>
Before proving all the various properties of breadth-first search, we take on the somewhat easier job of analyzing its running time on an input graph <I>G</I> = (<I>V,E</I>). After initialization, no vertex is ever whitened, and thus the test in line 12 ensures that each vertex is enqueued at most once, and hence dequeued at most once. The operations of enqueuing and dequeuing take <I>O</I>(1) time, so the total time devoted to queue operations is <I>O</I>(<I>V</I>). Because the adjacency list of each vertex is scanned only when the vertex is dequeued, the adjacency list of each vertex is scanned at most once. Since the sum of the lengths of all the adjacency lists is <img src="../images/bound.gif">(<I>E</I>), at most <I>O</I>(<I>E</I>) time is spent in total scanning adjacency lists. The overhead for initialization is <I>O</I>(<I>V</I>), and thus the total running time of <B>BFS</B> is <I>O</I>(<I>V</I> + <I>E</I>). Thus, breadth-first search runs in time linear in the size of the adjacency- list representation of <I>G</I>.<P>
<P>







<h2>Shortest paths</h2><P>
<a name="08a6_174d"><a name="08a6_174e"><a name="08a6_174f"><a name="08a6_1750"><a name="08a6_1751"><a name="08a6_1752">At the beginning of this section, we claimed that breadth-first search finds the distance to each reachable vertex in a graph <I>G</I> = (<I>V,E</I>) from a given source vertex <I>s</I> <img src="../images/memof12.gif"> <I>V</I>. Define the <I><B>shortest-path distance</I></B> <img src="../images/delta12.gif"> (<I>s,v</I>) from s to <I>v</I> as the minimum number of edges in any path from vertex <I>s</I> to vertex <I>v</I>, or else <img src="../images/infin.gif"> if there is no path from <I>s</I> to <I>v</I>. A path of length <img src="../images/delta12.gif"> (<I>s</I>,<I>v</I>) from <I>s</I> to <I>v</I> is said to be a <I><B>shortest path</I></B><SUP>1</SUP> from <I>s</I> to <I>v</I>. Before showing that breadth-first search actually computes shortest-path distances, we investigate an important property of shortest-path distances.<P>
<SUP>1</SUP> In Chapters 25 and 26, we shall generalize our study of shortest paths to weighted graphs, in which every edge has a real-valued weight and the weight of a path is the sum of the weights of its constituent edges. The graphs considered in the present chapter are unweighted.<P>
<a name="08a6_1753">Lemma 23.1<a name="08a6_1753"><P>
Let <I>G</I> = (<I>V,E</I>) be a directed or undirected graph, and let <I>s </I><img src="../images/memof12.gif"> <I>V</I> be an arbitrary vertex. Then, for any edge (<I>u</I>, <I>v</I>) <img src="../images/memof12.gif"> <I>E</I>,<P>
<pre><img src="../images/delta12.gif">(<I>s</I>,<I>v</I>)<I> </I><img src="../images/lteq12.gif"> <img src="../images/delta12.gif">(<I>s</I>,<I>u</I>) + 1 .</sub></sup></pre><P>
<I><B>Proof     </I></B>If <I>u</I> is reachable from <I>s</I>, then so is <I>v</I>. In this case, the shortest path from <I>s</I> to <I>v</I> cannot be longer than the shortest path from <I>s</I> to <I>v</I> followed by the edge (<I>u</I>, <I>v</I>), and thus the inequality holds. If <I>u</I> is not reachable from <I>s</I>, then <img src="../images/delta12.gif"> (<I>s,u</I>) = <img src="../images/infin.gif">, and the inequality holds.      <P>
We want to show that BFS properly computes <I>d</I>[<I>v</I>] = <img src="../images/delta12.gif"><I></I> (<I>s</I>, <I>v</I>) for each vertex <I>v</I> <img src="../images/memof12.gif"> <I>V</I>. We first show that <I>d </I>[<I>v</I>] bounds <img src="../images/delta12.gif"><I> (</I>s<I>, </I>v<I>) from above.</I><P>
<a name="08a6_1754">Lemma 23.2<a name="08a6_1754"><P>
Let <I>G</I> = (<I>V</I>,<I>E</I>) be a directed or undirected graph, and suppose that BFS is run on <I>G</I> from a given source vertex <I>s</I> <img src="../images/memof12.gif"> <I>V</I>. Then upon termination, for each vertex <I>v</I> <img src="../images/memof12.gif"> <I>V</I>, the value <I>d</I>[<I>v</I>] computed by BFS satisfies <I>d</I>[<I>v</I>] <img src="../images/gteq.gif"> <img src="../images/delta12.gif"><I>(s, </I>v<I>).</I><P>
<I><B>Proof     </I></B>We use induction on the number of times a vertex is placed in the queue <I>Q</I>. Our inductive hypothesis is that <I>d</I>[<I>v</I>] <img src="../images/gteq.gif"> <img src="../images/delta12.gif"><I></I> (<I>s</I>,<I>v</I>) for all <I>v</I> <img src="../images/memof12.gif"> <I>V</I>.<P>
The basis of the induction is the situation immediately after <I>s</I> is placed in <I>Q</I> in line 8 of BFS. The inductive hypothesis holds here, because <I>d</I>[<I>s</I>] = 0 = <img src="../images/delta12.gif"><I>(</I>s<I>, </I>s<I>) and </I>d<I>[</I>v<I>] = <FONT FACE="Times New Roman" SIZE=3><img src="../images/infin.gif"></FONT> <img src="../images/gteq.gif"> <img src="../images/delta12.gif"></I>(<I>s</I>, <I>v</I>) for all <I>v </I><img src="../images/memof12.gif"><I> </I>V<I> - {</I>s<I>}.</I><P>
For the inductive step, consider a white vertex <I>v</I> that is discovered during the search from a vertex <I>u</I>. The inductive hypothesis implies that <I>d</I>[<I>u</I>] <img src="../images/gteq.gif"> <img src="../images/delta12.gif"><I></I>(<I>s</I>, <I>u</I>). From the assignment performed by line 14 and from Lemma 23.1, we obtain<P>
<pre><I>d</I>[<I>v</I>]  =  <I>d</I>[<I>u</I>] + 1</sub></sup></pre><P>
<pre><img src="../images/gteq.gif">  <img src="../images/delta12.gif">(<I>s</I>,<I>u</I>) + 1</sub></sup></pre><P>
<pre><img src="../images/gteq.gif">  <img src="../images/delta12.gif">(<I>s</I>,<I>v</I>) .</sub></sup></pre><P>
Vertex <I>v</I> is then inserted into the queue <I>Q</I>, and it is never inserted again because it is also grayed and the <B>then</B> clause of lines 13-16 is executed only for white vertices. Thus, the value of <I>d</I>[<I>v</I>] never changes again, and the inductive hypothesis is maintained.      <P>
To prove that <I>d</I>[<I>v</I>] = <img src="../images/delta12.gif">(<I>s</I>, <I>v</I>), we must first show more precisely how the queue <I>Q</I> operates during the course of BFS. The next lemma shows that at all times, there are at most two distinct <I>d</I> values in the queue.<P>
<a name="08a6_1755">Lemma 23.3<a name="08a6_1755"><P>
Suppose that during the execution of BFS on a graph <I>G</I> = (<I>V</I>, <I>E</I>), the queue <I>Q</I> contains the vertices <img src="../images/lftwdchv.gif"><I>v</I><SUB>1</SUB>, <I>v</I><SUB>2</SUB>, . . . , <I>v</I><SUB>r</SUB><img src="../images/wdrtchv.gif">, where <I>v</I><SUB>1</SUB> is the head of <I>Q </I>and <I>v<SUB>r</I></SUB> is the tail. Then, <I>d</I>[<I>v<SUB>r</I></SUB>] <img src="../images/lteq12.gif"> <I>d</I>[<I>v</I><SUB>1</SUB>] + 1 and <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>
<I><B>Proof     </I></B>The proof is by induction on the number of queue operations. Initially, when the queue contains only <I>s</I>, the lemma certainly holds.<P>
For the inductive step, we must prove the lemma holds after both dequeuing and enqueuing a vertex. If the head <I>v</I><SUB>1</SUB> of the queue is dequeued, the new head is <I>v</I><SUB>2</SUB>. (If the queue becomes empty, then the lemma holds vacuously.) But then we have <I>d</I>[<I>v<SUB>r</I></SUB>]<SUB> </SUB><img src="../images/lteq12.gif"> <I>d</I>[<I>v</I><SUB>1</SUB>] + 1 <img src="../images/lteq12.gif"> <I>d</I>[<I>v</I><SUB>2</SUB>] + 1, and the remaining inequalities are unaffected. Thus, the lemma follows with <I>v</I><SUB>2</SUB> as the head. Enqueuing a vertex requires closer examination of the code. In line 16 of BFS, when the vertex <I>v</I> is enqueued, thus becoming <I>v</I>r+1, the head <I>v</I><SUB>1</SUB> of <I>Q</I> is in fact the vertex <I>u</I> whose adjacency list is currently being scanned. Thus, <I>d</I>[<I>v<SUB>r</I></SUB>+1] = <I>d</I>[<I>v</I>] = <I>d</I>[<I>u</I>] + 1 = <I>d</I>[<I>v</I><SUB>1</SUB>] + 1. We also have <I>d</I>[<I>v<SUB>r</I></SUB>] <img src="../images/lteq12.gif"> <I>d</I>[<I>v</I><SUB>1</SUB>] + 1 = <I>d</I>[<I>u</I>] + 1 = <I>d</I>[<I>v</I>] = <I>d</I>[<I>v<SUB>r </I>+ 1</SUB>], and the remaining inequalities are unaffected. Thus, the lemma follows when <I>v </I>is enqueued.      <P>
We can now prove that breadth-first search correctly finds shortest-path distances.<P>
<a name="08a6_1756">Theorem 23.4<a name="08a6_1756"><P>
Let <I>G</I> = (<I>V</I>, <I>E</I>) be a directed or undirected graph, and suppose that BFS is run on <I>G</I> from a given source vertex <I>s</I> <img src="../images/memof12.gif"> <I>V</I>. Then, during its execution, BFS discovers every vertex <I>v</I> <img src="../images/memof12.gif"> <I>V</I> that is reachable from the source <I>s</I>, and upon termination, <I>d</I>[<I>v</I>] = <img src="../images/delta12.gif"><I></I>(<I>s</I>, <I>v</I>) for all <I>v</I> <img src="../images/memof12.gif"> <I>V</I>. Moreover, for any vertex <I>v</I> <img src="../images/noteq.gif"> <I>s</I> that is reachable from <I>s</I>, one of the shortest paths from <I>s</I> to <I>v</I> is the shortest path from <I>s</I> to <img src="../images/piuc.gif">[<I>v</I>] followed by the edge (<img src="../images/piuc.gif"><I>[</I>v<I>], </I>v<I>).</I><P>
<I><B>Proof     </I></B>We start with the case in which <I>v</I> is unreachable from <I>s</I>. Since Lemma 23.2 gives <I>d</I>[<I>v</I>] <img src="../images/gteq.gif"> <img src="../images/delta12.gif"><I></I>(<I>s</I>, <I>v</I>) = <img src="../images/infin.gif">, vertex <I>v </I>cannot have <I>d</I>[<I>v</I>] set to a finite value in line 14. By induction, there cannot be a first vertex whose <I>d</I> value is set to <img src="../images/infin.gif"> by line 14. Line 14 is therefore only executed only for vertices with finite <I>d</I> values. Thus, if <I>v</I> is unreachable, it is never discovered.<P>