Lecture 8: Disjoint Sets
Felipe Vicencio-Heap July 21, 2020
Suppose we want to track a finite universe of objects, partition the objects into a finite number of sets, and check which objects are in the same set.
We can define the ADT as follows: • A set of objects
•
•
•
1
Applications:
• Computer networks
• Web pages on the internet
• Components (transistors) in a computer
• Physical systems •
•
2
For convenience we can label them with the elements of [0..n − 1]. Like with Dictionaries we can ignore the actual objects being stored, and treat the integer labels as pointers.
For example start with 0123456789
That is 10 insert operations, followed by the union operations: • union(3,9)
• union(8,4) • union(2,3) • union(5,6)
Find query: are 2 and 9 in the same set?
3
Goal: design an efficient data structure to perform union-find.
• Operations could be intermixed (adding elements, unions, finds) • Number of operations M could be huge.
• Number of elements N could be huge.
Introducing the Disjoint Set ADT:
Objects: a finite collection of disjoint, non-empty sets S = {S1,…,Sk}. Each set is identified by a unique, (possibly arbitrarily chosen), representative. Operations:
• Make-Set(x): Given a new element x, add the singleton {x} with repre- sentative x to S
• Find-Set(x): Given an element x, return the representative of the set containing x in S, or Nil if x doesn’t appear in any of the sets in S.
• Union(x,y): Given distinct x and y, let Sx be the set containing x and Sy be the set containing y. Create a new set Sx ∪ Sy and add it to the collection, and remove Sx and Sy from the collection. Pick a new representative from the set.
If x and y are already in the same set do nothing.
4
Important use case: Kruskal’s algorithm (we’ll talk about graphs later!)
KRUSKAL-MST(G=(V,E),w:E->R)
T <- {}
sort edges so w(e_1) <= w(e_2) <= ... <= w(e_m)
for each v in V:
Make-Set(v)
for i <- 1 to m:
# let (u_i,v_i) = e_i
if Find-Set(u_i) != Find-Set(v_i):
Union(u_i,v_i)
T <- T u {e_i}
5
How do we implement it efficiently?
6
1. Circular linked lists
7
2. Linked list with representative pointers
8
3. Linked list with representative pointers, union-by-weight
9
4. Inverted trees
10
5. Inverted trees, union by weight
11
6. Inverted trees, path compression
12
7. Inverted tree, union by rank, path compression
13