next up previous contents index CD CD Algorithms
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 gif. In such geometric problems, the point set tex2html_wrap_inline25268 defines a complete graph, with edge tex2html_wrap_inline25270 assigned a weight equal to the distance from tex2html_wrap_inline25272 to tex2html_wrap_inline25274 . Additional applications of minimum spanning trees are discussed in Section gif.

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.  

Mon Jun 2 23:33:50 EDT 1997