Given a connected, undirected graph, a spanning tree is a graph that is a tree and connects all the vertices together. There may be many different spanning trees for a graph. One of them can be selected based on the weights of the edges. A minimum spanning tree is a spanning tree with weight less than or equal to the weight of every other spanning tree. A maximum spanning tree, in a similar way, is the spanning tree with the sum of the weights higher than or equal to the other possible trees. A minimum spanning tree can be determined using Prim's or Kruskal's algorithms. Also see Prim's Algorithm and Kruskal's Algorithm.
