Kruskal & Union-Find

The problem

You need to connect a set of towns with cable, and each possible link has a cost. Which links connect everything for the least total cost? Any cheapest solution has no cycles: drop one edge of a cycle and everything stays connected for less. So the answer is a tree spanning all the nodes, a minimum spanning tree (MST). MSTs show up in network design, clustering, and as a building block for approximation algorithms.

Kruskal's algorithm

Sort the edges from lightest to heaviest.
Go through them in order. Add an edge to the tree unless it would close a cycle, i.e. unless its two endpoints are already connected by edges chosen so far.
Stop when the tree has n − 1 edges.

This greedy choice is safe: the lightest edge joining two separate pieces can always be part of some MST. (If an MST didn't use it, swapping it in for the heavier edge joining those pieces would cost no more.)

Union-find: "are these already connected?"

Checking for a cycle could mean searching the tree built so far, which is slow. Instead, a union-find structure keeps the nodes in sets of "already connected" nodes. Each set is stored as a little tree of parent pointers; its root points to itself and names the set.

find(x): follow parent pointers from x until reaching the root. Two nodes are connected exactly when they have the same root.
union(a, b): make one root point to the other, merging the two sets.

Two tricks keep those trees very flat:

Union by rank. Each root has a rank, an upper bound on its tree's height. Put the root with the smaller rank underneath. If the ranks are equal, either can go on top (these pages put the second endpoint's root under the first's), and the new root's rank grows by one.
Path compression. After a find, point every node on the path straight at the root, so the next find is quicker.

Together they make each operation take effectively constant time: the amortised cost is O(α(n)), where α, the inverse Ackermann function, is at most 4 for any input that fits in the universe.

Reading the pictures

In the graph, thick blue edges are in the tree, faded edges were skipped, and the highlighted edge is being examined. Below it, each union-find set is drawn as a tree: filled roots, with their rank (r) underneath. Edges are taken by weight, with ties broken alphabetically by name (A–B before A–C).

	Kruskal with union-find
Time	O(E log E), dominated by sorting the edges; the union-find work is nearly linear.
Alternative	Prim's algorithm grows one tree from a start node, picking the cheapest edge leaving it, much like Dijkstra with a priority queue.