Transcript PowerPoint Presentation - Topology Based Methods in Shape

CSE 2331/5331
Extra topic:
Union-find:
Operations
Linked-list rep.
Disjoint forest rep.
CSE 2331/5331 Algorithms
Dynamic Disjoint Sets

Maintain collection of dynamic disjoint sets


Each set has a representative


Does not matter who is the representative
Operations:



Make-Set(x)
Find-Set(x)
Union(x, y)
Example

Connected component (CC) of graph G = (V, E)


Two nodes in the same CC if there is a path connecting
them in G
Build a data structure for CC of G,

As well as enabling future CC-query
Remarks

Representatives don’t matter


Sometimes simple requirements for reps can be
satisfied
Maintain dynamic sets when only adding and
merging happen

Compare to previous data structures
Linked-list Representation

Each set represented by a singly-linked list


head/tail
Every node in a set:



pointer to next in the list
pointer to representative of the set
Other info.
Operations

Make-Set(x):


Find-Set(x):


Create a singleton list
Return the representative of the set
Union(x, y):


O (1)
O (1)
O (size of list y)
Need to first do Find-Set(x) and Find-Set(y)
x’stwo
listreturned
onto endset
of y’s list
ThenAppend
union the
using head/tail pointers
Update representative pointer for
each element in x’s list
Analysis


A sequence of m operations
n : total number of elements throughout


#Make-Sets = n
#Union ≤ n
Straightforward:
O ( nm )
Does averaging analysis help?
No.. Can have  (n^2) for m =  (n)
A Different Representation

Disjoint-set forests



Represent each set as a tree
Root of the tree as representative of the set
Operations:


O(1)
Make-Set(x): make a singleton tree
Find-Set(x): return the root
O(path-to-root)


Perform Find-Path operation
Union(x, y): root of x becomes a child of root of y
O(1)
Example
Analysis

Straightforward: O(nm)

Find-Set(x) can be costly


Does amortized analysis help?


worst case: a tree is a path
No
One solution

Union by weight as well
Union by weight

Consider the worst case example


A weighted-union heuristic



cost comes from update representative pointer
weight(a set) = size of the set
Always append list of smaller weight to the larger one
Observation:

An element cannot update its pointer too often
Union by Weight


After n union operations
Height of tree = O(log n) !
CSE 2331/5331
Pseudocode with Heuristics
Conclusion

By using disjoint-set forest representation for
maintaining dynamic disjoint set, together with the
union-by-rank and path-compression heuristics, a
sequence of m operations takes O(m  (m, n) )
amortized time to complete.
CSE 780 Algorithms