Transcript lee-chap21
Chapter 21
Data Structures for Disjoint Sets
Lee, Hsiu-Hui
Ack: This presentation is based on the lecture slides
from Prof. Tsai, Shi-Chun as well as various materials
from the web.
.
Disjoint-set Data Structure
•
To maintain a collection of disjoint dynamic sets
S = {S1, S2, …, Sk}.
Each set Si is identified by a representative x=rep[Si].
•
Operations:
MAKE-SET(x): creates a new set whose only member is x.
with rep[{x}] = x (for any x ∉ Si for all i).
UNION(x, y): replaces sets Sx, Sy with Sx ∪ Sy in S
for any x, y in distinct sets Sx, Sy .
FIND-SET(x): returns representative of set Sx containing x.
20080111 chap21
Hsiu-Hui Lee
2
Connected Component:
an application
a
b
e
c
d
g
f
h
j
i
(a)
20080111 chap21
Hsiu-Hui Lee
3
CONNECTED-COMPONENTS(G)
1 for each vertex v V[G]
2
do MAKE-SET(v)
3 for each edge (u,v) E[G]
4
do if FIND-SET(u) ≠ FIND-SET(v)
5 then UNION(u,v)
SAME-COMPONENT(u,v)
1 if FIND-SET(u) = FIND-SET(v)
2
then return TRUE
3
else return FALSE
20080111 chap21
Hsiu-Hui Lee
4
Linked-list representation
of disjoint sets
The first object in each linked list
serve as its set’s representative
20080111 chap21
Hsiu-Hui Lee
5
MAKE-SET(x) : O(1)
FIND-SET(x) : O(1)
UNION(x, y) : by appending x’s list onto the end of y’s list
UNION (e, g)
20080111 chap21
Hsiu-Hui Lee
6
A simple implementation
of union
m: # of operation = 2n-1
Amortized time : Θ (n)
Θ(n)
Θ (1+2+...+n)
=Θ (n2)
20080111 chap21
Hsiu-Hui Lee
7
A weight-union heuristic
• In simple implementation of union, we may be
appending a longer list onto a shorter list
• Weighted-union heuristic
To append the smaller list onto the longer
20080111 chap21
Hsiu-Hui Lee
8
Theorem 21.1
• Using the linked-list representation of disjoint
sets and the weight-union heuristic, a sequence
of m MAKE-SET, UNION, and FIND-SET
operations, n of which are MAKE-SET
operations, takes O( m + n lg n) time.
20080111 chap21
Hsiu-Hui Lee
9
Disjoint-set forests
• We represent sets by rooted trees.
• Each node contains one member and each tree
represents one set.
• In a disjoint-set forest, each member points to
its parent.
20080111 chap21
Hsiu-Hui Lee
UNION (e, g)
10
Heuristics to improve
the running time
• Union by rank
The root with smaller rank is made to point to
the root with larger rank during a UNION
operation
• Path compression
During FIND-SET, to make each node on the
find path point directly to the root.
20080111 chap21
Hsiu-Hui Lee
11
Before FIND-SET(a)
20080111 chap21
Hsiu-Hui Lee
After FIND-SET(a)
12
Pseudo code for
disjoint-set forests
MAKE-SET(x)
1 p[x] x
2 rank[x] 0
path compression
UNION(x, y)
1 LINK(FIND-SET(x), FIND-SET(y))
20080111 chap21
Hsiu-Hui Lee
13
LINK(x, y)
union by rank
1 if rank[x] > rank[y]
2 then p[y] x
3 else p[x] y
4
if rank[x] = rank[y]
5
then rank[y] rank[y] + 1
FIND-SET(x)
1 if x ≠ p[x]
2 then p[x] FIND-SET(p[x])
3 return p[x]
20080111 chap21
Hsiu-Hui Lee
14
Effect of the heuristics
• Either union by rank or path
compression improves the running time.
O(m lg n)
--- union by rank
Θ(n + f ‧ (1+log2+f/nn)) --- path comprsssion
• The improvement is greater when the
two heuristics are used together.
O(m (n))
20080111 chap21
--- both
Hsiu-Hui Lee
15