Disjoint Set Operations.pdf

3 Pages
Unlock Document

Computer Science
Anna Bretscher

Disjoint Set Operations Abstract Data Structure: A collection of nonempty disjoint dynamic sets -> S = S , S1, 2.., S k -Each set is a representative (member of the set) - Only care about getting the same number when asked for a representative of a dynamic set twice without modifying the set Since we represent each element of a set by an object (this being x) we have the following operations 1) Make_Set(x)  Creates new set whose only member is x (the representative)  Because its disjoint, we need to make sure x does not belong in another set 2) Union(x, y)  Unites set x and y, Sxand S ynto new set  Assume that these sets are disjoint before operation  Sx∪ S y  After union, sets get destroyed conceptionally -> S axd S reyoved from S  One becomes absorbed into another 3) Find_Set(x)  Returns pointer to representative of unique set containing x Finding connected components: For all v in V do MAKE-SET(v) For all (u,v) in E do UNION(u,v) Linked-List Representation of Disjoint Sets A linked list is a way to implement a disjoint-set data structure  Each object in the list contains a set member,  A pointer to the next object in list and  Pointer back to set object - The representative is the set member in first object in litst Make_Set and Find_Set takes O(1) time - Make_Set(x) – creates new linked list & therefore is the only object x thus O(1) time - Find_Set(x) – follows pointer from x back to set object and returns member in object that head points to Find_Set(g) – would return f (the representative) Union(x, y) takes ϴ(n) time (AMORTIZED) - Performed by adding y’s list to end of x’s list - Representative of x’s list becomes representative of resulting set - Tail pointer for x has to find ad append y’s list which causes pointer to update to set object for each object in y’s list (takes linear time in length of y’s list) Disjoint-Set Forests -Can be represented by rooted trees with each node containing 1 member & each tree representing 1 set -Each member points only to its parent 3 Operations are performed: 1) Make_Set – creates tree with one node 2) Find_Set – follows parent pointers until root of tree is found - Nodes visited in path constitute find path 3) Union – causes root of one tree to point root of the other Before (2 SETS)
More Less

Related notes for CSCB63H3

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.