chap24.htm

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

<a name="08ba_17c7">24.2-5<a name="08ba_17c7"><P>
<a name="08ba_17c1">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 Prim'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>
<a name="08ba_17c8">24.2-6<a name="08ba_17c8"><P>
Describe an efficient algorithm that, given an undirected graph <I>G</I>, determines a spanning tree of <I>G</I> whose largest edge weight is minimum over all spanning trees of <I>G</I>.<P>
<a name="08ba_17c9">24.2-7<a name="08ba_17c9"><P>
Suppose that the edge weights in a graph are uniformly distributed over the half-open interval [0, 1). Which algorithm, Kruskal<FONT FACE="CG Times (W1)" SIZE=2>'</FONT>s or Prim<FONT FACE="CG Times (W1)" SIZE=2>'</FONT>s, can you make run faster?<P>
<a name="08ba_17ca">24.2-8<a name="08ba_17ca"><P>
Suppose that a graph<I> G</I> has a minimum spanning tree already computed. How quickly can the minimum spanning tree be updated if a new vertex and incident edges are added to <I>G</I>?<P>
<P>


<P>







<h1><a name="08bb_17c6">Problems<a name="08bb_17c6"></h1><P>
<a name="08bb_17c7">24-1 Second-best minimum spanning tree<a name="08bb_17c7"><P>
<a name="08bb_17c2"><a name="08bb_17c3">Let <I>G = </I>(<I>V, E</I>) be an undirected, connected graph with weight function <I>w </I>: <I>E</I> <img src="../images/arrow12.gif"> <B>R</B>, and suppose that |<I>E| </I><img src="../images/gteq.gif"> |<I>V| .</I><P>
<I><B>a.</I></B>     Let <I>T</I> be a minimum spanning tree of <I>G</I>. Prove that there exist edges (<I>u, v</I>)<I> </I><img src="../images/memof12.gif"> T<I> and (</I>x, y<I>)</I> <I><img src="../images/notmem.gif"></I> T <I>such that</I> T -<I>{(</I>u, v<I>)}<img src="../images/wideu.gif">{(</I>x, y<I>)} is a second-best minimum spanning tree of </I>G<I>.</I><P>
<I><B>b.</I></B>     Let <I>T</I> be a spanning tree of <I>G</I> and, for any two vertices <I>u, v </I><img src="../images/memof12.gif"> V<I>, let </I>max<I>[</I>u, v<I>] be an edge of maximum weight on the unique path between </I>u <I>and </I>v<I> in </I>T<I>. Describe an </I>O<I>(</I>V<I><SUP><FONT FACE="Times New Roman" SIZE=1>2</FONT></SUP>)-time algorithm that, given </I>T<I>, computes </I>max<I>[</I>u, v<I>] for all </I>u, v <I><img src="../images/memof12.gif"></I> V<I>.</I><P>
<I><B>c.</I></B>     Give an efficient algorithm to compute the second-best minimum spanning tree of <I>G</I>.<P>
<a name="08bb_17c8">24-2 Minimum spanning tree in sparse graphs<a name="08bb_17c8"><P>
<a name="08bb_17c4">For a very sparse connected graph<I> G</I> = (<I>V, E</I>), we can improve upon the <I>O</I>(<I>E </I>+ <I>V </I>lg <I>V</I>) running time of Prim's algorithm with Fibonacci heaps by "preprocessing" <I>G</I> to decrease the number of vertices before running Prim's algorithm. The following procedure takes as input a weighted graph <I>G</I> and returns a &quot;contracted&quot; version of <I>G</I>, having added some edges to the minimum spanning tree <I>T</I> under construction. Initially, for each edge (<I>u, v</I>) <img src="../images/memof12.gif"><I> E</I>, we assume that <I>orig</I>[<I>u, v</I>] = (<I>u, v</I>) and that <I>w</I>[<I>u, v</I>] is the weight of the edge.<P>
<pre><a name="08bb_17c5">MST-REDUCE(<I>G, T</I>)</sub></sup></pre><P>
<pre>1  <B>for</B> each <I>v</I> <img src="../images/memof12.gif"> <I>V</I>[<I>G</I>]</sub></sup></pre><P>
<pre>2      <B>do</B> <I>mark</I>[<I>v</I>] <img src="../images/arrlt12.gif"> FALSE</sub></sup></pre><P>
<pre>3         MAKE-SET(<I>v</I>)</sub></sup></pre><P>
<pre>4  <B>for</B> each <I>u</I> <img src="../images/memof12.gif"> <I>V</I>[<I>G</I>]</sub></sup></pre><P>
<pre>5      <B>do if</B> <I>mark</I>[<I>u</I>] = FALSE</sub></sup></pre><P>
<pre>6            <B>then</B> choose <I>v</I> <img src="../images/memof12.gif"> <I>Adj</I>[<I>u</I>] such that <I>w</I>[<I>u, v</I>] is minimized</sub></sup></pre><P>
<pre>7                 UNION(<I>u,v</I>)</sub></sup></pre><P>
<pre>8                 <I>T</I> <img src="../images/arrlt12.gif"> <I>T</I> <img src="../images/wideu.gif"> {<I>orig</I>[<I>u, v</I>]}</sub></sup></pre><P>
<pre>9                 <I>mark</I>[<I>u</I>] <img src="../images/arrlt12.gif"> <I>mark</I>[<I>v</I>] <img src="../images/arrlt12.gif"> TRUE</sub></sup></pre><P>
<pre>10  <I>V</I>[<I>G</I>'<I>] <img src="../images/arrlt12.gif"> {FIND-SET(</I>v<I>) : </I>v<I> <img src="../images/memof12.gif"> </I>V<I>[</I>G<I>]}</I></sub></sup></pre><P>
<pre>11  <I>E</I>[<I>G</I>'<I>] <img src="../images/arrlt12.gif"> <img src="512_a.gif"></I></sub></sup></pre><P>
<pre>12  <B>for</B> each (<I>x, y</I>) <img src="../images/memof12.gif"> <I>E</I>[<I>G</I>]</sub></sup></pre><P>
<pre>13      <B>do</B> <I>u</I> <img src="../images/arrlt12.gif"> FIND-SET(<I>x</I>)</sub></sup></pre><P>
<pre>14         <I>v</I> <img src="../images/arrlt12.gif"> FIND-SET(<I>y</I>)</sub></sup></pre><P>
<pre>15         <B>if</B> (<I>u, v</I>) <img src="../images/notmem.gif"> <I>E</I>[<I>G</I>']</sub></sup></pre><P>
<pre>16            <B>then</B> <I>E</I>[<I>G</I>'] <img src="../images/arrlt12.gif"> <I>E</I>[<I>G</I>'] <img src="../images/wideu.gif"> {(<I>u, v</I>)}</sub></sup></pre><P>
<pre>17                 <I>orig</I>[<I>u, v</I>] <img src="../images/arrlt12.gif"> <I>orig</I>[<I>x, y</I>]</sub></sup></pre><P>
<pre>18                 <I>w</I>[<I>u, v</I>] <img src="../images/arrlt12.gif"> <I>w</I>[<I>x, y</I>]</sub></sup></pre><P>
<pre>19            <B>else if</B> <I>w</I>[<I>x, y</I>] &lt; <I>w</I>[<I>u, v</I>]</sub></sup></pre><P>
<pre>20                    <B>then</B> <I>orig</I>[<I>u, v</I>]<img src="../images/arrlt12.gif"> <I>orig</I>[<I>x, y</I>]</sub></sup></pre><P>
<pre>21                         <I>w</I>[<I>u, v</I>] <img src="../images/arrlt12.gif"> <I>w</I>[<I>x, y</I>]</sub></sup></pre><P>
<pre>22  construct adjacency lists <I>Adj</I> for <I>G</I>'</sub></sup></pre><P>
<pre>23  <B>return</B> <I>G</I>' and <I>T</I></sub></sup></pre><P>
<I><B>a.     </I></B>Let <I>T</I> be the set of edges returned by MST-<FONT FACE="Courier New" SIZE=2>REDUCE</FONT>, and let <I>T</I>' be a minimum spanning tree of the graph <I>G</I>' returned by the procedure. Prove that <I>T </I><img src="../images/wideu.gif"> <I>{</I>orig<I>[</I>x, y<I>] </I>: <I>(</I>x, y<I>)</I> <I><img src="../images/memof12.gif"> T</I>'} is a minimum spanning tree of <I>G</I>.<P>
<I><B>b.</I></B>     Argue that |<I>V</I>[<I>G</I>']|<img src="../images/lteq12.gif"> |<I>V| </I>/2.<P>
<I><B>c.</I></B>     Show how to implement MST<B>-</B><FONT FACE="Courier New" SIZE=2>REDUCE</FONT> so that it runs in <I>O</I>(<I>E</I>) time. (<I>Hint</I>: Use simple data structures.)<P>
<I><B>d.</I></B>     Suppose that we run <I>k</I> phases of MST-R<FONT FACE="Courier New" SIZE=2>EDUCE<I>, </I></FONT>using the graph produced by one phase as input to the next and accumulating edges in<I> T</I>. Argue that the overall running time of the <I>k</I> phases is <I>O</I>(<I>kE</I>).<P>
<I><B>e.</I></B>     Suppose that after running <I>k</I> phases of MST-<FONT FACE="Courier New" SIZE=2>REDUCE</FONT>, we run Prim's algorithm on the graph returned by the last phase. Show how to pick <I>k </I>so that the overall running time is <I>O</I>(<I>E </I>lg lg <I>V</I>). Argue that your choice of <I>k</I> minimizes the overall asymptotic running time.<P>
<I><B>f.</I></B><I>     </I>For what values of |<I>E| (in terms of |</I>V|) does Prim's algorithm with preprocessing asymptotically beat Prim's algorithm without preprocessing?<P>
<P>







<h1>Chapter notes</h1><P>
Tarjan [188] surveys the minimum-spanning-tree problem and provides excellent advanced material. A history of the minimum-spanning-tree problem has been written by Graham and Hell [92].<P>
Tarjan attributes the first minimum-spanning-tree algorithm to a 1926 paper by O. Boruvka. Kruskal's algorithm was reported by Kruskal [131] in 1956. The algorithm commonly known as Prim's algorithm was indeed invented by Prim [163], but it was also invented earlier by V. Jarn&iacute;k in 1930.<P>
The reason why greedy algorithms are effective at finding minimum spanning trees is that the set of forests of a graph forms a graphic matroid. (See Section 17.4.) <P>
The fastest minimum-spanning-tree algorithm to date for the case in which |E| = <img src="../images/omega12.gif">(<I>V </I>lg <I>V</I>) is Prim's algorithm implemented with Fibonacci heaps. For sparser graphs, Fredman and Tarjan [75] give an algorithm that runs in <I>O</I>(<I>E</I> <img src="../images/beta14.gif"><I></I>(|<I>E|, |</I>V|)) time, where <img src="../images/beta14.gif"><I></I>(|<I>E|, |</I>V|) = min{<I>i</I>: lg<SUP>(<I>i</I>)</SUP> |<I>V|</I><img src="../images/lteq12.gif"> |<I>E|</I> / |<I>V|</I>}. The fact that |<I>E| <img src="../images/gteq.gif"> |</I>V| implies that their algorithm runs in time <I>O</I>(<I>E </I>lg<FONT FACE="Courier New" SIZE=2>*</FONT> <I>V</I>).<P>
<P>


<P>
<P>
<center>Go to <a href="chap25.htm">Chapter 25</A>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Back to <a href="toc.htm">Table of Contents</A>
</P>
</center>


</BODY></HTML>