The disjoint-set data structure is a data structure that represents set partitions.

A set partition of a set S is a collection of disjoint subsets of S whose union is S.

Sets are *disjoint* if and only if they have no elements in common, and the *union* of a collection of sets is the set obtained by combining the elements of each set. So, when we partition a set, we put all of its elements into a collection of subsets, making sure that none of the subsets share any elements. For example, the set partitions of {1,2,3} are {{1,2,3}}, {{1},{2},{3}}, {{1},{2,3}}, {{1,2},{3}}, and {{1,3},{2}}.

Again, a disjoint-set data structure lets us efficiently model a set partition on a computer. It has two operations defined on it:

1. **Union**: Replaces two subsets with their union.

2. **Find**: Locates an element’s subset.

For this reason, disjoint-set data structures are also called “union-find data structures.”

To see my Python implementation of a disjoint-set data structure, visit my GitHub.

Kruskal’s algorithm uses disjoint-set data structures to find minimum spanning trees.

### Like this:

Like Loading...

*Related*