📄 chap24.htm
字号:
<HTML><HEAD>
<TITLE>Intro to Algorithms: CHAPTER 24: MINIMUM SPANNING TREES</TITLE></HEAD><BODY BGCOLOR="#FFFFFF">
<a href="chap25.htm"><img align=right src="../../images/next.gif" alt="Next Chapter" border=0></A>
<a href="toc.htm"><img align=right src="../../images/toc.gif" alt="Return to Table of Contents" border=0></A>
<a href="chap23.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A>
<h1><a name="08b3_17a4">CHAPTER 24: MINIMUM SPANNING TREES<a name="08b3_17a4"></h1><P>
<a name="08b3_179e"><a name="08b3_179f">In the design of electronic circuitry, it is often necessary to make the pins of several components electrically equivalent by wiring them together. To interconnect a set of <I>n</I> pins, we can use an arrangement of <I>n -</I> 1 wires, each connecting two pins. Of all such arrangements, the one that uses the least amount of wire is usually the most desirable.<P>
<a name="08b3_17a0"><a name="08b3_17a1"><a name="08b3_17a2">We can model this wiring problem with a connected, undirected graph <I>G</I> = (<I>V, E</I>), where <I>V</I> is the set of pins, <I>E</I> is the set of possible interconnections between pairs of pins, and for each edge (<I>u, v</I>) <img src="../images/memof12.gif"> <I>E</I>, we have a weight <I>w</I>(<I>u</I>, <I>v</I>) specifying the cost (amount of wire needed) to connect <I>u</I> and <I>v</I>. We then wish to find an acyclic subset <I>T</I> <img src="../images/rgtubar.gif"> <I>E</I> that connects all of the vertices and whose total weight<P>
<img src="498_a.gif"><P>
is minimized. Since <I>T</I> is acyclic and connects all of the vertices, it must form a tree, which we call a <I><B>spanning</I></B><I> <B>tree</I> </B>since it"spans" the graph <I>G</I>. We call the problem of determining the tree <I>T</I> the <I><B>minimum-spanning-tree problem</I></B>.<SUP>1</SUP> Figure 24.1 shows an example of a connected graph and its minimum spanning tree.<P>
<SUP>1</SUP>The phrase "minimum spanning tree" is a shortened form of the phrase "minimum-weight spanning tree." We are not, for example, minimizing the number of edges in <I>T</I>, since all spanning trees have exactly |<I>V|</I> - 1 edges by Theorem 5.2.<P>
In this chapter, we shall examine two algorithms for solving the minimum-spanning-tree problem: Kruskal's algorithm and Prim's algorithm. Each can easily be made to run in time <I>O</I>(<I>E </I>lg <I>V</I>) using ordinary binary heaps. By using Fibonacci heaps, Prim's algorithm can be sped up to run in time<I> O</I>(<I>E</I> + <I>V</I> lg <I>V</I>), which is an improvement if |<I>V|</I> is much smaller than |<I>E| .</I><P>
<a name="08b3_17a3">The two algorithms also illustrate a heuristic for optimization called the "greedy" strategy. At each step of an algorithm, one of several possible choices must be made. The greedy strategy advocates making the choice that is the best at the moment. Such a strategy is not generally guaranteed to find globally optimal solutions to problems. For the minimum-spanning-tree problem, however, we can prove that certain greedy strategies do yield a spanning tree with minimum weight. Greedy strategies are discussed at length in Chapter 17. Although the present chapter can be read independently of Chapter 17, the greedy methods presented here are a classic application of the theoretical notions introduced there.<P>
<img src="499_a.gif"><P>
<h4><a name="08b3_17a5">Figure 24.1 A minimum spanning tree for a connected graph. The weights on edges are shown, and the edges in a minimum spanning tree are shaded. The total weight of the tree shown is 37. The tree is not unique: removing the edge (b, c) and replacing it with the edge (a, h) yields another spanning tree with weight 37.<a name="08b3_17a5"></sub></sup></h4><P>
Section 24.1 introduces a "generic" minimum-spanning-tree algorithm that grows a spanning tree by adding one edge at a time. Section 24.2 gives two ways to implement the generic algorithm. The first algorithm, due to Kruskal, is similar to the connected-components algorithm from Section 22.1. The second, due to Prim, is similar to Dijkstra's shortest-paths algorithm (Section 25.2).<P>
<h1><a name="08b5_17ac">24.1 Growing a minimum spanning tree<a name="08b5_17ac"></h1><P>
Assume that we have a connected, undirected graph <I>G</I> = (<I>V, E</I>) with a weight function <I>w </I>: <I>E</I> <img src="../images/arrow12.gif"> <B>R</B> and wish to find a minimum spanning tree for <I>G</I>. The two algorithms we consider in this chapter use a greedy approach to the problem, although they differ in how they apply this approach.<P>
<a name="08b5_17a4"><a name="08b5_17a5"><a name="08b5_17a6">This greedy strategy is captured by the following "generic" algorithm, which grows the minimum spanning tree one edge at a time. The algorithm manages a set <I>A</I> that is always a subset of some minimum spanning tree. At each step, an edge (<I>u</I>, <I>v</I>) is determined that can be added to <I>A</I> without violating this invariant, in the sense that <I>A</I> <img src="../images/wideu.gif"> {(<I>u</I>, <I>v</I>)} is also a subset of a minimum spanning tree. We call such an edge a <I><B>safe edge</I></B> for <I>A</I>, since it can be safely added to <I>A</I> without destroying the invariant.<P>
<img src="500_a.gif"><P>
<h4><a name="08b5_17ad">Figure 24.2 Two ways of viewing a cut (S, V - S) of the graph from Figure 24.1. (a) The vertices in the set S are shown in black, and those in V - S are shown in white. The edges crossing the cut are those connecting white vertices with black vertices. The edge (d, c) is the unique light edge crossing the cut. A subset A of the edges is shaded; note that the cut (S, V - S) respects A, since no edge of A crosses the cut. (b) The same graph with the vertices in the set S on the left and the vertices in the set V - S on the right. An edge crosses the cut if it connects a vertex on the left with a vertex on the right.<a name="08b5_17ad"></sub></sup></h4><P>
<pre><a name="08b5_17a7">GENERIC-MST(<I>G, w</I>)</sub></sup></pre><P>
<pre>1 <I>A</I> <img src="../images/arrlt12.gif"> <img src="500_b.gif"></sub></sup></pre><P>
<pre>2 <B>while</B> <I>A</I> does not form a spanning tree</sub></sup></pre><P>
<pre>3 <B>do</B> find an edge (<I>u, v</I>) that is safe for <I>A</I></sub></sup></pre><P>
<pre>4 <I>A</I> <img src="../images/arrlt12.gif"> <I>A</I> <img src="../images/wideu.gif"> {(<I>u, v</I>)}</sub></sup></pre><P>
<pre>5 <B>return</B> <I>A</I></sub></sup></pre><P>
Note that after line 1, the set <I>A</I> trivially satisfies the invariant that it is a subset of a minimum spanning tree. The loop in lines 2-4 maintains the invariant. When the set <I>A</I> is returned in line 5, therefore, it must be a minimum spanning tree. The tricky part is, of course, finding a safe edge in line 3. One must exist, since when line 3 is executed, the invariant dictates that there is a spanning tree <I>T</I> such that <I>A</I> <img src="../images/rgtubar.gif"> <I>T</I>, and if there is an edge (<I>u</I>, <I>v</I>) <img src="../images/memof12.gif"> <I>T</I> such that (<I>u</I>, <I>v</I>) <img src="../images/notmem.gif"> <I>A</I>, then (<I>u</I>, <I>v</I>) is safe for <I>A</I>. <P>
In the remainder of this section, we provide a rule (Theorem 24.1 ) for recognizing safe edges. The next section describes two algorithms that use this rule to find safe edges efficiently.<P>
<a name="08b5_17a8"><a name="08b5_17a9"><a name="08b5_17aa"><a name="08b5_17ab">We first need some definitions. A <I><B>cut</I></B> (<I>S, V - S</I>) of an undirected graph <I>G</I> = (<I>V, E</I>) is a partition of <I>V</I>. Figure 24.2 illustrates this notion. We say that an edge (<I>u</I>, <I>v</I>) <img src="../images/memof12.gif"> <I>E<B> crosses</I></B> the cut (<I>S, V - S</I>) if one of its endpoints is in <I>S</I> and the other is in <I>V - S</I>. We say that a cut <I><B>respects</I></B> the set <I>A</I> of edges if no edge in <I>A</I> crosses the cut. An edge is a <I><B>light edge</I> </B>crossing a cut if its weight is the minimum of any edge crossing the cut. Note that there can be more than one light edge crossing a cut in the case of ties. More generally, we say that an edge is a <I><B>light edge</I></B> satisfying a given property if its weight is the minimum of any edge satisfying the property.<P>
<img src="501_a.gif"><P>
<h4><a name="08b5_17ae">Figure 24.3 The proof of Theorem 24.1. The vertices in S are black, and the vertices in V - S are white. The edges in the minimum spanning tree T are shown, but the edges in the graph G are not. The edges in A are shaded, and (u, v) is a light edge crossing the cut (S, V - S). The edge (x, y) is an edge on the unique path p from u to v in T. A minimum spanning tree T' that contains (u, v) is formed by removing the edge (x, y) from T and adding the edge (u, v).<a name="08b5_17ae"></sub></sup></h4><P>
Our rule for recognizing safe edges is given by the following theorem.<P>
<a name="08b5_17af">Theorem 24.1<a name="08b5_17af"><P>
Let <I>G</I> = (<I>V, E</I>) be a connected, undirected graph with a real-valued weight function <I>w</I> defined on <I>E</I>. Let <I>A</I> be a subset of <I>E</I> that is included in some minimum spanning tree for <I>G</I>, let (<I>S, V - S</I>) be any cut of <I>G</I> that respects <I>A</I>, and let (<I>u</I>, <I>v</I>) be a light edge crossing (<I>S, V - S</I>). Then, edge (<I>u</I>, <I>v</I>) is safe for <I>A</I>.<P>
<I><B>Proof </I></B>Let <I>T</I> be a minimum spanning tree that includes A, and assume that <I>T</I> does not contain the light edge (<I>u</I>, <I>v</I>), since if it does, we are done. We shall construct another minimum spanning tree <I>T</I><I>'</I> that includes <I>A</I> <img src="../images/wideu.gif"> {(<I>u</I>, <I>v</I>)} by using a cut-and-paste technique, thereby showing that (<I>u</I>, <I>v</I>) is a safe edge for <I>A</I>.<P>
The edge (<I>u</I>, <I>v</I>) forms a cycle with the edges on the path <I>p</I> from <I>u</I> to <I>v</I> in <I>T</I>, as illustrated in Figure 24.3. Since <I>u</I> and <I>v</I> are on opposite sides of the cut (<I>S, V - S</I>), there is at least one edge in <I>T</I> on the path <I>p</I> that also crosses the cut. Let (<I>x</I>, <I>y</I>) be any such edge. The edge (<I>x, y</I>) is not in <I>A</I>, because the cut respects <I>A</I>. Since (<I>x, y</I>) is on the unique path from <I>u</I> to <I>v</I> in <I>T</I>, removing (<I>x, y</I>) breaks <I>T</I> into two components. Adding (<I>u</I>, <I>v</I>) reconnects them to form a new spanning tree <I>T</I>'<I> = </I>T - <I>{(</I>x, y<I>)} <img src="../images/wideu.gif"> {(</I>u<I>, </I>v<I>)}.</I><P>
We next show that <I>T</I>'<I> is a minimum spanning tree. Since (</I>u<I>, </I>v<I>) is a light edge crossing (</I>S, V - S<I>) and (</I>x, y<I>) also crosses this cut, </I>w<I>(</I>u<I>, </I>v<I>) <img src="../images/lteq12.gif"> </I>w<I>(</I>x, y<I>). Therefore,</I><P>
<pre>w(T') = w (T) - w(x, y) + w(u, <I>v</I>)</sub></sup></pre><P>
<pre><img src="../images/lteq12.gif"> w (T) .</sub></sup></pre><P>
But <I>T</I> is a minimum spanning tree, so that <I>w</I>(<I>T</I>) <img src="../images/lteq12.gif"> <I>w</I>(<I>T</I>'<I>); thus, </I>T<I>'</I> must be a minimum spanning tree also.<P>
It remains to show that (<I>u</I>, <I>v</I>) is actually a safe edge for <I>A</I>. We have <I>A</I> <img src="../images/rgtubar.gif"><I></I> <I>T</I><I>'</I>, since <I>A</I> <img src="../images/rgtubar.gif"> <I>T</I> and (<I>x, y</I>) <img src="../images/notmem.gif"> <I>A</I>; thus, <I>A</I> <img src="../images/wideu.gif"> {(<I>u</I>, <I>v</I>)} <img src="../images/rgtubar.gif"> <I>T</I><I>'</I>. Consequently, since <I>T</I><I>'</I> is a minimum spanning tree, (<I>u</I>, <I>v</I>) is safe for <I>A</I>. <P>
Theorem 24.1 gives us a better understanding of the workings of the <FONT FACE="Courier New" SIZE=2>GENERIC</FONT>-MST algorithm on a connected graph <I>G</I> = (<I>V, E</I>). As the algorithm proceeds, the set <I>A</I> is always acyclic; otherwise, a minimum spanning tree including <I>A</I> would contain a cycle, which is a contradiction. At any point in the execution of the algorithm, the graph <I>G<SUB>A</I></SUB> = (<I>V, A</I>) is a forest, and each of the connected components of <I>G<SUB>A</I></SUB> is a tree. (Some of the trees may contain just one vertex, as is the case, for example, when the algorithm begins: <I>A</I> is empty and the forest contains |<I>V| </I>trees, one for each vertex.) Moreover, any safe edge<I> </I>(<I>u</I>, <I>v</I>) for <I>A</I> connects distinct components of <I>G<SUB>A</I></SUB>, since <I>A</I> <img src="../images/wideu.gif"> {(<I>u, v</I>)} must be acyclic.<P>
The loop in lines 2-4 of <FONT FACE="Courier New" SIZE=2>GENERIC</FONT>-MST is executed |<I>V</I>| - 1 times as each of the |<I>V</I>| - 1 edges of a minimum spanning tree is successively determined. Initially, when <img src="502_a.gif">, there are |<I>V</I>| trees in <I>G<SUB>A</I></SUB> and each iteration reduces that number by 1. When the forest contains only a single tree, the algorithm terminates.<P>
The two algorithms in Section 24.2 use the following corollary to Theorem 24.1.<P>
<a name="08b5_17b0">Corollary 24.2<a name="08b5_17b0"><P>
Let <I>G</I> = (<I>V, E</I>) be a connected, undirected graph with a real-valued weight function <I>w</I> defined on <I>E</I>. Let <I>A</I> be a subset of <I>E</I> that is included in some minimum spanning tree for <I>G</I>, and let <I>C</I> be a connected component (tree) in the forest <I>G<SUB>A</I></SUB> = (<I>V, A</I>). If (<I>u, v</I>) is a light edge connecting <I>C</I> to some other component in <I>G<SUB>A</I></SUB>, then (<I>u, v</I>) is safe for <I>A</I>.<P>
<I><B>Proof </I></B>The cut (<I>C, V - C</I>) respects <I>A</I>, and (<I>u, v</I>) is therefore a light edge for this cut. <P>
<h2><a name="08b6_0001">Exercises<a name="08b6_0001"></h2><P>
<a name="08b6_0002">24.1-1<a name="08b6_0002"><P>
Let (<I>u</I>, <I>v</I>) be a minimum-weight edge in a graph <I>G</I>. Show that (<I>u</I>, <I>v</I>) belongs to some minimum spanning tree of <I>G</I>.<P>
<a name="08b6_0003">24.1-2<a name="08b6_0003"><P>
Professor Sabatier conjectures the following converse of Theorem 24.1. Let <I>G</I> = (<I>V</I>, <I>E</I>) be a connected, undirected graph with a real-valued weight function <I>w</I> defined on <I>E</I>. Let <I>A</I> be a subset of <I>E</I> that is included in some minimum spanning tree for <I>G</I>, let (<I>S</I>, <I>V </I>- <I>S</I>) be any cut of <I>G</I> that respects <I>A</I>, and let (<I>u</I>, <I>v</I>) be a safe edge for <I>A</I> crossing (<I>S</I>, <I>V</I> - <I>S</I>). Then, (<I>u</I>, <I>v</I>) is a light edge for the cut. Show that the professor's conjecture is incorrect by giving a counterexample.<P>
<a name="08b6_0004">24.1-3<a name="08b6_0004"><P>
Show that if an edge (<I>u</I>, <I>v</I>) is contained in some minimum spanning tree, then it is a light edge crossing some cut of the graph.<P>
<a name="08b6_0005">24.1-4<a name="08b6_0005"><P>
Give a simple example of a graph such that the set of all edges that are light edges crossing some cut in the graph does not form a minimum spanning tree.<P>
<a name="08b6_0006">24.1-5<a name="08b6_0006"><P>
Let <I>e</I> be a maximum-weight edge on some cycle of <I>G</I> = (<I>V</I>, <I>E</I>). Prove that there is a minimum spanning tree of <I>G</I>' = (<I>V</I>, <I>E</I> - {<I>e</I>}) that is also a minimum spanning tree of <I>G</I>.<P>
<a name="08b6_0007">24.1-6<a name="08b6_0007"><P>
Show that a graph has a unique minimum spanning tree if, for every cut of the graph, there is a unique light edge crossing the cut. Show that the converse is not true by giving a counterexample.<P>
<a name="08b6_0008">24.1-7<a name="08b6_0008"><P>
Argue that if all of the edge weights of a graph are positive, then any subset of edges that connects all of the vertices and has minimum total weight must be a tree. Give an example to show that the same conclusion does not follow if we allow some weights to be nonpositive.<P>
<a name="08b6_0009">24.1-8<a name="08b6_0009"><P>
Let <I>T</I> be a minimum spanning tree of a graph <I>G</I>, and let <I>L</I> be the sorted list of the edge weights of <I>T</I>. Show that for any other minimum spanning tree <I>T</I>' of <I>G</I>, the list <I>L</I> is also the sorted list of edge weights of <I>T</I>'.<P>
<a name="08b6_000a">24.1-9<a name="08b6_000a"><P>
Let <I>T</I> be a minimum spanning tree of a graph <I>G</I> = (<I>V</I>, <I>E</I>), and let <I>V</I>' be a subset of <I>V</I>. Let <I>T</I>' be the subgraph of <I>T</I> induced by <I>V</I>', and let <I>G</I>' be the subgraph of <I>G</I> induced by <I>V</I>'. Show that if <I>T</I>' is connected, the <I>T</I>' is a minimum spanning tree of <I>G</I>'<P>
<P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -