Disjoint Sets | Disjoint set operations in daa

Disjoint Sets Introduction

1. A tree is used to represent each set and the root to name a set.
2. Each node points upwards to its parent
3. Two sets A and B are said to be disjoint if A – B = f. i.e., there is no common element in both A and B
4. A collection of disjoint sets is called a disjoint set forest
5. An array can be used to store parent of each element

Let  Σ = { S1  , S2 , …, Sk  }  be a collection of dynamic disjoint-sets of the elements and let x and y be any two elements. We want to support:

Make-Set(x):  create a set containing x

Find(x): return which set x belongs

Union(x, y): merge the sets containing x and containing y into one

Example:

n=11, 4 sets
s1 = {1,7,10,11} ,  s2 = {2,3,5,6},  s3 = {4,8} and s4 = {9}

Disjoint set operations in daa

Two important operations performed on disjoint sets are:

1. Union
2. Find

Disjoint set operations Union

1. If S1 and S2 are two disjoint sets, their union S1 U S2 is a set of all elements x such that x is in either S1 or S2
2. As the sets should be disjoint S1 U S2 replaces S1 and S2 which no longer exist
3. Union is achieved by simply making one of the trees as a subtree of other i.e to set parent field of one of the roots of the trees to other root

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²)

Disjoint set operations 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;
}

Topic : Disjoint Sets | Disjoint set operations in daa