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.

Log in or register to write something here or to contact authors.