UNIT- DISJOINT SETS DISJOINT SETS : Sets are represented by pair wise disjoint sets. IF Siand Syare two sets and i #j, then there is no common elements for Si and S). Example : When N = 10 elements. That can be partitioned into three disjoint sets i.e, $1, $2 and $3. S1={1,7,8,9) $2=(2,5,10} $3={3,4,6) Sets can be represented in 3 ways 1 : Tree Representation 2: Data Representation 3 : Array Representation 1: Tree Representation : The set will be represented as the tree structure where all children will store the address of parent / root node. The root node will store null at the place of parent address. In the given set of elements any element can be selected as the root node, generally we select the first node as the root node. Example: $1=({1,7,8,9} S2=(2,5,10) $3 = (3,4, 6}, Then these sets can be represented as SL s2 s3 2: Data Representation: We need to maintain the name of each set. So, we require one more data structure to store the set names. The data structure contains two fields. One is the set name and the other one is the pointer to root. The data representation for $1, $2 and $3. Example: S1={1,7,8,9} S2={2,5,10} $3=(3,4,6}3 : Array Representation : To represent the sets, we use an array of 1 to n elements where n is the ‘maximum value among the elements of all sets. The index values represent the nodes (elements of set) and the entries represent the parent node. For the root value the entry will be'“1'. Array Representation of the sets $1, $2 and $3 Example: $1={1,7,8,9} S2=(2,5,10} $3=(3,4,6} Jo J doo» si s2 83Disjoint Set Operations : Disjoint set supports two operations 1. Union 2. Find 1 : Disjoint set Union : IfS; and S) are two disjoint sets, then their union S; US) = {all elements x such that s is in Sor S)} Example: S1={1,7,8,9} $2={2,5,10} S$1US2={1,7,8,9,2,5,10} To perform disjoint set union between two sets Si and Sj can take any one root and make it sub-tree of the other. Example : S1={1,7,8,9} S2={2,5,10},Then SI U S2.can be represented as any one of the following. (3) on s1us2 2: Find (i) : Given the element, find the set containing i. Example: $1={1,7,8,9} $2=(2,5,10} $3={3,4,6} Find (4) = 4isin set $3 Find (9) = 9 is in set $1 Find (10 ) = 10 isin set S2UNION AND FIND ALGORITHMS : 1: Simple Union 2: Weighted Union 3: Find 4: Collapsing Find 1: Simple Union : To perform union the SimpleUnion(ij) function takes the inputs as the set roots i and j . And make the parent of ias j ie, make the second root as the parent of first root. Algorithm : Algorithm SimpleUnion (ij) { } Example : union (1,3) (or) The SimpleUnion(ij), algorithm is very easy to state, their performance characteristics are not very good. Ifwe want to perform following sequence of operations Union(1,2) Union(2,3), Union(3,4), Union(4,5)...... Union(n-1,n) ‘The sequence of Union operations is called degenerate tree as belowExample : The union operation can be performed as follows. union(10,20), union(20,30), union(30,40), union(40,50). Tx ec union (10,20) union (20,30) union (30,40) __ union (40,50) Union algorithm Time complexity : O(n) We can improve the performance of our union algorithm by avoiding the creation of degenerate trees. We can use Weighted Union rule.2.Weighted Union Algorithm Definition : if the number of nodes in the tree with root i is less than the number in the tree with root j, then make j the parent o otherwise make i the parent of Algorithm : Algorithm : Weighted_Union( i,j) { pli] €-count{i]; //Initially pli] € - count{j}; temp € pli] + Ui]: if(pi] > p[j]) then // ihas few nodes than j { pli]=j; //j becomes parent of 1 ij] = temp; } else { pii]=i; //ibecomes parent ofj p[i] = temp; } } Example : Weighting rule to perform the sequence of set unions given below Solution: Array Representation pl] - a a Step1 : Initially OOOO:Step2 : Union(1,2) iy 2 2 3 4 N p| 2 6 OO- Step3 : Union(1,3) i 1 2 3 4 n p| 3 il 1 a “1 -3] |=-count{j]=p[3]=- Step4: Union(1,4) The above trees obtained using the weighting ruleExample : Consider the behavior of Weighted union on the following sequences of unions. Union (1,2 ), Union (3,4), Union (5,6 ), Union (7,8 ), Union (1,3 ), Union (5,7 ), Union (1,5), Solution: The sequence of unions starting from the initial configuration p[i] = -count[i]=-1 (1) [-4)) f-tl G4) Et) E44) E4411 OOOODO0O00 union(1,2) union(3,4) union(5,6) union(7,8) [2] [2] [2] [2] union (1,3) union (5,7) -4) -4)union (1,5) [-4] [-4] [-8] Explanation in Weighted Union Algorithm Union(1,5) pli] P[j]=-count{j] p(5]=-count[(5] p[5]=-4 temp = pli]+p[j] temp =-4-4=-8 if(pLi] > p[j]) then -4>-4-false P[j]=ip[5]=1 // for 5%node 1 is the root node pli] =temp pl1]=-8Find Algorithm: FIND(i), means it finds the root node of ith node, in other words, it returns the name of set i. Algorithm SimpleFind(i) >=0) do Example : Consider a tree Solution : If we want to Find(i) = 8, (*) Array Representation of tree i 1 2 3 4 5 6 7 8 p| -8 1 1 3 1 5 5 7 while ( p[i]>=0) - true i=p[8], ie 7 while (p[i]>=0) - true isp[7],ieS while (p[i]>=0) - true i=p[5], ie 1 while ( pliJ>=0) - false returni,iei=1. So 1 is the root node of node 8 Find algorithm Time complexity : 0 (N2) 10Collapsing Find Algorithm : Definition : ifj is anode on the path from ito its root and afi] # root[i), then set afj] to rootfij. using collapsing rule, the find operation can be performed. Algorithm : Collapse_find( i) { // Problem Description : This algorithm Collapse all nodes from i to root node. while ( p[r] > 0) do r=plr];_ //Find the root. while (i#r) do //Collapse nodes from itorootr return r; } Example : Consider a tree a‘Solution : IF we want to Find(i) = 8, Array Representation of tree i 1 2 3 4 5 6 p| 38 il 1 3 1 5 Step1:i=8,r=8 while ( p[r]>0) - true r=p[8], ie7 while (p[r]>0) - true r=p[7], Le S while (p{r]>0) - true r=p[5], ke 1 while ( p{r]>0) - false Step2 : Collapse nodes from I to root r. p[8}=1 // means for 8! node 1 is the root node i=7 again while (i #r 7#1 _ s=pli], s=pl7] s=5 plil=r p[7]=1 // means for 7* node 1 is the root node iS again while (i # r S#1 s=pli), p{S]=1 // means for St* node 1 is the root node i=l 2again while (i #r 1#1 return r, ie r=1 Array Representation of collapsing nodes from i to root j n 1 2 3 4 5 6 7 P 8 Al 1 3 1 5 1 After collapsing nodes from i to root j, the given tree is,