The Disjoint-Set Abstract Data Type | Algorithms II

Definition

A disjoint-set (or union-find) data structure maintains a partition of a set of $n$ elements into disjoint subsets. Each subset has a canonical representative element (typically the root in tree-based implementations).

Operations

Operation	Description
`MakeSet(x)`	Create a singleton set $\{x\}$ containing only element $x$ .
`Find(x)`	Return the representative of the set containing $x$ .
`Union(x, y)`	Merge the sets containing $x$ and $y$ into a single set. The representative of the result is typically the representative of one of the input sets.

In some formulations, Find is called In-Same-Set(x, y) and returns a boolean; this is equivalent to Find(x) == Find(y).

Invariant

At all times, the sets are pairwise disjoint. Every element belongs to exactly one set. After $n$ MakeSet operations, there are $n$ singleton sets; after $n-1$ Union operations, there is one set containing all elements.

Applications

Kruskal’s Minimum Spanning Tree

The canonical application. Kruskal’s algorithm sorts edges by weight, then iteratively adds the lightest edge that does not create a cycle. Disjoint sets track connected components:

for each vertex v: MakeSet(v)
edges = sort(edges by weight)
for (u, v, weight) in edges:
    if Find(u) != Find(v):
        add (u, v) to tree
        Union(u, v)

With an optimal disjoint-set implementation, Kruskal runs in $O(|E| \log |V|)$ time (dominated by sorting), where union-find operations contribute near-constant time.

Other Applications

Connected components in an undirected graph: iterate edges, Union the endpoints; each set is a component.
Equivalence relations: maintain equivalence classes under Union.
Dynamic connectivity: answer whether two vertices are connected after a sequence of edge additions.
Percolation theory: grid-based simulations of fluid flow; Union adjacent open cells.

Goal: Nearly Constant Time

The naive approaches (linked lists, hash tables) give $O(n)$ worst-case for at least one operation. With union by rank and path compression, $m$ operations on $n$ elements take $O(m \cdot \alpha(n))$ time, where $\alpha(n)$ is the inverse Ackermann function — effectively constant for any practical $n$ (see The Inverse Ackermann Bound).

Worked Example: Kruskal Trace

Consider the graph:

Vertices: A, B, C, D, E
Edges (weight): AB(1), CD(2), AC(3), BE(4), DE(5), BC(6), AE(7)

Step	Edge	Find	Action	Sets after
1	AB(1)	A≠B	Union	{A,B}, {C}, {D}, {E}
2	CD(2)	C≠D	Union	{A,B}, {C,D}, {E}
3	AC(3)	A≠C	Union	{A,B,C,D}, {E}
4	BE(4)	B≠E	Union	{A,B,C,D,E}
5	DE(5)	D=E	Reject	—
6	BC(6)	B=C	Reject	—
7	AE(7)	A=E	Reject	—

MST edges: AB, CD, AC, BE. Total weight: $1+2+3+4 = 10$ .

Summary

Property	Value
ADT operations	MakeSet, Find, Union
Key invariant	Sets are disjoint; union reduces count by 1
Naive linked list	Find $O(1)$ , Union $O(n)$
Naive hash table	Find $O(1)$ , Union $O(n)$
Optimal (forest + heuristics)	Both $\sim O(\alpha(n))$ amortised
Primary application	Kruskal’s MST algorithm
Exam context	Tripos Paper 1 Q9-10; trace on small examples and explain heuristics