algorithms

Union-Find Data Structure: Intro

A disjoint-set data structure, also called a union–find data structure keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets. With this setting we define the following operations:

Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.

Union: Join two subsets into a single subset.

To be more specific, Union(x, y): replaces the set x and set y with a single set x U y.  Find(x): returns the unique ID for the set containing x.

Example Usage:
The data structure can be used in Kruskal’s algorithm. Kurskal’s algorithm to find the minimum spanning tree first sorts all the edges and then adds them one by one to the tree taking care that no cycle is formed.

When we consider an edge (v, w) in the algorithm, we just test whether Find(v) equals Find(w). If they are equal, it means that v and w are already in the same tree so we skip over the edge. If they are not equal, we insert the edge into our forest and perform a Union(v, w) operation.

Advertisements

One thought on “Union-Find Data Structure: Intro

Let me Know What you Think!

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 )

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s