chap24.htm

美国麻省理工的算法导论,英文版,看后程序员宏观的能力培养有好处

<P>







<h1><a name="08b7_0001">24.2 The algorithms of Kruskal and Prim<a name="08b7_0001"></h1><P>
The two minimum-spanning-tree algorithms described in this section are elaborations of the generic algorithm. They each use a specific rule to determine a safe edge in line 3 of <FONT FACE="Courier New" SIZE=2>GENERIC</FONT>-MST. In Kruskal's algorithm, the set <I>A</I> is a forest. The safe edge added to <I>A</I> is always a least-weight edge in the graph that connects two distinct components. In Prim's algorithm, the set <I>A</I> forms a single tree. The safe edge added to <I>A</I> is always a least-weighted edge connecting the tree to a vertex not in the tree.<P>





<h2>Kruskal's Al gorithm</h2><P>
<a name="08b8_17ac"><a name="08b8_17ad"><a name="08b8_17ae"><a name="08b8_17af">Kruskal's algorithm is based directly on the generic minimum-spanning-tree algorithm given in Section 24.1. It finds a safe edge to add to the growing forest by finding, of all the edges that connect any two trees in the  forest, an edge (<I>u</I>, <I>v</I>) of least weight. Let <I>C</I><SUB>1</SUB> and <I>C</I><SUB>2</SUB> denote the two trees that are connected by (<I>u</I>, <I>v</I>). Since (<I>u</I>,<I>v</I>) must be a light edge connecting <I>C</I><SUB>1</SUB> to some other tree, Corollary 24.2 implies that (<I>u</I>, <I>v</I>) is a safe edge for <I>C</I><SUB>1</SUB>. Kruskal's algorithm is a greedy algorithm, because at each step it adds to the forest an edge of least possible weight.<P>
Our implementation of Kruskal's algorithm is like the algorithm to compute connected components from Section 22.1. It uses a disjoint-set data structure to maintain several disjoint sets of elements. Each set contains the vertices in a tree of the current forest. The operation <FONT FACE="Courier New" SIZE=2>FIND</FONT>-<FONT FACE="Courier New" SIZE=2>SET</FONT>(<I>u</I>) returns a representative element from the set that contains <I>u</I>. Thus, we can determine whether two vertices <I>u</I> and <I>v</I> belong to the same tree by testing whether <FONT FACE="Courier New" SIZE=2>FIND</FONT>-<FONT FACE="Courier New" SIZE=2>SET</FONT>(<I>u</I>) equals <FONT FACE="Courier New" SIZE=2>FIND</FONT>-<FONT FACE="Courier New" SIZE=2>SET</FONT>(<I>v</I>). The combining of trees is accomplished by the <FONT FACE="Courier New" SIZE=2>UNION</FONT> procedure.<P>
<pre><a name="08b8_17b0">MST-KRUSKAL(<I>G</I>, <I>w</I>)</sub></sup></pre><P>
<pre>1  <I>A</I> <img src="../images/arrlt12.gif"> <img src="505_a.gif"></sub></sup></pre><P>
<pre>2  <B>for</B> each vertex <I>v</I> <img src="../images/memof12.gif"> <I>V</I>[<I>G</I>]</sub></sup></pre><P>
<pre>3      <B>do</B> MAKE-SET (<I>v</I>)</sub></sup></pre><P>
<pre>4  sort the edges of <I>E</I> by nondecreasing weight <I>w</I></sub></sup></pre><P>
<pre>5  <B>for</B> each edge (<I>u</I>, <I>v</I>) <img src="../images/memof12.gif"> <I>E</I>, in order by nondecreasing weight</sub></sup></pre><P>
<pre>6      <B>do</B> if FIND-SET(<I>u</I>) <img src="../images/noteq.gif"> FIND-SET(<I>v</I>)</sub></sup></pre><P>
<pre>7            <B>then</B> <I>A</I> <img src="../images/arrlt12.gif"> <I>A</I> <img src="../images/wideu.gif"> {(<I>u</I>, <I>v</I>)}</sub></sup></pre><P>
<pre>8                 UNION (<I>u</I>, <I>v</I>)</sub></sup></pre><P>
<pre>9  <B>return</B> <I>A</I></sub></sup></pre><P>
Kruskal's algorithm works as shown in Figure 24.4. Lines 1-3 initialize the set <I>A</I> to the empty set and create |<I>V</I>| trees, one containing each vertex. The edges in <I>E</I> are sorted into order by nondecreasing weight in line 4. The <B>for</B> loop in lines 5-8 checks, for each edge (<I>u</I>, <I>v</I>), whether the endpoints <I>u </I>and <I>v</I> belong to the same tree. If they do, then the edge (<I>u</I>, <I>v</I>) cannot be added to the forest without creating a cycle, and the edge is discarded. Otherwise, the two vertices belong to different trees, and the edge (<I>u</I>, <I>v</I>) is added to <I>A</I> in line 7, and the vertices in the two trees are merged in line 8.<P>
The running time of Kruskal's algorithm for a graph <I>G</I> = (<I>V</I>, <I>E</I>) depends on the implementation of the disjoint-set data structure. We shall assume the disjoint-set-forest implementation of Section 22.3 with the union-by-rank and path-compression heuristics, since it is the asymptotically fastest implementation known. Initialization takes time <I>O</I>(<I>V</I>), and the time to sort the edges in line 4 is <I>O</I>(<I>E</I> lg <I>E</I>). There are <I>O</I>(<I>E</I>) operations on the disjoint-set forest, which in total take <I>O</I>(<I>E</I> <img src="../images/alpha12.gif"> (<I>E</I>, <I>V</I>)) time, where <img src="../images/alpha12.gif"> is the functional inverse of Ackermann's function defined in Section 22.4. Since <img src="../images/alpha12.gif">(<I>E</I>, <I>V</I>) = <I>O</I>(lg <I>E</I>), the total running time of Kruskal's algorithm is <I>O</I>(<I>E</I> lg <I>E</I>).<P>
<P>







