Disjoint Sets:

Set Representation:

• 1. An array can be used to store parent of each element
  2. The ith element of this array represents the tree node that contains the element I and it gives the parent of that element
  3. Root node has a parent -1
  4. An array P[1:n] can be taken for all n elements in the forest
  5. Element at the root node is taken as the name of the set

Example: n=11, 4 sets S1 = {1, 7, 10, 11}, S2 = {2, 3, 5, 6}, S3 = {4, 8} and S4 = {9}

UNION-FIND Algorithms:

Union:

Algorithm SimpleUnion(i,j)
{
P[i] := j;
}

 Find:

Algorithm SimpleFind(i)
{
while( P[i] >= 0) do
{
i := P[i];
}
return I;
}

In a worst-case scenario SimpleUnion() and SimpleFind() perform badly. Suppose we start with the single element sets {1},{2},…,{n} , then, execute the following sequence of unions and finds UNION(1,2), UNION(2,3),…,UNION(n –1,n)
FIND(1),FIND(2),…,FIND(n).

This sequence results in a skewed tree

Time complexity for 1 union = 1
Time complexity for n-1 union = n-1
Therefore Tall unions = O(n)
Time complexity for 1 find = i
Time complexity for n find = 1+2+….+ n-1 + n = n(n+1)/2
Therefore Tall finds = O(n²)

Weighted Union:

• • 1. Simple Union leads to high time complexity in some cases
    2. Weighted union is a modified union algorithm with weighting rule
    3. Widely used to analyze the time complexity of an algorithm in average case
    4. Weighted union deals with making the smaller tree a subtree of the larger
    5. If the no.of nodes in the tree with root i is less than the no.of nodes in the tree with root j, then make j the parent of I, otherwise make i the parent of j
    6. Count of nodes can be placed as a negative number in the P[i] value of the root i

       WeightedUnion(i,j)
       {
       temp := P[i] + P[j]; // P[i]:=-count(i), P[j]:=-count(j) if(P[i]>P[j]) then
       {
       P[i] := j;
       P[j] := temp;
       }
       else
       {
       P[j] := i;
       P[i] := temp;
       }
       }

Collapsing Find:

1. SimpleFind() leads to high time complexity in some cases
2. CollapsingFind() is a modified version of SimpleFind()
3. If j is a node on the path from i to its parent and P[i]!= root, then set j to root

Algorithm CollapsingFind(i)
{
r := i;
while (P[r] >0) do
{
r := P[i];
}
while(i!=r) do
{
j := P[i];
P[i] := r;
i := j;
}
return r;
}