CSE 326 Data Structures Disjoint Union Find Equivalence Relations Relation R For every pair of elements a b in a set S a R b is either true or false If a R b is true then a is related to b An equivalence relation satisfies 1 Reflexive a R a 2 Symmetric a R b iff b R a 3 Transitive a R b and b R c implies a R c 2 A new question Which of these things are similar grapes blackberries plums apples oranges peaches raspberries lemons If limes are added to this fruit salad and are similar to oranges then are they similar to grapes How do you answer these questions efficiently 3 Equivalence Classes Given a set of things grapes blackberries plums apples oranges peaches raspberries lemons bananas define the equivalence relation All citrus fruit is related all berries all stone fruits and THAT S IT partition them into related subsets grapes blackberries raspberries oranges lemons plums peaches apples bananas Everything in an equivalence class is related to each other 4 Determining equivalence classes Idea give every equivalence class a name oranges limes lemons like ORANGES peaches plums like PEACHES Etc To answer if two fruits are related FIND the name of one fruit s e c FIND the name of the other fruit s e c Are they the same name 5 Building Equivalence Classes Start with disjoint singleton sets apples bananas peaches As you gain information about the relation UNION sets that are now related peaches plums apples bananas E g if peaches R limes then we get peaches plums limes oranges lemons 6 Disjoint Union Find Maintain a set of pairwise disjoint sets 3 5 7 4 2 8 9 1 6 Each set has a unique name one of its members 3 5 7 4 2 8 9 1 6 7 Union Union x y take the union of two sets named x and y 3 5 7 4 2 8 9 1 6 Union 5 1 3 5 7 1 6 4 2 8 9 8 Find Find x return the name of the set containing x 3 5 7 1 6 4 2 8 9 Find 1 5 Find 4 8 9 Example S 1 2 7 8 9 13 19 3 4 5 6 10 11 17 12 14 20 26 27 15 16 21 22 23 24 29 39 32 33 34 35 36 Find 8 7 Find 14 20 Union 7 20 S 1 2 7 8 9 13 19 14 20 26 27 3 4 5 6 10 11 17 12 15 16 21 22 23 24 29 39 32 33 34 35 36 10 Cute Application Build a random maze by erasing edges 11 Cute Application Pick Start and End Start End 12 Cute Application Repeatedly pick random edges to delete Start End 13 Desired Properties None of the boundary is deleted Every cell is reachable from every other cell There are no cycles no cell can reach itself by a path unless it retraces some part of the path 14 A Cycle Start End 15 A Good Solution Start End 16 A Hidden Tree Start End 17 Number the Cells We have disjoint sets S 1 2 3 4 36 each cell is unto itself We have all possible edges E 1 2 1 7 2 8 2 3 60 edges total Start 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 End 18 Basic Algorithm S set of sets of connected cells E set of edges Maze set of maze edges initially empty While there is more than one set in S pick a random edge x y and remove from E u Find x v Find y if u v then Union u v else add x y to Maze All remaining members of E together with Maze form the maze 19 Example Step Pick 8 14 Start 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 End S 1 2 7 8 9 13 19 3 4 5 6 10 11 17 12 14 20 26 27 15 16 21 22 23 24 29 30 32 33 34 35 36 20 Example S 1 2 7 8 9 13 19 3 4 5 6 10 11 17 12 14 20 26 27 15 16 21 22 23 24 29 39 32 33 34 35 36 Find 8 7 Find 14 20 Union 7 20 S 1 2 7 8 9 13 19 14 20 26 27 3 4 5 6 10 11 17 12 15 16 21 22 23 24 29 39 32 33 34 35 36 21 Example Pick 19 20 Start 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 End S 1 2 7 8 9 13 19 14 20 26 27 3 4 5 6 10 11 17 12 15 16 21 22 23 24 29 39 32 33 34 35 36 22 Example at the End S 1 2 3 4 5 6 7 36 Start 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 E Maze End 23 Implementing the DS ADT n elements Total Cost of m finds n 1 unions Target complexity O m n i e O 1 amortized O 1 worst case for find as well as union would be great but Known result find and union cannot both be done in worst case O 1 time 24 Implementing the DS ADT Observation trees let us find many elements given one root Idea if we reverse the pointers make them point up from child to parent we can find a single root from many elements Idea Use one tree for each equivalence class The name of the class is the tree root 25 Up Tree for DU F Initial state Intermediate state 1 2 3 1 4 5 6 3 7 2 Roots are the names of each set 7 5 4 6 26 Find Operation Find x follow x to the root and return the root 1 3 7 2 Find 6 7 5 4 6 27 Union Operation Union i j assuming i and j roots point i to j Union 1 7 1 3 7 2 5 4 6 28 Simple Implementation Array of indices Up x 0 means x is a root 1 2 3 4 5 6 7 up 0 1 0 7 7 5 0 1 3 7 2 5 4 6 29 Union Union up integer array x y integer precondition x and y …