M A B POW CSE 326 Data Structures Part 7 o u D e c n le a iv u q E The Dynamic n io s s re p m o C th a P Weighted Union W ha ck Henry Kautz Autumn Quarter 20 02 ZING Today s Outline Making a good maze Disjoint Set Union Find ADT Up trees Weighted Unions Path Compression What s a Good Maze What s a Good Maze 1 Connected 2 Just one path between any two rooms 3 Random The Maze Construction Problem Given collection of rooms V connections between rooms initially all closed E Construct a maze collection of rooms V V designated rooms in i V and out o V collection of connections to knock down E E such that one unique path connects every two rooms The Middle of the Maze So far a number of walls have been knocked down while others remain Now we consider the wall between A and B Should we knock it down When should we not knock it A B Maze Construction Algorithm While edges remain in E Remove a random edge e u v from E How can we do this efficiently If u and v have not yet been connected add e to E mark u and v as connected How to check connectedness efficiently Equivalence Relations An equivalence relation R must have three properties reflexive symmetric transitive Connection between rooms is an equivalence relation Why Equivalence Relations An equivalence relation R must have three properties reflexive for any x xRx is true symmetric for any x and y xRy implies yRx transitive for any x y and z xRy and yRz implies xRz Connection between rooms is an equivalence relation any room is connected to itself if room a is connected to room b then room b is connected to room a if room a is connected to room b and room b is connected to room c then room a is connected to room c Disjoint Set Union Find ADT name of set Union Find operations create destroy union find find 4 1 4 8 8 6 7 2 3 6 5 9 10 union 3 6 Disjoint set partition property every element of a DS U F structure belongs to exactly one set with a unique name Dynamic equivalence property Union a b creates a new set which is the union of the sets containing a and b 2 3 Example Construct the maze on the right Initial the name of each set is underlined a b c d e f g h i a 3 2 d g 10 1 4 11 Randomly select edge 1 b e 6 7 9 12 h c f 8 5 Order of edges in blue i Example First Step a b c d e f g h i find b b find e e find b find e so add 1 to E union b e a b e c d f g h i a 3 2 d 10 1 4 11 g b e 6 7 9 12 h c f 8 5 Order of edges in blue i Example Continued a b e c d f g h i a 3 b 10 2 d 6 4 11 g c e 7 9 12 h f 8 5 Order of edges in blue i Up Tree Intuition Finding the representative member of a set is somewhat like the opposite of finding whether a given key exists in a set So instead of using trees with pointers from each node to its children let s use trees with a pointer from each node to its parent Up Tree Union Find Data Structure Each subset is an up tree with its root as its representative member All members of a given set are nodes in that set s upd tree Hash table maps input data to the node associated with that data a c b f g h i e Up trees are not necessarily binary Find find f find e a d c b f g h i a b 10 c d e 11 9 8 g 12 h i 7 e runtime Just traverse to the root f Union union a c a d c b f g h i a b 10 c d e f 11 9 8 g 12 h i e runtime Just hang one root from the other For Your Reading Pleasure a The Whole Example 1 11 3 2 d 4 11 union b e c 1 6 e b c d a b c d e 7 9 g 12 h a e b 10 f 8 5 f g h i f g h i i a The Whole Example 2 11 a b 10 2 d 11 union a d 3 6 4 e c d f g h i f g h i e a b d c e 7 9 g 12 h b c f 8 5 i a The Whole Example 3 11 3 d union a b 4 d e c f g h 7 9 g 12 h b 5 e b c d e f g h f 8 i a c 6 11 a b 10 i i a The Whole Example 4 11 b 10 6 d 11 find d find e No union 4 e b c f g h 7 9 g 12 h a c f 8 5 i i d e While we re finding e could we do anything else a The Whole Example 5 11 union h i a b c d e b 10 6 d e 11 9 7 g h i a b c d e f g f 8 g 12 h f c 5 h i i a The Whole Example 6 11 b c d e f g h i a b e d e 11 9 8 g 12 h i c d c 6 union c f a b 10 g f 7 h i f The Whole Example 7 11 find e find f union a c a b c d g f h Could we do a better job on this union b 10 c d e f 11 9 8 g 12 h i c a i e a b f d e g h i 7 The Whole Example 8 11 find f find i union c h c a b f d e g h a b 10 c d e f 11 9 8 g 12 h i c a i b f d e g h i The Whole Example 9 11 find e find h and find b find c So no unions for either of these c a b f d e a b 10 c d e f 11 9 g 12 h g h i i The Whole Example 10 11 find d find g union c g f g d e c d e f g 12 h i g c h a b b 11 c a a i b …