General Discussions

Union-Find Data Structure: Intro

PH Bytes

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…

View original post 43 more words


Let me Know What you Think!

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

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

Connecting to %s