Turn the cut property into Kruskal's implementation
Sort all undirected edges by weight. Add an edge only if union-find confirms it connects different components. Continue until the connected graph has V-1 selected edges, or exhaust input and return a forest with an explicit disconnected status.
Vertices: 0, 1, 2, 3
Edges by weight:
0-1: 1 -> take
1-2: 2 -> take
0-2: 3 -> skip: cycle
2-3: 4 -> take
Total: 7, selected edges: 3
With sorting, the common bound is O(E log E), plus near-linear union-find work. Prim's priority-queue version explores frontier edges from a growing component and commonly runs in O(E log V). Choose based on graph representation and workload, not only headline bounds.
Exercise
Use the previous lesson's disjoint set to implement Kruskal. Test equal weights, negative weights, parallel edges, self-loops, and disconnected input. Sum weights in Long and define accepted bounds.
Check: validate both acyclicity and connectivity for a claimed tree. Compare total weight against exhaustive spanning-tree enumeration on very small graphs, allowing multiple valid edge sets with the same optimum.