MST — Kruskal's Algorithm
Build a minimum spanning tree by taking edges cheapest-first, skipping any that would close a cycle.
Open on GeeksforGeeks ↗Intuition
Sort every edge by weight and walk the list, taking an edge whenever its endpoints are not already connected. Unlike Prim's, the partial result is a forest of separate trees that gradually merge. The only hard question — 'are these two vertices already connected?' — is exactly what Union-Find answers in near-constant time.
Sort edges cheapest-first and take any that doesn't close a cycle — the classic greedy, with union-find providing the cycle test in near-constant time. The pairing is what matters: Kruskal is a sort plus a disjoint-set structure, and the DSU is what makes "would this create a cycle?" cheap enough for the greedy to be practical.
Approach
Sort edges by weight
Cheapest first. This is the greedy order, and the sort dominates the runtime at O(E log E).
Union-Find as the cycle test
find(u) == find(v) means both are already in the same tree, so the edge would create a cycle — skip it. Otherwise union them and take the edge.
Stop at V−1 edges
A spanning tree on V vertices has exactly V−1 edges. Finishing with fewer means the graph was disconnected and no spanning tree exists.
Solution & live demo
Common pitfalls
Comparing vertices instead of their roots
if u == v: continue
ru, rv = find(u), find(v) if ru == rv: continue
Two different vertices can already sit in the same component through earlier edges, and adding another edge between them closes a cycle. Only the component representatives reveal that — the raw endpoints never match.
Merging vertices rather than roots
parent[u] = v
parent[ru] = rv
Attaching a non-root breaks the forest: the old root of u's component still points elsewhere, so the two components never actually merge and later cycle tests give wrong answers.
Assuming an MST always exists
return total
return total if used == n - 1 else None
A disconnected graph has no spanning tree — the loop simply runs out of edges having used fewer than n - 1. Returning the accumulated weight reports a spanning forest as though it were a tree.
Edge cases
Fewer than V−1 edges are taken — report no MST.
Any consistent tie-break works; different MSTs may result, all of equal weight.
Endpoints share a root immediately — always skipped.