What you're seeing
A minimum spanning tree connects every vertex of a weighted graph using a subset of edges whose total weight is as small as possible — the cheapest way to wire up a network with no redundant loops. Kruskal's method is pure greed with a safety check: sort all edges from cheapest to most expensive, then walk the list and grab each edge unless its two endpoints are already connected (which would create a cycle and waste weight). Telling "already connected?" fast is exactly the job of union–find: each vertex starts in its own set, and every accepted edge merges two sets. When one set remains, the tree spans the whole graph. The node colors here are those sets, coalescing as edges are added.
The rule
sort edges by weight, ascending
make each vertex its own set # union–find
MST = {}
for (u, v, w) in sorted edges:
if find(u) ≠ find(v): # different components → no cycle
add (u, v) to MST; union(u, v)
# else: same component, skip (would form a cycle)
stop once MST has V−1 edges
The invariant
Greedy works here because of the cut property: for any way of splitting the vertices into two groups (a "cut"), the lightest edge crossing it belongs to some minimum spanning tree. Kruskal maintains the invariant that the edges chosen so far are a subset of some MST. When it accepts an edge, that edge is the cheapest one joining two still-separate components — i.e. the lightest edge crossing the cut between them — so by the cut property adding it keeps the set extendable to an MST. When it rejects an edge, both endpoints are already in the same component, so the edge closes a cycle; the cycle property says the heaviest edge on any cycle is in no MST, and since we're going in increasing weight this edge is that heaviest one — safely discarded. Process every edge and the chosen set is a minimum spanning tree (this entry's test checks its weight against Prim's algorithm).
The cost
The sort dominates: O(E log E), which is O(E log V) since E < V². The union–find work across all operations is only O(E·α(V)) — effectively linear — so it's free next to the sort. The alternative, Prim's algorithm, grows one tree from a seed using a priority queue and matches the bound; Kruskal tends to win on sparse graphs (and when edges are already sorted, it's essentially linear). For truly enormous graphs, Borůvka's algorithm parallelizes well, and randomized linear-time MST (Karger–Klein–Tarjan) exists.
In the wild
Minimum spanning trees are everywhere you want to connect points cheaply or cluster them. They design networks — power grids, water pipes, road and telecom layouts, chip routing — at minimum cost; they underlie single-linkage clustering (cut the most expensive MST edges to split data into groups) and are a step in some approximation algorithms (e.g. the classic 2-approximation for the travelling salesman). Image segmentation, handwriting recognition, and network-reliability analysis all lean on MSTs. Kruskal's pairing with union–find is also the textbook example of why that little data structure matters.
Try this
Watch the node colors: each accepted edge fuses two colors into one, and the algorithm finishes exactly when every node shares a color — that's the forest becoming a single tree in V−1 edges. Notice the faint skipped edges: each one was cheap enough to consider but would have closed a loop. Hit New graph and the chosen tree changes, but it's always the lightest one possible.
References
- Kruskal, J. B. "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem." Proceedings of the American Mathematical Society 7(1):48–50, 1956.
- Cormen, Leiserson, Rivest & Stein. Introduction to Algorithms, 4th ed. (CLRS), §21 (Minimum Spanning Trees) — the cut and cycle properties. MIT Press, 2022.
- Sedgewick & Wayne. Algorithms, 4th ed., §4.3 (Minimum Spanning Trees). algs4.cs.princeton.edu/43mst.