| In the design of electronic circuitry, it is often necessary to make the pins of several components electricallyequivalent by wiring them together. To interconnect a set of n pins, we can use an arrangement of n – 1 wires, each connecting two pins. Of all such arrangements, the one that uses the least amount of wire is usually the most desirable.
We can model this wiring problem with a connected, undirected graph G = (V,E), where V is the set of pins, E is the set of possible interconnections between pairs of pins, and for each edge (u, v) ∈ E, we have a weight w(u,v) specifying the cost (amount of wire needed) to connect u and v. We then wish to find an acyclic subset T ⊆ E that connects all of the vertices and whose total weight
 <![CDATA[<a onClick="window.open('/olcweb/cgi/pluginpop.cgi?it=gif:: ::/sites/dl/free/0070131511/25338/ch23_overview_1.gif','popWin', 'width=NaN,height=NaN,resizable,scrollbars');" href="#"><img valign="absmiddle" height="16" width="16" border="0" src="/olcweb/styles/shared/linkicons/image.gif"> (0.0K)</a>]]>
is minimized. Since T is acyclic and connects all of the vertices, it must form a tree, which we call a spanning tree since it “spans” the graph G. We call the problem of determining the tree T the minimum-spanning-tree problem.1 Figure 23.1 shows an example of a connected graph and its minimum spanning tree.
In this chapter, we shall examine two algorithms for solving the minimum-spanning-tree: Kruskal’s algorithm and Prim’s algorithm. Each can easily be made to run in time O(E lg V) using ordinary binary heaps. By using Fibonacci heaps, Prims’s algorithm can be sped up to run in time O(E + V lg V), which is an improvement if |V| is much smaller than |E|.
The two algorithms are greedy algorithms, as described in Chapter 16. 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. Although the present chapter can be read independently of Chapter 16, the greedy methods presented here are a classic application of the theoretical notions introduced there.
Section 23.1 introduces a “generic” minimum-spanning-tree algorithm that grows a spanning tree by adding one edge at a time. Section 23.2 gives two ways to implement the generic algorithm. The first algorithm, due to Kruskal, is similar to the connected-components algorithm from Section 21.1. The second, due to Prim, is similar to Dijkstra’s shortest-paths algorithm (Section 24.3).
1The 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 T, since all spanning trees have exactly |V| - 1 edges by Theorem B.2. |
2002 McGraw-Hill Higher Education