Disjoint Sets Representation

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:


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


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)

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(n2)

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
        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;
        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;

Leave a Reply