Disjoint Sets: An Article

In this article, I will cover:

1. Disjoint sets and operations

2. Detecting a cycle

3. Graphical Representation

4. Array Representation

5. Weighted Union and Collapsing Find. 

Disjoint Sets are useful for detecting a cycle in a nondirected graph. We can represent disjoint sets using graph and array and time efficient operations are weighted union and collapsing find. 

Let's understand what disjoint sets are. You can represent each component as a set with S1 as {1, 2, 3, 4} and S2 as {5, 6, 7, 8} and the numbers are not common here, and the intersection of these two will not get anything which is ϕ. 

So the first unit gets a disjoint set and we can see how join(4,8) appended with join(1,5) results in a circle. 

Before to after: 

We can form all the sets in the beginning and add all the edges one by one. We can try to find the cycles in the graph through the Disjoint Set Data Structure. I will include all the edges of a graph, and how can we take the help of disjoint sets of finding a cycle? We can consider each element as a set. We'll be going on taking edges and finding the sets of them one by them. 

So we iteratively add all the edges and seeing if we find either of the numbers in the same set. If they are in the same set already, then we have a cycle detected. Kruskal's Algorithm uses the same way in order to find a spanning tree. We can also do parent-child relationships where in set{A,B} A is a parent of B. It really makes no difference which node you select as a parent. 

Here's how we do things graphically: 

And we assign each set's parents accordingly based on the from-to pair of the set we got earlier as indicated by {A. B}.

We start the array as a value of -1's. We first set the cell as a parent of itself. So if node 2 parent is 1 then we set element 2 to be 1. We can also set node 1 to -2 to show that there are multiple nodes and node 2 to 1.

If se set a node (3,4} and 3 is a parent of 4 so you can set node 3 to -2 and node 4 to 3. For 5 and 6 5 is a parent of 6 node 6 is 5 (Parent) and 6 is -2. Now (7,8) we have 7 at index 8 and -2 at index 7.  We all go to the main parent by going to the nodes until you reach a negative number to go to same parent. For example node 4's parent is 3, then find node 3 parent, and then traverse back until we find the "official parent node". That's how you take the union. We make the rank as even more negative as the number of nodes that the node is a parent as, and this is how union is performed on each node. The parent array is shown below.