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.