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.