chapter 8 THE DISJOINT SET ADT 81 Equivalence relations Definition) Arelation R is defined on a set S if for every pair of elements(a, b),a, b ES, aR b is either true or false. If a b is true, then we say that a is related to b Definition A relation, over a set, S, is said to be an equivalence relation over S iff it is symmetric, reflexive, and transitive over S (Definition Two members x and y of a set S are said to be in the same equivalence class iffx-y
CHAPTER 8 THE DISJOINT SET ADT §1 Equivalence Relations 【Definition】A relation R is defined on a set S if for every pair of elements (a, b), a, b S, a R b is either true or false. If a R b is true, then we say that a is related to b. 【Definition】A relation, ~, over a set, S, is said to be an equivalence relation over S iff it is symmetric, reflexive, and transitive over S. 【Definition】Two members x and y of a set S are said to be in the same equivalence class iff x ~ y
82 The Dynamic Equivalence Problem Given an equivalence relation decide for any a and b if a-b Example〗 Given s={1,2,3,4,5,6,7,8,9,10,1,12}and9 relations:12=4,3=1,6≡10,8=9,7=4,6=8,3=5,2=11,1l=12 The equivalence classes are ( 2, 4, 7,11, 123,(,, 5,(6,8,9,) Algorithm:(Union /Find) [ /step 1: read the relations in*/ Initialize n disjoint sets; while( read in a -b)i if(! (Find (a== Find(b)) Union the two sets: 3/*end-while*/ / step 2: decide if a-b*/ while( read in a and b) if Find(a= Find(b)output( true ) else output( false )
§2 The Dynamic Equivalence Problem Given an equivalence relation ~, decide for any a and b if a ~ b. 〖Example〗 Given S = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 } and 9 relations: 124, 31, 610, 89, 74, 68, 35, 211, 1112. The equivalence classes are { 2, 4, 7, 11, 12 }, { 1, 3, 5 }, { 6, 8, 9, 10 } Algorithm: { /* step 1: read the relations in */ Initialize N disjoint sets; while ( read in a ~ b ) { if ( ! (Find(a) == Find(b)) ) Union the two sets; } /* end-while */ /* step 2: decide if a ~ b */ while ( read in a and b ) if ( Find(a) == Find(b) ) output( true ); else output( false ); } (Union / Find)
Elements of the sets:1.2.3.N e Sets:S1,S2,……andS;^S=(i≠j)— disjoint Example S1={6,7,8,10},S2={1,4,9},S3={2,3,5} Note: Pointers are from children 8) to parents A possible forest representation of these sets e Operations (1) Union(i)∷= Replace s;andS;bys=S∪S (2)Find (i): : Find the set Sk which contains the element i
Elements of the sets: 1, 2, 3, ..., N Sets : S1 , S2 , ... ... and Si Sj = ( if i j ) —— disjoint 〖Example〗 S1 = { 6, 7, 8, 10 }, S2 = { 1, 4, 9 }, S3 = { 2, 3, 5 } 10 6 7 8 4 1 9 2 3 5 A possible forest representation of these sets Note: Pointers are from children to parents Operations : (1) Union( i, j ) ::= Replace Si and Sj by S = Si Sj (2) Find( i ) ::= Find the set Sk which contains the element i
s3 Basic Data Structure ☆ Union(ij) Idea: Make S a subtree of s, or vice versa. that is, we can set the parent pointer of one of the roots to the other root. S1∪S Im plementation 1 S,∪S name[l S2 S3 ①⑨ → 2
§3 Basic Data Structure ❖ Union ( i, j ) Idea: Make Si a subtree of Sj , or vice versa. That is, we can set the parent pointer of one of the roots to the other root. 10 6 8 7 4 1 9 4 1 9 10 S 6 7 8 1 S2 S2 S1 Implementation 1: S1 S2 S3 • • • name[ ] 10 6 7 8 4 1 9 2 3 5 S2 S1 S2
Im plementation 2: s[element]=the elements parent. Note: S[ root]=0 and set name= root index. I Example The array representation of the three sets is Heave use中2图4ospo Hence they can be ual a of an ard void SetUnion( DisjSet S, (S1∪S SetType Rt1 SetType Rt2) I s[Rt2 ]=Rt1; y ☆Find(i) Im plementation 1: Implementation 2: SetType Find( elementType X, name啊ks DisjSet S) I for(; S[X]>0; X=SX]); return X; find(i)='s
Here we use the fact that the elements are numbered from 1 to N. Hence they can be used as indices of an array. Implementation 2: S [ element ] = the element’s parent. Note: S [ root ] = 0 and set name = root index. 10 6 7 8 4 1 9 2 3 5 〖Example〗The array representation of the three sets is ( S1 S2 S1 ) S [ 4 ] = 10 ❖ Find ( i ) Implementation 1: name[k] S • j i ... find ( i ) = ‘S’ Implementation 2: SetType Find ( ElementType X, DisjSet S ) { for ( ; S[X] > 0; X = S[X] ) ; return X ; } void SetUnion ( DisjSet S, SetType Rt1, SetType Rt2 ) { S [ Rt2 ] = Rt1 ; } [1] 4 [2] 0 [10] 0 [9] 4 [8] 10 [7] 10 [6] 10 [5] 2 [4] 0 [3] 2 S 10