CSE310 Lecture 13 Disjoint Set Operations Guoliang Larry Xue Computer Science and Engineering Arizona State University http optimization asu edu xue Guoliang Xue asu edu Topics of this lecture Disjoint Sets Operations on Disjoint sets Applications Tree Representation and Array Implementations Union by Rank Find with Path Compression Amortized Analysis 2 Guoliang Xue asu edu Data Structure for Disjoint Sets A disjoint set data structure maintains a collection set S S1 S2 Sk of disjoint dynamic sub sets Each element x of a set is a pointer to an object possibly with multiple fields Representative of a set We choose one element of a set to identify the set e g we use the root of a tree to identify a tree or the head element of a linked list to access the linked list Operations on this data structure An application Implementation using linked lists and rooted trees Running time 3 Guoliang Xue asu edu Operations on Disjoint Sets Make Set x creates a new set whose only member is x Obviously x is the representative Union x y replaces the two sets Sx and Sy that contain elements x and y by their union Sets are assumed to be disjoint no element overlap The representative of Sx or Sy becomes the representative of the united set Find Set x returns the pointer to the representative of the unique set containing x 4 Guoliang Xue asu edu Understanding Disjoint Set via an Example Assume we have an undirected graph G V E consisting of a number of subgraphs that are not connected to each other a b c d e f h g i How do we store a graph in a computer Standard methods Adjacency matrix e g a 9x9 matrix 1 1 1 1 1 1 1 1 G 1 1 1 1 1 1 1 1 Set G V E V a b i E a b a c b c d e d g e f e g h i We can use disjoint set to determine whether a graph is connected and whether two vertices are in the same connected component 5 Guoliang Xue asu edu Algorithm Finding Connected Components Connected Components G n 1 2 n 1 n 3 2 4 5 Same Components u v for each vertex v V G do Make Set v for each edge u v E G do if Find Set u Find Set v 1 if Find Set u Find Set v 2 then return TRUE 3 else return FALSE then Union u v edge processed initial sets a b a c b c d e d g e f e g h i collection of disjoint sets a b c d e f g h a b c d e f g h a b c d e f g h i i i Find Set b Find Set c a b c a b c a b c d e d e g d e g f f f g h h h i i i Find Set e Find Set g a b c d e g f 6 h i Guoliang Xue asu edu three disjoint sets Tree View We can use a forest to represent disjoint sets The root is the representative How to perform Make Set How to perform Find x How to perform Union x y What are the time complexities How do we represent the forest 7 Guoliang Xue asu edu Array Implementation of Disjoint Sets We use a linear array A with index from 1 to n to implement disjoint sets on the first n numbers Make Set x is accomplished by A x 0 x is the root the rank of the tree at x is 0 A x 0 indicates that x is not the root and that the parent of x is at location A x A x 0 indicates that x is the root and that the rank of the tree rooted at x is A x 8 Guoliang Xue asu edu Array Implementation of Disjoint Sets 0 0 0 0 0 0 0 0 1 1 1 3 1 5 1 7 9 Guoliang Xue asu edu Array Implementation of Disjoint Sets Link x y is accomplished by if A x A y then x has a higher rank than y A y x else if A x A y then A y A y 1 rank of y is incremented A x y If the two trees have the same rank we choose y as the root and increment its rank If the two trees have different ranks we favor the tree with a higher rank 10 Guoliang Xue asu edu Array Implementation of Disjoint Sets Find Set1 x is accomplished by if A x 0 then return x else return Find Set1 A x Union1 x y is accomplished by Link Find Set1 x Find Set1 y 11 Guoliang Xue asu edu Height of the trees THEOREM Let n be the number of nodes in a tree and let r be the rank of the tree Assuming we are using union by rank then n 2r Proof This is true when r 0 n 1 When we are taking the union of two trees with different ranks the number of nodes is increased but the rank stays the same When we are taking the union of two trees with the same rank the number of nodes in the new tree is at least 2 2r but the new rank is r 1 12 Guoliang Xue asu edu Example rank b log 3 1 a c f b b UNION a b UNION c e d e rank a rank b rank e log 1 0 e a c d f b UNION b f a e f c d UNION b e rank b rank e log 2 1 e c a b e UNION a d d f 13 rank e log 5 2 b c a d f Guoliang Xue asu edu m total number of operations MAKE SET UNION FIND n total number of MAKE SET operations Union by rank heuristic worst case total running time for all m operations is m log n Why It is not hard to see that the total running time is O m log n We just need to show that a tree representing a set with k elements has height log k since the maximum height of a tree is an upper bound on the running time of any of the three operations How do we show that the height of a tree with k elements is log k 14 Guoliang Xue asu edu Use induction on number of elements in a tree y log k1 x log k2 tree with k2 elements tree with k1 elements Base case a tree with one element has height of log 1 0 Resulting tree after UNION operation has k1 k2 elements Height of resulting tree is max log k1 log k2 1 log k1 k2 15 since we are using union by rank Guoliang Xue asu edu Use induction on number of …
View Full Document
Unlocking...