Next: Prim's Algorithm Up: Graph Algorithms Previous: Modeling Graph Problems

# Minimum Spanning Trees

A tree is a connected graph with no cycles. A spanning tree is a subgraph of G that has the same set of vertices of G and is a tree. A minimum spanning tree of a weighted graph G is the spanning tree of G whose edges sum to minimum weight.

Figure: Two spanning trees of point set (a); the minimum spanning tree (b), and the shortest path from center tree (c)

Minimum spanning trees are useful in finding the least amount of wire necessary to connect a group of homes or cities, as illustrated in Figure . In such geometric problems, the point set defines a complete graph, with edge assigned a weight equal to the distance from to . Additional applications of minimum spanning trees are discussed in Section .

A minimum spanning tree minimizes the total length over all possible spanning trees. However, there can be more than one minimum spanning tree in any graph. Consider a graph G with m identically weighted edges. All spanning trees of G are minimum spanning trees, since each contains exactly n-1 equal-weight edges. For general weighted graphs, however, the problem of finding a minimum spanning tree is more difficult. It can, however, be solved optimally using two different greedy algorithms. Both are presented below, to illustrate how we can demonstrate the optimality of certain greedy heuristics.

Algorithms
Mon Jun 2 23:33:50 EDT 1997