Disjoint-Set Data Structures

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.

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s