Advanced · Module 18
Union-find and spanning trees
Track connected groups in nearly constant time, and build minimum spanning trees with it.
Some problems only ever merge groups: friendships, network links, regions of an image, variables proven equal. Union-find tracks those groups with an array of parent pointers, and two small improvements make its operations nearly constant time. This module builds that structure, then uses it, and a heap, in the two classic greedy algorithms for minimum spanning trees, with the cut property that proves they are correct.
- 1Disjoint setsPro — members onlyUnion-find keeps elements in groups that only ever merge. Each group is a tree of parent pointers, its root names the group, and two questions, which group is x in and merge these two groups, cover a surprising range of problems.13 min
- 2Union by rank and path compressionPro — members onlyAttaching the smaller tree under the larger keeps trees logarithmically shallow, and pointing every visited node straight at the root flattens them further. Together they make union-find's operations nearly constant time.14 min
- 3Kruskal's algorithmPro — members onlyA minimum spanning tree connects every vertex at the lowest total edge weight. Kruskal's algorithm sorts the edges and takes each one that joins two different components, with union-find deciding in nearly constant time.14 min
- 4Prim's algorithmPro — members onlyPrim's algorithm grows one tree from a starting vertex, each time adding the cheapest edge that leaves it. It looks like Dijkstra's algorithm with a different priority, and its array version is the best choice for dense graphs.14 min