Kruskal's MST

Builds a minimum spanning tree by sorting every edge by weight and greedily keeping any edge that connects two so-far-separate components. A disjoint-set structure answers "would this edge close a cycle?" in near-constant time; its forest is drawn alongside the graph as it merges.

Best

O(E log E)

Average

O(E log E)

Worst

O(E log E)

Space

O(V)