Disjoint-set forest 2026-10-18
View more
A disjoint-set forest represents each block of a set partition by a rooted tree. Each set element stores a pointer to its parent in a rooted tree; the root of a tree stores a pointer to itself as a stopping convention. These self-pointers are sentinels, omitted from the forest's edges. Following parent pointers reaches the disjoint-set representative, the root of a tree. An indexed array parent suffices when members are numbered consecutively. The rooted trees encode membership; their edges need not be edges of any input graph.
To link different blocks of a set partition, point one root of a tree at the other root of a tree. Linking roots preserves every old membership and joins exactly the two rooted trees. Arbitrarily reparenting a nonroot could detach only part of a block of a set partition, so it would not implement the required disjoint-set union operation. The disjoint-set find operation terminates because each nonroot pointer moves towards the unique root of a tree; linking distinct roots cannot introduce a graph cycle.
Read the full article
Disjoint-set union operation 2026-10-18
View more
The disjoint-set union operation first uses the disjoint-set find operation to locate the blocks of a set partition containing . If they are different blocks of a set partition , replace them by their union ; every other block of a set partition stays as it was. If the two disjoint-set representatives agree, no merge is needed. Here unite returns True exactly when it merges two different blocks of a set partition. A successful call decreases their count by one; a redundant call preserves it. The name union is also customary. Some interfaces instead accept already found disjoint-set representatives, making that linking step a separate operation.
For an original example, initialize as seven singleton sets. Apply the calls in this order:
(1)
The first five calls succeed. After the third, the partition of a set is ; after the fifth it is . The sixth returns False: are already together. The blocks of a set partition number , counting the initial state. A disjoint-set find operation on cannot merge it with any other member.
Figure 1.
Five successful disjoint-set union operations and one redundant call on seven elements
. Each coloured enclosure is one block of a set partition. Columns identify the same seven members in every row; enclosures show membership rather than parent pointers. Details.
This is exactly the kind of changing membership needed by Kruskal component merging: an accepted edge joins two current connected components of a graph, while an edge whose endpoints already have equal disjoint-set representatives is rejected. The existing Kruskal's algorithm worked example follows that application. A disjoint-set forest stores membership efficiently without repeatedly enumerating every block of a set partition.
Read the full article
Path compression 2026-10-18
View more
Path compression changes parent pointers during a disjoint-set find operation so that future queries traverse fewer edges. Full path compression first follows the entire parent route to its root of a tree, then makes every member on that route point directly to that same root of a tree. No member changes its block of a set partition or its disjoint-set representative. Pointers outside the traversed route stay as they were. The following iterative Python implements full path compression and union by rank; parent and rank are initially indexed arrays with parent[x] = x and rank[x] = 0 for every valid member.
def find(x):
    root = x
    while parent[root] != root:
        root = parent[root]
    while parent[x] != x:
        following = parent[x]
        parent[x] = root
        x = following
    return root

def unite(x, y):
    a, b = find(x), find(y)
    if a == b:
        return False
    if rank[a] < rank[b]:
        a, b = b, a
    parent[b] = a
    if rank[a] == rank[b]:
        rank[a] += 1
    return True
Starting from the displayed disjoint-set forest, find(3) traverses , returns and changes only from to . The route still has two edges. Then find(5) changes only from to . The final parent array is ; every stored rank retains its displayed value. The rooted tree at now has height one although its root's rank is two. Root still represents a separate singleton set.
Figure 1.
Full path compression shortens two parent routes while union by rank metadata stays unchanged
. Arrows point towards the parent in a rooted tree; self-pointers at roots are omitted. The same partition of a set appears before and after find(3) followed by find(5). Labels record stored ranks, including historical ranks at nonroots. Details.
The two-pass algorithm first discovers the answer and then reuses it. During the second pass, saving following before overwriting the pointer preserves the remaining route. Every replacement pointer targets the original root of a tree, proving that the partition of a set is unchanged.
Full path compression is one specific rule. The authored UF.java implementation instead uses path halving, redirecting a visited member to its parent's parent while advancing along the route. Its union by rank rule agrees with the one above.[ref]
Read the full article