Kruskal's MST with Union-Find
Problem statement
You have a connected, weighted, undirected graph with $n$ vertices labelled $0 \dots n-1$ and a list of edges. Each edge is given as $[u, v, w]$: an undirected edge between vertices $u$ and $v$ with weight $w$.
Implement mst_weight(n, edges) returning the total weight of a minimum spanning tree (MST), computed with Kruskal's algorithm backed by a union-find (disjoint-set) structure using path compression and union-by-rank. The total MST weight is unique even when the specific set of chosen edges is not.
Example
mst_weight(4, [[0, 1, 1], [1, 2, 2], [2, 3, 3], [0, 3, 4]]) -> 6
The three cheapest edges (weights 1, 2, 3) connect all four vertices without forming a cycle; the weight-4 edge would close a cycle and is skipped, so the MST weight is $1 + 2 + 3 = 6$.
Going deeper (discussion):
- Prove Kruskal's is correct using the cut property.
- Show the running time is $O(m \log n)$.
- Compare with Prim's algorithm: when are binary-heap or Fibonacci-heap variants of Prim's preferable, and vice versa?
Show hint
Which data structure lets you ask, in near-constant time, whether two vertices are already connected by the edges you have kept so far?
Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.