Type the CLRS MST-KRUSKAL pseudocode

Answer

A = {} for each vertex v in G.V: MAKE-SET(v) sort G.E by non-decreasing weight w for each edge (u, v) in sorted order: if FIND-SET(u) != FIND-SET(v): A = A union {(u, v)} UNION(u, v) return A

Sorting the edges is the O(E lg V) bottleneck; the union-find operations are near-linear. Adding only cross-component edges keeps A a forest and, by Corollary 21.2, a subset of some MST.