Implementation of Disjoint-Set Data Structure

The disjoint-set data structure (also known as the union-find data structure) is useful for implementing Kruskal’s algorithm, but it is also useful, in general, for checking equivalences. Two elements that are equivalent, under any notion of equivalence, can be thought of as belonging to the same equivalence class and equivalence classes are essentially disjoint sets.

Operations

We go over one of the ways to implement the following methods supported by the disjoint-set data structure.

• DisjointSet(x): Create a set containing the element x.

• Find(x): Find the name of the set containing the element x.

• Union(x, y): Merge the sets named x and y.

Implementation as rooted trees

A single set is implemented as a rooted tree, where the tree is named after the name of the element present at the root.

• Each node has a parent pointer that points to the parent of that node in the rooted tree.

• The parent pointer of the root points to the root itself.