Ch08 THE DISJOINT SET ADT(数据结构外文版).pptVIP

* 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. §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: 12?4, 3?1, 6?10, 8?9, 7?4, 6?8, 3?5, 2?11, 11?12. 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) Dynamic (on-line) §2 The Dynamic Equivalence Problem ? 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 8 7 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. §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 6 8 7 S1 ? S2 S2 ? S1 Implementation 1: S1 S2 S3 ? ? ? name[ ] 10 6 8 7 4 1 9 2 3 5 S2 ? S1 ? S2 Here we use the fact that the elements are numbered from 1 to N.