Disjoint sets

#Day 4

Disjoint sets are the important data structure, mostly used in solving graph problems.

According to Wikipedia

In mathematics, two sets are said to be disjoint if they have no element in common. Equivalently,disjoint sets are sets whose intersection is the empty set.

For this data structure, we will take an example of 5 vertices, say 1,2,3,4 and 5.

How to construct disjoint sets

For the construction of disjoint sets, we need to initialize a Node which can hold three type of values

  • Representative of the set (value of the node itself)
  • Parent (pointer to itself in starting)
  • Rank (starts with 0)

 

ds1
Image: 1

 

For above example, we created 5 different nodes with rank 0 and parent pointing to themselves. Apart from this,we initialize an empty dictionary and store above nodes against the vertices of the node as key.

So we have a dictionary as

{ 1:node1,2:node2,3:node3,4:node4,5:node5 }

Next operation which can be done on this structure is the union of sets. For this, basic idea is to find the parent(the most upper level) of both the sets and merge the sets according to their parent. We get the nodes of both the vertices which need to be joined and process according to the following code

 

parent1 = self.findParent(node1)
parent2 = self.findParent(node2)
if parent1==parent2:
 do nothing
if parent1.rank<parent2.rank:
 parent1.parent = parent2
elif parent1.rank>parent2.rank:
 parent2.parent = parent1
else:
 parent1.parent = parent2
 parent2.rank +=1

 

 

Finding the parent of node

To find the parent of the node we backtrack to the higher level of the tree and in the process of that, we do the path compression which decreases the level of the tree.(Parent-child tree)

def findParent(node): 
    if node.parent!=node:
        node.parent = findParent(node.parent)   
    return node.parent

After initializing the nodes we do following operations-

  • union(1,2)       (Image:2)

 

ds2.png
Image: 2

 

After above operation, our structure holds the structure as Image 2. Now rank of node 2 is 1 and parent of node 1 is node 2.

  • union(4,3)       (Image:3)
ds3
Image: 3

Now we got the parent of node 4 as node 3. And the rank of node 3 increased by 1.

  • union(5,4)       (Image:4)
ds4.png
Image: 4

Now the parent of 5 is also node 3.

  • union (2,5)      (Image:5)
ds5.png
Image: 5

As a final structure, node 3 is the parent of all.

If we query on this structure with each node, the answer should return as 3.

Use of Disjoint Sets

Disjoint sets are used to determine cycle in the graph.

This is pretty useful in Kruskal’s Minimum Spanning Tree algorithm as well.

Source Code

To get the source code implementation of DS please refer to this.

Advertisements

One thought on “Disjoint sets”

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