The Min Cost Spanning Tree finds a tree of minimum cost
Initialize each node as it's own tree in a forest
Sort the arcs in min-cost order.
For each arc, attempt to add it. If both ends of the arc have the same tree id, then don't add the arc.
If the nodes have differing tree ids, then add the arc and merge the trees together.
The heavy computation is the disjoint set union.
I think this one is about as good as it gets.