The Disjoint Set ADTIssues:Equivalence RelationsThe Dynamic Equivalence ProblemDisjoint SetsExample:PowerPoint PresentationcodingThe first algorithmOptimizationsSlide 11Slide 12Slide 13The O(M+N) algorithmSlide 15Slide 16Smart Union AlgorithmsSlide 18Slide 19Path Compression for faster findSlide 21Slide 22Union and FindSlide 24Slide 25Slide 26Slide 27Slide 28Slide 2911 The Disjoint Set ADTThe Disjoint Set ADTCS146CS146Chapter 8Chapter 8Yan Qing LeiYan Qing Lei22Issues:Issues:•The equivalence problemThe equivalence problem•The first algorithmThe first algorithm•Smart union algorithmsSmart union algorithms•Union and FindUnion and Find33Equivalence RelationsEquivalence Relations•A relation R is defined on a set S if for A relation R is defined on a set S if for every pair of elements (a,b), a,bevery pair of elements (a,b), a,bS, a R b S, a R b is either true or false. If a R b is true, then is either true or false. If a R b is true, then we say that a is related to b.we say that a is related to b.•An equivalence relation is a relation R that An equivalence relation is a relation R that satisfy three properties:satisfy three properties:–(reflexive) a R a, for all a (reflexive) a R a, for all a  S. S.–(symmetric) a R b if and only if b R a.(symmetric) a R b if and only if b R a.–(transitive) a R b and b R c implies that a R c.(transitive) a R b and b R c implies that a R c.44The Dynamic Equivalence The Dynamic Equivalence ProblemProblem•The equivalence class of an element The equivalence class of an element aaS is S is the subset of S that contains all the the subset of S that contains all the elements that are related to elements that are related to aa..•Equivalence classes form a partition of S: Equivalence classes form a partition of S: every member of S appears in exactly one every member of S appears in exactly one equivalence class.equivalence class.•To decide if two member are related, only To decide if two member are related, only need to check whether the two are in the need to check whether the two are in the same equivalence class.same equivalence class.55Disjoint SetsDisjoint Sets•Make the input a collection of N sets, each with Make the input a collection of N sets, each with one element.one element.–All relations (except reflexive) are false;All relations (except reflexive) are false;–Each set has a different element: SEach set has a different element: SiiSSjj== => it makes => it makes the sets disjoint.the sets disjoint.•Find operation: returns the name of the set Find operation: returns the name of the set containing a given element. containing a given element. •Add operation (e.g., add relation aAdd operation (e.g., add relation a~b)~b)–Check if a and b are already related: if they are in the Check if a and b are already related: if they are in the same equivalence class.same equivalence class.–If not, apply “union”: merge the two equivalence classes If not, apply “union”: merge the two equivalence classes containing a and b into a new equivalence class.containing a and b into a new equivalence class.66Example:Example: On a set of subsets, the three On a set of subsets, the three operations amount to operations amount to •Create a set of n disjoint subsets with Create a set of n disjoint subsets with every node in its own subset every node in its own subset •Test wheter A and B are in the same Test wheter A and B are in the same subset subset •If A and B are in the same subset, If A and B are in the same subset, then do nothing, else unify the then do nothing, else unify the subsets to which A and B belong subsets to which A and B belong77•The most efficient way to implement The most efficient way to implement the operation is:the operation is:•For every A it is possible to ask for the For every A it is possible to ask for the index of the subset to which A belongs index of the subset to which A belongs •This will be denoted as This will be denoted as find(A)find(A). And we . And we have A ~ B <--> find(A) == find(B). The have A ~ B <--> find(A) == find(B). The operation of adding a relation between operation of adding a relation between A and B will be denoted by A and B will be denoted by union(A, B)union(A, B) (even though nothing needs to happen). (even though nothing needs to happen). Thus, for union(A, B) one performs Thus, for union(A, B) one performs88codingcodingvoid union(Node A, Node B) void union(Node A, Node B) {{ if (find(A) != find(B))if (find(A) != find(B)) unify(A, B);unify(A, B); } }99The first algorithmThe first algorithm•All the elements in S are numbered sequentially All the elements in S are numbered sequentially from 0 to N-1from 0 to N-1—the numbering can be determined —the numbering can be determined by hashing —we have Sby hashing —we have Sii={i} for i=0 through N-1.={i} for i=0 through N-1.•Maintain, in an array, the name of the Maintain, in an array, the name of the equivalence class for each element.equivalence class for each element.• “ “find” is just a simple O(1) lookup.find” is just a simple O(1) lookup.•““union(a,b)”: suppose that a is in equivalence union(a,b)”: suppose that a is in equivalence class i and b is in equivalence class j. Scan class i and b is in equivalence class j. Scan through the array, changing each i to j. It takes through the array, changing each i to j. It takes O(N) for one operation and O(NO(N) for one operation and O(N22) for N number of ) for N number of unionunion1010OptimizationsOptimizations•Keep all the elements that are in the same Keep all the elements that are in the same equivalence class in a linked list.equivalence class in a linked list.•By tracking the size of each equivalence class, By tracking the size of each equivalence class, we, when “union”, change the name of the we, when “union”, change the name of the smaller equivalence class to the larger. Thus the smaller equivalence class to the larger. Thus the total time spent for N “union” is O(NlogN). Using total time spent for N “union” is O(NlogN). Using this strategy, any sequence of M finds and up to this strategy, any sequence of M finds and up to N-1unions takes at most O(M+NlogN) time.N-1unions takes at most O(M+NlogN) time.1111121213131414The O(M+N) algorithmThe O(M+N) algorithmClass DisjSetsClass DisjSets{{pubic: pubic: explicit DisjSets(int numElements);explicit DisjSets(int