Kruskal's algorithm sorts every edge by weight, then walks the list adding each edge to the growing forest — but only if its two endpoints belong to different components. Cycle-checking is done in near-constant time using a union-find (disjoint-set) structure with path compression and union by rank. After |V|−1 accepted edges the forest becomes a single spanning tree of minimum total weight. Watch the DSU roots merge and the sorted edge list get consumed step by step.
accepted (MST) current rejected (cycle)
Every time Kruskal accepts an edge e = (u, v), that edge is the lightest one crossing the cut that separates u's component from every other vertex. The cut property says: for any cut, the minimum-weight edge crossing it belongs to some MST. So accepting e can never be a mistake. Sorted-edge order plus union-find gives us O(|E| log |E|) — dominated by the sort — and the DSU operations amortise to nearly O(|E| α(|V|)), where α is the inverse Ackermann function (effectively constant for any conceivable input).
When the graph is disconnected, Kruskal still terminates cleanly — you get a minimum spanning forest, one MST per connected component. That's why real-world tools like tc traffic-control classes, network-latency clustering, and cluster hierarchical-linkage (single-linkage clustering is literally MST plus cut) can use Kruskal on graphs without a global connectivity guarantee.
| Kruskal | Prim | |
|---|---|---|
| Grows by | lightest global edge that doesn't cycle | lightest edge leaving current tree |
| Core data structure | union-find (DSU) | min-priority queue |
| Complexity | O(|E| log |E|) | O((|V|+|E|) log |V|) |
| Better on | sparse graphs / edge-list input | dense graphs / adjacency-matrix input |
| Disconnected graph | gives minimum spanning forest naturally | needs a wrapper loop, one Prim per component |