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.

Mon Jun 2 23:33:50 EDT 1997