<h2>Prim's algorithm</h2><P>
<a name="08b9_17b1"><a name="08b9_17b2"><a name="08b9_17b3"><a name="08b9_17b4"><a name="08b9_17b5">Like Kruskal's algorithm, Prim<FONT FACE="CG Times (W1)" SIZE=2>'</FONT>s algorithm is a special case of the generic minimum-spanning-tree algorithm from Section 24.1. Prim<FONT FACE="CG Times (W1)" SIZE=2>'</FONT>s algorithm operates much like Dijkstra<FONT FACE="CG Times (W1)" SIZE=2>'</FONT>s algorithm for finding shortest paths in a graph. (See Section 25.2.) Prim<FONT FACE="CG Times (W1)" SIZE=2>'</FONT>s algorithm has the property that the edges in the set <I>A</I> always form a single tree. As is illustrated in Figure 24.5, the tree starts from an arbitrary root vertex <I>r</I> and grows until the tree spans all the vertices in <I>V</I>. At each step, a light edge connecting a vertex in <I>A</I> to a vertex in <I>V</I> - <I>A</I> is added to the tree. By Corollary 24.2, this rule adds only edges that are safe for <I>A</I>; therefore, when the algorithm terminates, the edges in <I>A</I> form a minimum spanning tree. This strategy is &quot;greedy&quot; since the tree is augmented at each step with an edge that contributes the minimum amount possible to the tree<FONT FACE="CG Times (W1)" SIZE=2>'</FONT>s weight.<P>
<img src="506_a.gif"><P>
<h4><a name="08b9_17bd">Figure 24.4 The execution of Kruskal's algorithm on the graph from Figure 24.1. Shaded edges belong to the forest A being grown. The edges are considered by the algorithm in sorted order by weight. An arrow points to the edge under consideration at each step of the algorithm. If the edge joins two distinct trees in the forest, it is added to the forest, thereby merging the two trees.<a name="08b9_17bd"></sub></sup></h4><P>
<img src="507_a.gif"><P>
<a name="08b9_17b6">The key to implementing Prim's algorithm efficiently is to make it easy to select a new edge to be added to the tree formed by the edges in <I>A</I>. In the pseudocode below, the connected graph <I>G</I> and the root <I>r</I> of the minimum spanning tree to be grown are inputs to the algorithm. During execution of the algorithm, all vertices that are <I>not</I> in the tree reside in a priority queue <I>Q</I> based on a <I>key</I> field. For each vertex <I>v</I>, <I>key</I>[<I>v</I>] is the minimum weight of any edge connecting <I>v</I> to a vertex in the tree; by convention, <I>key</I>[<I>v</I>] = <img src="../images/infin.gif"> if there is no such edge. The field <img src="../images/piuc.gif">[<I>v</I>] names the &quot;parent&quot; of <I>v</I> in the tree. During the algorithm, the set <I>A</I> from <FONT FACE="Courier New" SIZE=2>GENERIC</FONT>-MST is kept implicitly as<P>
<pre><I>A</I> = {(<I>v</I>, <img src="../images/piuc.gif">[<I>v</I>]) : <I>v</I> <img src="../images/memof12.gif"> <I>V</I> - {<I>r</I>} - <I>Q</I>} .</sub></sup></pre><P>
When the algorithm terminates, the priority queue <I>Q</I> is empty; the minimum spanning tree <I>A</I> for <I>G</I> is thus<P>
<pre><I>A</I> = {(<I>v</I>, <img src="../images/piuc.gif">[<I>v</I>]) : <I>v</I> <img src="../images/memof12.gif"> <I>V</I> - {<I>r</I>}} .</sub></sup></pre><P>
<img src="508_a.gif"><P>
<h4><a name="08b9_17be">Figure 24.5 The execution of Prim's algorithm on the graph from Figure 24.1. The root vertex is a. Shaded edges are in the tree being grown, and the vertices in the tree are shown in black. At each step of the algorithm, the vertices in the tree determine a cut of the graph, and a light edge crossing the cut is added to the tree. In the second step, for example, the algorithm has a choice of adding either edge (b, c) or edge (a, h) to the tree since both are light edges crossing the cut.<a name="08b9_17be"></sub></sup></h4><P>
<pre><a name="08b9_17b7">MST-PRIM(<I>G, w, r</I>)</sub></sup></pre><P>
<pre>1  <I>Q</I> <img src="../images/arrlt12.gif"> <I>V</I>[<I>G</I>]</sub></sup></pre><P>
<pre>2  <B>for</B> each <I>u</I> <img src="../images/memof12.gif"> <I>Q</I></sub></sup></pre><P>
<pre>3      <B>do</B> <I>key</I>[<I>u</I>] <img src="../images/arrlt12.gif"> <img src="../images/infin.gif"></sub></sup></pre><P>
<pre>4  <I>key</I> [<I>r</I>] <img src="../images/arrlt12.gif"> 0</sub></sup></pre><P>
<pre>5  <img src="../images/piuc.gif"><I>[</I>r<I>] <img src="../images/arrlt12.gif"> NIL</I></sub></sup></pre><P>
<pre>6  <B>while</B> <I>Q </I><img src="../images/noteq.gif"> <img src="509_a.gif"></sub></sup></pre><P>
<pre>7      <B>do</B> <I>u</I> <img src="../images/arrlt12.gif"> EXTRACT-MIN(<I>Q</I>)</sub></sup></pre><P>
<pre>8         <B>for</B> each <I>v</I> <img src="../images/memof12.gif"> <I>Adj</I>[<I>u</I>]</sub></sup></pre><P>
<pre>9             <B>do</B> <B>if</B> <I>v</I> <img src="../images/memof12.gif"> <I>Q</I> and <I>w </I>(<I>u</I>, <I>v</I>) &lt; <I>key</I>[<I>v</I>]</sub></sup></pre><P>
<pre>10                  <B>then</B> <img src="../images/piuc.gif"><I>[</I>v<I>] <img src="../images/arrlt12.gif"> </I>u</sub></sup></pre><P>
<pre>11                       <I>key</I>[<I>v</I>] <img src="../images/arrlt12.gif"> <I>w</I>(<I>u</I>, <I>v</I>)</sub></sup></pre><P>
<a name="08b9_17b8">Prim's algorithm works as shown in Figure 24.5. Lines 1-4 initialize the priority queue <I>Q</I> to contain all the vertices and set the key of each vertex to <FONT FACE="Times New Roman" SIZE=3><img src="../images/infin.gif"></FONT>, except for the root <I>r</I>, whose key is set to 0. Line 5 initializes <img src="../images/piuc.gif">[<I>r</I>] to <FONT FACE="Courier New" SIZE=2>NIL</FONT>, since the root <I>r</I> has no parent. Throughout the algorithm, the set <I>V - Q</I> contains the vertices in the tree being grown. Line 7 identifies a vertex <I>u </I><img src="../images/memof12.gif"><I> Q</I> incident on a light edge crossing the cut (<I>V - Q, Q</I>) (with the exception of the first iteration, in which <I>u</I> = <I>r</I> due to line 4). Removing <I>u </I>from the set <I>Q</I> adds it to the set <I>V - Q</I> of vertices in the tree. Lines 8-11 update the <I>key</I> and <img src="../images/piuc.gif"> fields of every vertex <I>v</I> adjacent to <I>u</I> but not in the tree. The updating maintains the invariants that <I>key</I>[<I>v</I>] = <I>w</I>(<I>v</I>,<I> </I><img src="../images/piuc.gif"><I></I>[<I>v</I>]) and that (<I>v</I>,<I> </I><img src="../images/piuc.gif"><I></I>[<I>v</I>]) is a light edge connecting <I>v</I> to some vertex in the tree.<P>
<a name="08b9_17b9"><a name="08b9_17ba">The performance of Prim's algorithm depends on how we implement the priority queue <I>Q</I>. If <I>Q</I> is implemented as a binary heap (see Chapter 7), we can use the <FONT FACE="Courier New" SIZE=2>BUILD-</FONT><FONT FACE="Courier New" SIZE=2>HEAP</FONT> procedure to perform the initialization in lines 1-4 in <I>O</I>(<I>V</I>) time. The loop is executed |<I>V|</I> times, and since each <FONT FACE="Courier New" SIZE=2>EXTRACT-</FONT><FONT FACE="Courier New" SIZE=2>MIN</FONT> operation takes <I>O</I>(lg <I>V</I>) time, the total time for all calls to <FONT FACE="Courier New" SIZE=2>EXTRACT-</FONT><FONT FACE="Courier New" SIZE=2>MIN</FONT> is <I>O</I>(<I>V</I> 1g <I>V</I>). The <B>for</B> loop in lines 8-11 is executed <I>O</I>(<I>E</I>) times altogether, since the sum of the lengths of all adjacency lists is 2 |<I>E</I><FONT FACE="CG Times (W1)" SIZE=2>|</FONT>. Within the <B>for</B> loop, the test for membership in <I>Q</I> in line 9 can be implemented in constant time by keeping a bit for each vertex that tells whether or not it is in <I>Q</I>, and updating the bit when the vertex is removed from <I>Q</I>. The assignment in line 11 involves an implicit <FONT FACE="Courier New" SIZE=2>DECREASE-</FONT><FONT FACE="Courier New" SIZE=2>KEY</FONT> operation on the heap, which can be implemented in a binary heap in <I>O</I>(lg <I>V</I>) time. Thus, the total time for Prim<FONT FACE="CG Times (W1)" SIZE=2>'</FONT>s algorithm is <I>O</I>(<I>V </I>1g <I>V </I>+ <I>E </I>1g <I>V</I>) = <I>O</I>(<I>E </I>lg <I>V</I>), which is asymptotically the same as for our implementation of Kruskal<FONT FACE="CG Times (W1)" SIZE=2>'</FONT>s algorithm.<P>
<a name="08b9_17bb"><a name="08b9_17bc">The asymptotic running time of Prim's algorithm can be improved, however, by using Fibonacci heaps. Chapter 21 shows that if |<I>V</I><FONT FACE="CG Times (W1)" SIZE=2>|</FONT> elements are organized into a Fibonacci heap, we can perform an <FONT FACE="Courier New" SIZE=2>EXTRACT-</FONT><FONT FACE="Courier New" SIZE=2>MIN </FONT>operation in <I>O</I>(lg <I>V</I>) amortized time and a <FONT FACE="Courier New" SIZE=2>DECREASE-</FONT><FONT FACE="Courier New" SIZE=2>KEY</FONT> operation (to implement line 11) in <I>O</I>(1) amortized time. Therefore, if we use a Fibonacci heap to implement the priority queue <I>Q</I>, the running time of Prim's algorithm improves to <I>O</I>(<I>E + V</I> 1g <I>V</I>).<P>
<P>







