Minimum Spanning Trees

Overview: 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 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

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. Figure 23.1 shows an example of a connected graph and its minimum spanning tree.

Figure 23.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. This minimum spanning tree is not unique: removing the edge (b, c) and replacing it with the edge (a, h) yields another spanning tree with weight 37.

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 O(E lg V) using ordinary binary heaps. By using Fibonacci heaps, Prim'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 Greedy Algorithms. 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 Greedy Algorithms, the greedy methods presented here are a classic application of the theoretical notions introduced there.