Union Find Preliminary Definitions A set is a collection of objects Set A is a subset of set B if all elements of A are in B Subsets are sets Union of two sets A and B is a set C which consists of all elements in A and B Two sets are mutually disjoint if they do not have a common element A partition of a set is a collection of subsets such that Union of all these subsets is the set itself Any two subsets are mutually disjoint S 1 2 3 4 A 1 2 B 3 4 C 2 3 4 D 4 Is A B a partition of S Is A C partition of S Is A D partition of S A partition of a set is a collection of subsets such that Union of all these subsets is the set itself Any two subsets are mutually disjoint S 1 2 3 4 A 1 2 B 3 4 C 2 3 4 D 4 Is A B a partition of S Yes Is A C partition of S No Is A D partition of S No Disjoint Set Operations A disjoint set data structure Maintains a collection S S1 Sk of disjoint dynamic sets Each set is identified by a representative which is some member of the set In some applications It doesn t matter which member is used as the representative We only care that if we ask for the representative of a set twice without modifying the set between the requests we get the same answer both times 4 Disjoint Set Operations In other applications There may be a prescribed rule for choosing the representative E G Choosing the smallest member in the set Each element of a set is represented by an object x MAKE SET x creates a new set whose only member is x Object x is the representative of the set x is not already a member of any other set UNION x y unites the dynamic sets S Sy that contain x y S Sy are assumed to be disjoint prior to the operation The new representative is some member of S Sy 5 Disjoint Set Operations Usually the representative of either S ORSy is chosen as the new representative We destroy sets S Sy removing them from the collection S since we require the sets in the collection to be disjoint FIND SET x returns a pointer to the representative of the unique set containing x We will analyze the running times in terms of two parameters n The number of MAKE SET operations m The total number of MAKE SET UNION and FIND SET operations 6 Disjoint Set Operations Each union operation reduces the number of sets by one since the sets are disjoint Therefore only one set remains after n 1 union operations Thus the number of union operations is n 1 Also note that m n always hold since MAKE SET operations are included in the total number of operations 7 An Application of Disjoint Set Data Structures Determining the connected components of an undirected graph G V E a b e c d g Initial a b h f j i c d e f g h i j 8 An Application of Disjoint Set Data Structures Determining the connected components of an undirected graph G V E a b e c d g h f j i Initial a b c b d a b d c d e f g h i j e f g h i j 9 An Application of Disjoint Set Data Structures Determining the connected components of an undirected graph G V E a b e c d g Initial a b b d a e g a h f j i c d e f g h i j b d c e f g h i j b d c e g f h i j 10 An Application of Disjoint Set Data Structures Determining the connected components of an undirected graph G V E a b e c d g h f j i Initial a b c b d a b d c e g a c a b d c a c b d d e f g h i j e f g h i j e g f e g f h i j h i j 11 An Application of Disjoint Set Data Structures Determining the connected components of an undirected graph G V E a b e c d g h f j i Initial a b c b d a b d c e g a c h i a b d c a c b d a c b d d e f g h i j e f g h i j e g f e g f e g f h i j h i j h i j 12 An Application of Disjoint Set Data Structures Determining the connected components of an undirected graph G V E a b e c d g h f j i Initial a b c b d a b d c e g a b d c a c a c b d h i a c b d a b a b c d d e f g h i j e f g h i j e g e g e g e g f f f f h i h i h i h i j j j j 13 An Application of Disjoint Set Data Structures Determining the connected components of an undirected graph G V E a b e c d g h f j i Initial a b c b d a b d c e g a b d c a c a c b d h i a c b d a b a b c d e f a b c d j d e f g h i j e f g h i j e g f e g f e g f e g f e f g h i h i h i h i h i j j j j 14 An Application of Disjoint Set Data Structures Determining the connected components of an undirected graph G V E a b e c d g h f j i Initial a b c b d a b d c e g a b d c a c a c b d h i a c b d a b a b c d e f a b c d j b c a b c d d e f g h i j e f g h i j e g f e g f e g f e g f e f g e f g h i h i h i h i h i h i j j j j j 15 An Application of Disjoint Set Data Structures Determining the connected components of an undirected graph G V E CONNECTED COMPONENTS G for each vertex v V G do MAKE SET v endfor for each edge u …
View Full Document
Unlocking...