Sunday, February 15, 2015
What is Disjoint set Data Structure
It is a data structure to keep a record of set of elements that are partitioned into number of disjoint subsets.
Such type of data structure performs three basic operations:
1. MakeSet operation
2. Find operation
3. Union operation
1. MakeSet operation
2. Find operation
3. Union operation
Sometimes, it is called Union-Find data structure or Merge-Find data structure.
Applications
Applications
It is used as an auxiliary data structure for various algorithms like Kruskal’s algorithm in graph theory and other partitioning problems.
Also Read: C Program for Tower of Hanoi Problem
Also Read: C Program for Sorting an Array using Heap Sort
Also Read: C Program for Tower of Hanoi Problem
Also Read: C Program for Sorting an Array using Heap Sort
MakeSet Operation
Initially, input elements are considered as a collection of n sets, of which each element in each set. Each set has different element, so Si ∩ Sj = Φ. This makes sets disjoints.The operation MakeSet creates a new set containing a single element for each given element. MakeSet creates a set of singleton elements in which each element represent its own set as shown below.
Union and Find Operation
To add relation, aRb (a and b can be any element from given elements) we use Union operation. But to do union we have to find out that whether a and b are related or not.
This can be verified by Find operation. Find operation check whether a and b are already related or not. If they are not, then union is applied creating a new set Sk = Si U Sj and deletes Si and Sj. If they are related, Find returns the set in which they are located.
Eg: After some operations of union, some sets are grouped together as shown below:
To represent each set, which is important, an element is fixed which is called representative of that set. So, while we are using Find operation on any element X, it will return the representative of the set in which element X is present.
For better understanding watch below video:
In next tutorial we will be discussing about implementations of disjoint-set data structure.
Author Bio:
Manisha Khandelwal is a computer science engineering student who lives in India. Data Structure is one of her favorite subjects. You can find her on Facebook at http://www.facebook.com/mannkhandelwal or contact her on Gmail at manishakhandelwal2611@gmail.com.
For better understanding watch below video:
In next tutorial we will be discussing about implementations of disjoint-set data structure.
Author Bio:
Manisha Khandelwal is a computer science engineering student who lives in India. Data Structure is one of her favorite subjects. You can find her on Facebook at http://www.facebook.com/mannkhandelwal or contact her on Gmail at manishakhandelwal2611@gmail.com.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.