Why Kruskal’s Algorithm Needs Disjoint Sets
Kruskal’s algorithm processes the edges of a weighted graph in nondecreasing order of weight. It accepts an edge when its endpoints are in different components of the forest built so far, and rejects it when they are already connected. The central data-structure task is therefore to maintain a changing partition of the vertices and answer whether two vertices belong to the same part. A disjoint-set union structure, also called a union-find structure, performs this task.
Here, the input graph is finite, undirected and simple, with weights on its edges. A component of a graph is a maximal set of vertices in which every pair is joined by a path. In Kruskal’s algorithm, the relevant components are those of the subgraph formed by the edges accepted so far. The disjoint-set structure stores these components as sets; it does not store the input graph itself.
A representative is simply a selected element that identifies a set. Its identity is not mathematically important: two elements belong to the same set exactly when their find operations return the same representative. A common implementation represents each set by a rooted tree. Each element has a parent pointer; a root is an element whose parent is itself, and the root is the representative. The trees are separate, so they form a forest.
The Operations and Their Invariants
For every input vertex \(v\), make-set sets \(\operatorname{parent}[v]=v\) and \(\operatorname{rank}[v]=0\). It is applied once to each element before the other operations use it. Rank is an integer used to choose how to join two roots. It is not, in general, the current height of the tree.
Find follows parent pointers until it reaches a root. With path compression, it also changes the pointers along the search path so they point directly to that root. In recursive form, if \(v\) is not a root, the operation sets \(\operatorname{parent}[v]\) to \(\operatorname{find}(\operatorname{parent}[v])\), then returns that root. This shortcut changes the shape of a tree but not which elements belong to its set.
Union first finds the roots of the two elements. If the roots are equal, the elements are already in the same set, so no merge is needed. Otherwise, union by rank makes the root with smaller rank a child of the root with larger rank. If the ranks are equal, either root may be made the child; the surviving root’s rank is increased by one.
For every element \(v\), set its parent to itself and its rank to \(0\).
For elements \(u\) and \(v\), compute \(r_u=\operatorname{find}(u)\) and \(r_v=\operatorname{find}(v)\). Each find may compress its search path.
If \(r_u=r_v\), leave the forest unchanged. Otherwise, attach the lower-rank root under the higher-rank root; when ranks are equal, attach either root under the other and increase the surviving root’s rank by one.
Proof. Initially, each element is in its own singleton set, represented by itself. Suppose the parent-pointer trees represent the current partition. A find follows parent pointers within one tree, so it returns that tree’s root. Replacing pointers on the search path by pointers to that same root leaves every element in the same tree; thus path compression preserves the partition. For union, the two finds return the roots of the sets containing the arguments. If the roots agree, both arguments are in the same tree and no partition change is required. If the roots differ, they are roots of different trees. Making one root a child of the other joins those two trees into one and leaves every other tree unchanged. The represented partition has therefore merged exactly the two specified sets. Induction over the sequence of operations proves the result. \(\square\)
Proof. Initially, each root has rank \(0\), has one element, and has depth \(0\). Whenever one root is attached beneath another of strictly larger rank, ranks strictly increase along that new parent link. When equal-rank roots are joined, the attached root has rank \(r\) and the surviving root’s rank becomes \(r+1\), so rank again strictly increases along the link. A compression redirects a node to an ancestor. Ranks strictly increase along the original parent path, so the new parent also has strictly larger rank. This proves the parent-rank statement and shows that compression does not decrease a root’s rank.
It remains to check the size bound. A root of rank \(0\) has at least \(1=2^0\) element. A rank can increase only when two roots of the same rank \(r\) are joined. If each root represents at least \(2^r\) elements, their disjoint sets together contain at least \(2^r+2^r=2^{r+1}\) elements, and the new root has rank \(r+1\). Joining roots of unequal rank does not increase the surviving root’s rank or reduce its set size. Compression changes no set sizes. Thus every root of rank \(r\) has at least \(2^r\) elements. Finally, ranks strictly increase along each parent-pointer path, whose ranks are nonnegative integers and whose last vertex is a root of rank \(r\). A path can therefore have at most \(r\) links, proving the depth bound. \(\square\)
Worked Traces
Worked Example: Union by Rank and Path Compression
Start with the elements \(1,2,3,4,5,6\), each in its own set. The table records the parent pointers after each operation. A self-parent indicates a root. Ranks not changed in an operation retain their previous values.
| Operation | Parent pointers after the operation | Ranks after the operation |
|---|---|---|
| Make-set for all six elements | \(1,2,3,4,5,6\) | All \(0\) |
| \(\operatorname{union}(1,2)\) | \(1,1,3,4,5,6\) | \(r_1=1\); others \(0\) |
| \(\operatorname{union}(3,4)\) | \(1,1,3,3,5,6\) | \(r_1=r_3=1\); others \(0\) |
| \(\operatorname{union}(1,3)\) | \(1,1,1,3,5,6\) | \(r_1=2,\ r_3=1\); others \(0\) |
| \(\operatorname{find}(4)\) | \(1,1,1,1,5,6\) | Unchanged |
For the first union, the roots \(1\) and \(2\) both have rank \(0\). Attach \(2\) under \(1\) and raise \(r_1\) to \(1\). The second union similarly attaches \(4\) under \(3\) and raises \(r_3\) to \(1\). For \(\operatorname{union}(1,3)\), both roots have rank \(1\); attach \(3\) under \(1\) and raise \(r_1\) to \(2\). At this point the path from \(4\) to its root is \(4\to3\to1\). The find of \(4\) returns \(1\) and compresses that path by setting the parent of \(4\) directly to \(1\). Elements \(5\) and \(6\) remain singleton sets throughout.
Check: The final roots are \(1,5,6\), so the represented sets are \(\{1,2,3,4\}\), \(\{5\}\), and \(\{6\}\). There are four elements in the first set, consistent with its root rank \(2\) and the bound \(2^2=4\).
Worked Example: Testing Edges in Kruskal’s Algorithm
Let the weighted graph have vertex set \(V=\{A,B,C,D,E\}\) and edge set \(E=\{AB,CD,BC,DE,AC\}\), with weights \(w(AB)=1\), \(w(CD)=2\), \(w(BC)=3\), \(w(DE)=4\), and \(w(AC)=5\). The edges are already listed in nondecreasing order of weight. Make a singleton set for each vertex, then process each edge in order. In the table, a pair of different roots means the edge is accepted and their sets are united.
| Edge | Roots found for its endpoints | Decision and parent-pointer change |
|---|---|---|
| \(AB\), weight \(1\) | \(A,B\) | Accept; set parent of \(B\) to \(A\), and raise rank of \(A\) to \(1\). |
| \(CD\), weight \(2\) | \(C,D\) | Accept; set parent of \(D\) to \(C\), and raise rank of \(C\) to \(1\). |
| \(BC\), weight \(3\) | \(A,C\) | Accept; ranks tie, so set parent of \(C\) to \(A\), and raise rank of \(A\) to \(2\). |
| \(DE\), weight \(4\) | \(A,E\) | Accept; find compresses \(D\to C\to A\) to \(D\to A\), then sets parent of \(E\) to \(A\). |
| \(AC\), weight \(5\) | \(A,A\) | Reject; the endpoints already have the same representative. |
The accepted edge set is \(\{AB,CD,BC,DE\}\), with total weight \(1+2+3+4=10\). After the first two edges, \(B\) has root \(A\) and \(D\) has root \(C\). After \(BC\), \(C\) is a child of \(A\), while \(D\) still points to \(C\). Thus the find for \(D\) during the \(DE\) check follows \(D\to C\to A\), compresses the path, and returns \(A\). The root \(A\) has rank \(2\), greater than the rank \(0\) of \(E\), so \(E\) is attached beneath \(A\) without increasing \(r_A\).
Check: The four accepted edges connect all five vertices: \(B,C,D,E\) each have a path to \(A\). They have no cycle: each was added between different components. A connected graph on five vertices with four edges is a tree. Directly, the accepted edges form the path \(B-A-C-D-E\). The rejected edge \(AC\) joins vertices already connected by the accepted path \(A-B-C\), so adding it would create a cycle.
Worked Example: Disconnected Input and an Isolated Vertex
Let \(G\) have vertex set \(V=\{p,q,r,s,t\}\) and edge set \(E=\{pq,rs,qs\}\), with weights \(w(pq)=1\), \(w(rs)=2\), and \(w(qs)=3\). Vertex \(t\) is isolated. Initialise five singleton sets and process the edges in weight order.
For \(pq\), the representatives are \(p\) and \(q\), so accept the edge and unite their sets. For \(rs\), the representatives are \(r\) and \(s\), so accept it and unite those sets. Before checking \(qs\), the sets are \(\{p,q\}\), \(\{r,s\}\), and \(\{t\}\). The representatives of \(q\) and \(s\) are different, so accept \(qs\) and unite the first two sets. The final sets are \(\{p,q,r,s\}\) and \(\{t\}\), and the accepted edge set is \(\{pq,rs,qs\}\), with total weight \(1+2+3=6\).
Check: The accepted edges connect \(p,q,r,s\), and there are three edges on those four vertices. They form the path \(p-q-s-r\), so they make a tree on that component. The isolated vertex \(t\) remains a separate component, as it has no incident edge in \(E\). Thus the output is a spanning forest of \(G\), not a spanning tree of the disconnected graph.
Common Mistakes and Why the Structure Matters
Do not compare immediate parent pointers instead of finding roots. In the second example, after accepting \(BC\), the parent of \(B\) is \(A\), while the parent of \(D\) is \(C\). A direct comparison would report different parents for \(B\) and \(D\). But following the pointers gives \(B\to A\) and \(D\to C\to A\): both have representative \(A\). Therefore \(B\) and \(D\) are already in the same set. Only the roots returned by find correctly determine whether two vertices belong to the same component.
Rank is not the current height. In the first example, the root \(1\) has rank \(2\) after the unions. Before compression, the path from \(4\) to \(1\) has two edges; after compression it has one. The rank remains \(2\), because path compression changes parent pointers but does not reverse any union decision. Treating rank as the current height and reducing it after compression would confuse a structural bound with a measured height.
For Kruskal’s algorithm, the practical rule is simple: initialise one set per vertex, and for every candidate edge \(uv\), compare \(\operatorname{find}(u)\) and \(\operatorname{find}(v)\). If the representatives differ, accept the edge and union the sets. If they agree, reject the edge. This is precisely how the data structure records whether an edge would join distinct current components.
Check Your Understanding
For each question, reason from the parent-pointer and rank rules given above.
- After \(\operatorname{union}(a,b)\) joins two rank-\(0\) roots, which parent pointer changes and what is the surviving root’s rank?
- If a find follows the path \(x\to y\to z\), where \(z\) is a root, what parent pointer does path compression assign to \(x\)?
- Suppose \(\operatorname{find}(u)=r\) and \(\operatorname{find}(v)=r\). What does Kruskal’s algorithm do with the candidate edge \(uv\), and why?
- Can path compression change the partition of the elements? Explain using the parent-pointer trees.
- A root has rank \(3\). What lower bound on the number of elements in its set follows from the rank-size result?