DOC PREVIEW
WSU CPTS 223 - Disjoint Sets

This preview shows page 1-2-3-18-19-37-38-39 out of 39 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Disjoint SetsDisjoint SetsEquivalence RelationEquivalence ClassDisjoint SetsDisjoint SetsDisjoint SetsDisjoint SetsDisjoint SetsDisjoint SetsDisjoint SetsDisjoint SetsExampleExample (cont.)ImplementationImplementationImplementationImplementationAnalysisSmart UnionSmart Union ExampleSmart Union by HeightSmart Union by Height ExampleSmart Union by Height ImplementationPath CompressionPath Compression ExamplePath Compression ImplementationPath Compression with Smart UnionAnalysis of Union-by-Rank and Path CompressionAckermann’s FunctionInverse of Ackermann’s FunctionAnalysis of Union-by-Rank and Path CompressionApplication: Maze GenerationMaze Generation ExampleMaze Generation ExampleMaze Generation ExampleMaze Generation ExampleMore ApplicationsSummary111111Disjoint SetsCptS 223 – Advanced Data StructuresLarry HolderSchool of Electrical Engineering and Computer ScienceWashington State UniversityDisjoint Sets Data structure for problems requiring equivalence relations I.e., Are two elements in the same equivalence class Applications Reachability of components in a graph Disjoint sets provide a simple, fast solution Simple: array-based implementation Fast: O(1) per operation average case Analysis is challenging2Equivalence Relation Relation R on set S maps pairs of elements of S to true or false For all a,b ∈ S, (a R b) Æ {true,false} Equivalence relation is a relation R such that the following hold R is reflexive: (a R a) for all a ∈ S R is symmetric: (a R b) ⇔ (b R a) R is transitive: (a R b) and (b R c) Æ (a R c) Example: Equality over integers3Equivalence Class Given set S and equivalence relation R Find the subsets Siof S such that For all a,b ∈ Si: (a R b) For all a ∈ Si, b ∈ Sj, i ≠ j: not (a R b) These Siare the equivalence classes of S for relation R The Siare “disjoint sets” Example: S = {1,2,3,4,3,3,2,1,3}, R is =4Disjoint Sets Main operation Determine if a and b are in the same equivalence class Approach Put each element of S in a disjoint set of its own If a and b are related, then union the sets containing a and b5Disjoint Sets Example S = {1a, 2a, 3a, 4a, 3b, 3c, 2b, 1b, 3d} DS = { {1a}, {2a}, {3a}, {4a}, {3b}, {3c}, {2b}, {1b}, {3d} } 3aR 3b?, 3cR 3d? DS = { {1a}, {2a}, {3a,3b}, {4a}, {3c,3d}, {2b}, {1b} } 3aR 3c? DS = { {1a}, {2a}, {3a,3b,3c,3d}, {4a}, {2b}, {1b} }6Disjoint Sets Operations Find(a) Returns a representative of the equivalence class containing a Union(Si,Sj) Creates a new set Sk= SiU Sj Associates single representative to all elements of Sk Assume each element can be associated with a unique integer 0 to N-17Disjoint Sets Solution #1 Maintain an array of size N containing the representative of each element Find is a O(1) lookup Union(a,b) Assuming a in class i and b in class j Scan array, changing all i’s to j’s O(N) per union (how many unions?) Okay if Ω(N2) find operations O(1) per union/find operation8Disjoint Sets Solution #2a Maintain a linked list for each equivalence class Increases time to find an element Decreases time for unions by not having to search all N elements Just the two lists where the elements are found And then concatenate lists: O(size of larger list) Still, Θ(N2) performance in worst case9Disjoint Sets Solution #2b Maintain a linked list for each equivalence class Also maintain size of each class (list) Union always concatenates the smaller to the larger class (list) Thus, N-1 unions cost O(N log N) (why?) Any sequence of M finds and N-1 unions takes time O(M + N log N)10Disjoint Sets Performance Can ensure O(1) worst-case time for find operation Or, can ensure O(1) worst-case time for union operation But not both Solution #3 Fast unions, slow finds But, achieves O(M+N) time for any sequence of M finds and N-1 unions11Disjoint Sets Solution 3 Represent each set as a tree Tree’s root is the representative element for the set Disjoint sets are a forest of trees Find(a) returns root element of tree containing a Union(a,b) points root node of tree containing b to root node of tree containing a Implemented as array s, where s[i] = index of parent node in tree (or -1 if root)12Example13Initial disjoint sets of 8 elements (really an array of size 8 of all -1s):After union(4,5):Example (cont.)14After union(6,7):After union(4,6):Implementation15Implementation16Implementation17Implementation18Analysis Find(x) Proportional to depth of tree containing x Deepest tree? Worst-case running time O(N) M consecutive find operations O(MN) worst case Average case analysis What is the average case? Unions can still cost O(N2) But we can do better…19Smart Union Union by size Link smaller tree to larger tree Maximum node depth is (log2N) (why?) Find(x) running time? Sequence of M operations requires O(M) time Random unions tend to merge large sets with small sets Thus, only increase depth of smaller set Implementation Use (- size) instead of -1 for root entries20Smart Union Example21Union(3,4)Smart-Union(3,4)-1 -1 -1 4 -5 4 4 60 1 2 3 4 5 6 7Smart Union by Height Keep track of height of each tree, rather than size Union: Link smaller-height tree to larger-height tree Height only increases when two equal-height trees joined Still O(log N) maximum depth Still O(M) time for M operations Implementation Store (negative of height) minus 122Smart Union by HeightExample23-1 -1 -1 4 -3 4 4 60 1 2 3 4 5 6 7Smart Union by Height Implementation24Path Compression Smart union achieves O(M) time for M operations (average case) But still O(M log N) in the worst case Path compression All nodes accessed during a Find(x) are linked directly to the root Path compression without smart union still O(M log N) worst case25Path Compression Example26After Find(14):Path Compression Implementation27Path Compression withSmart Union Path compression works as is with union-by-size (tree sizes don’t change) Path compression with union-by-height requires re-computation of heights Solution: Don’t recompute heights Heights become (possibly over) estimates of true height Also called “ranks” and this solution is called “union-by-rank” Ranks are modified far less than sizes, so slightly faster in


View Full Document

WSU CPTS 223 - Disjoint Sets

Download Disjoint Sets
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Disjoint Sets and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Disjoint Sets 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?