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.