Given a
undirected weighted graph G, the minimum spanning tree (MST) is the
spanning tree such that the sum of the weights of edges used is minimized.
There are two well-studied algorithm for computing minimum spanning trees: Prim's algorithm and Kruskal's algorithm. Both are O(E lg V) on sparse graphs. There do exist linear time MST algorithms, but they remain quite complex.