<h2><a name="08ba_17c2">Exercises<a name="08ba_17c2"></h2><P>
<a name="08ba_17c3">24.2-1<a name="08ba_17c3"><P>
<a name="08ba_17bd"><a name="08ba_17be">Kruskal's algorithm can return different spanning trees for the same input graph <I>G</I>, depending on how ties are broken when the edges are sorted into order. Show that for each minimum spanning tree <I>T</I> of <I>G</I>, there is a way to sort the edges of <I>G</I> in Kruskal<FONT FACE="CG Times (W1)" SIZE=2>'</FONT>s algorithm so that the algorithm returns <I>T</I>.<P>
<a name="08ba_17c4">24.2-2<a name="08ba_17c4"><P>
<a name="08ba_17bf">Suppose that the graph <I>G</I> = (<I>V, E</I>) is represented as an adjacency matrix. Give a simple implementation of Prim<FONT FACE="CG Times (W1)" SIZE=2>'</FONT>s algorithm for this case that runs in <I>O</I>(<I>V</I><SUP>2</SUP>) time.<P>
<a name="08ba_17c5">24.2-3<a name="08ba_17c5"><P>
Is the Fibonacci-heap implementation of Prim<FONT FACE="CG Times (W1)" SIZE=2>'</FONT>s algorithm asymptotically faster than the binary-heap implementation for a sparse graph <I>G</I> = (<I>V, E</I>), where |<I>E</I><FONT FACE="CG Times (W1)" SIZE=2>|</FONT> = <img src="../images/bound.gif">(<I>V</I>)? What about for a dense graph, where <FONT FACE="CG Times (W1)" SIZE=2>|<I>E| = </I><img src="../images/bound.gif"></FONT>(<I>V</I><SUP>2</SUP>)? How must |<I>E</I><FONT FACE="CG Times (W1)" SIZE=2>|</FONT> and <FONT FACE="CG Times (W1)" SIZE=2>|<I>V</I>|</FONT> be related for the Fibonacci-heap implementation to be asymptotically faster than the binary-heap implementation?<P>
<a name="08ba_17c6">24.2-4<a name="08ba_17c6"><P>
<a name="08ba_17c0">Suppose that all edge weights in a graph are integers in the range from 1 to |<I>V</I><FONT FACE="CG Times (W1)" SIZE=2>|</FONT>. How fast can you make Kruskal<FONT FACE="CG Times (W1)" SIZE=2>'</FONT>s algorithm run? What if the edge weights are integers in the range from 1 to <I>W</I> for some constant <I>W</I>?<P>