Lecture 19: Disjoint Sets

CSE 373: Data Structures and Algorithms

1

CSE 373 23SU

CSE 373 23SU

1

Warmup

KruskalMST(Graph G)

initialize each vertex to be an independent component

sort the edges by weight

foreach(edge (u, v) in sorted order){

if(u and v are in different components){

add (u,v) to the MST

update u and v to be in the same component

}

}

Run Kruskal’s algorithm on the following graph to find the MST (minimum spanning tree) of the graph below.

Below is the provided pseudocode for Kruksal’s algorithm to choose all the edges.

CSE 373 23SU

2

Announcements

• Ex 5 due Monday 8/7 at 11:59PM
• P4 due 8/18 at 11:59PM
• Extra credit survey out! Due tonight!
• worth 0.1 final GPA boost!
• survey link: https://forms.gle/o5cCL4R9LU3ii2qy8

CSE 373 23SU

3

Disjoint Sets

CSE 373 23SU

4

Selecting an ADT

Kruskal’s needs to find what MST a vertex belongs to, and union those MSTs together

• Our existing ADTs don’t lend themselves well to “unioning” two sets…
• Let’s define a new one!

kruskalMST(G graph)

Set(?) msts; Set finalMST;

initialize msts with each vertex as single-element MST

sort all edges by weight (smallest to largest)

​

for each edge (u,v) in ascending order:

uMST = msts.find(u)

vMST = msts.find(v)

if (uMST != vMST):

finalMST.add(edge (u, v))

msts.union(uMST, vMST)

CSE 373 23SU

5

Disjoint Sets ADT (aka “Union-Find”)

Kruskal’s will use a Disjoint Sets ADT under the hood

• Conceptually, a single instance of this ADT contains a “family” of sets that are disjoint (no element belongs to multiple sets)

kruskalMST(G graph)

DisjointSets<V> msts; Set finalMST;

initialize msts with each vertex as single-element MST

sort all edges by weight (smallest to largest)

​

for each edge (u,v) in ascending order:

uMST = msts.find(u)

vMST = msts.find(v)

if (uMST != vMST):

finalMST.add(edge (u, v))

msts.union(uMST, vMST);

CSE 373 23SU

6

Disjoint Sets in mathematics

“In mathematics, two sets are said to be disjoint sets if they have no element in common.” - Wikipedia

disjoint = not overlapping

​

​

Kevin

Aileen

Keanu

Sherdil

Leona

These two sets are disjoint sets

Nishu

Santino

Brian

These two sets are not disjoint sets

Santino

Set #1

Set #2

Set #3

Set #4

CSE 373 23SU

7

Disjoint Sets in computer science

In computer science, disjointsets can refer to this ADT/data structure that keeps track of the multiple “mini” sets that are disjoint

​

This overall grey blob thing is the actual

disjoint sets, and it’s keeping track of any number of mini-sets, which are all disjoint (the mini sets have no overlapping values).

Note: this might feel really different than ADTs we’ve run into before. The ADTs we’ve seen before (dictionaries, lists, sets, etc.) just store values directly.

But the Disjoint Set ADT is particularly interested in

letting you group your values into sets and

keep track of which particular set your values are in.

new ADT!

Kevin

Aileen

Keanu

Sherdil

Leona

Set #1

Set #2

CSE 373 23SU

8

New ADT

CSE 373 23SU

9

findSet(value)

findSet(value) returns some ID for which particular set the value is in. For Disjoint Sets, we often call this the representative (as it’s a value that represents the whole set).

​

Examples:

findSet(Brian)

findSet(Sherdil)

findSet(Santino)

findSet(Kevin) == findSet(Aileen)

4

2

3

true

CSE 373 23SU

10

union(valueA, valueB)

union(valueA, valueB) merges the set that A is in with the set that B is in. (basically add the two sets together into one)

Example: union(Kevin, Nishu)

CSE 373 23SU

11

makeSet(value)

makeSet(value) makes a new mini set that just has the value parameter in it.

​

Examples:

makeSet(Elena)

makeSet(Anish)

Elena

Anisha

CSE 373 23SU

12

Example

new()

makeSet(a)

makeSet(b)

makeSet(c)

makeSet(d)

makeSet(e)

findSet(a)

findSet(d)

union(a, c)

CSE 373 23SU

13

Example

new()

makeSet(a)

makeSet(b)

makeSet(c)

makeSet(d)

makeSet(e)

findSet(a)

findSet(d)

union(a, c)

union(b, d)

CSE 373 23SU

14

Example

findSet(a) == findSet(c)

findSet(a) == findSet(d)

new()

makeSet(a)

makeSet(b)

makeSet(c)

makeSet(d)

makeSet(e)

findSet(a)

findSet(d)

union(a, c)

union(b, d)

true

false

CSE 373 23SU

15

Questions?

CSE 373 23SU

16

Disjoint Set Implementation

Weighted Union

Path Compression

Array Implementation

​

​

CSE 373 23SU

17

Implementation

Map<NodeValues, NodeLocations> nodeInventory

SetNode<E> parent

CSE 373 23SU

18

Implementation

Nishu

Santino

Brian

Rahul

TreeDisjointSet<E>

TreeSet<E>

SetNode<E>

1

4

Kevin

Aileen

Keanu

Sherdil

Leona

9

Disjoint Sets are built as a collection of three objects

The TreeDisjointSet<E> is the top level object with two fields:

• Set<TreeSet> forest
• Map with node references

Each TreeSet<E> is a collection of SetNodes<E>

Each SetNode<E> can have an unlimited number of children, but only one parent. Nodes store parents instead of children.

Set<TreeSet> forest =

Map<E, SetNode<E>> nodeInventory =

CSE 373 23SU

19

Implement makeSet(x)

Worst case runtime?

O(1)

forest

• makeSet(0)
• makeSet(1)
• makeSet(2)
• makeSet(3)
• makeSet(4)
• makeSet(5)

CSE 373 23SU

20

Implement find(X)

Key Idea: Jump to the node given. Travel upward to parent until parent field is null, nodes with null parents are roots and their data will act as the representative for the set

How do we jump to a node quickly?

• Store a map from value to its node (Omitted in future slides)

Runtime

• jump to node O(1)
• travel up to root
• based on height of TreeSet
• Worst case: O(n) if TreeSet is degenerate Tree

find(Santino) -> Aileen

find(Ken) -> Joyce

find(Santino) != find(Ken)

find(Santino) == find(Aileen)

find(Ken):

jump to Ken node

travel upward until root Joyce

return root “Joyce”

Paul

Map<E, SetNode<E>> nodeInventory =

CSE 373 23SU

21

Implement union(x, y)

Key idea: easy to simply rearrange pointers to union entire trees together!

• it doesn’t matter what the order of the trees are, only that all the nodes from one tree are connected to the other tree

union(Ken, Santino):

rootK = find(Ken) //Joyce

rootS = find(Santino) //Aileen

set rootK to point to rootS

RESULT:

Paul

CSE 373 23SU

22

Union: Why bother with the second root?

Key idea: keeping the height of each tree short will help minimize runtime for future find(x)

• Pointing directly to the individual element instead of the root can grow the tree height

union(Ken, Santino):

rootK = find(Ken)

rootS = find(Santino)

set rootK to point to rootS

union(Ken, Santino):

rootK = find(Ken)

set rootK to point to Santino

Why not just use:

Height = 3

Height = 4

CSE 373 23SU

23

Union runtime

union(A, B):

rootA = find(A)

rootB = find(B)

set rootA to point to rootB

find(A):

jump to A node

travel upward until root

return ID

A series of calls to union that would create a worst-case runtime for find on these Disjoint Sets:

A

B

C

D

union(A, B)

B

A

C

D

union(B, C)

union(C, D)

find(A)

n runtime :(

CSE 373 23SU

24

Analyzing the union worst case

• How did we get a degenerate tree?
• Even though pointing a root to a root usually helps with this, we can still get a degenerate tree if we put the root of a large tree under the root of a small tree.
• Instead of always putting rootA under rootB what if we could ensure the smaller tree went under the larger tree?

union(C, D)

What currently happens

What would help avoid degenerate tree

CSE 373 23SU

25

Practice

Given the following disjoint-set what would be the result of the following calls on union if we always add the smaller tree (fewer nodes) into the larger tree (more nodes). Draw the forest at each stage with corresponding ranks for each tree.

• union(2, 13)
• union(4, 12)
• union(2, 8)

CSE 373 23SU

26

Practice

Given the following disjoint-set what would be the result of the following calls on union if we add the “union-by-weight” optimization. Draw the forest at each stage with corresponding ranks for each tree.

• union(2, 13)

CSE 373 23SU

27

Practice

Given the following disjoint-set what would be the result of the following calls on union if we add the “union-by-weight” optimization. Draw the forest at each stage with corresponding ranks for each tree.

• union(2, 13)
• union(4, 12)

CSE 373 23SU

28

Practice

Given the following disjoint-set what would be the result of the following calls on union if we add the “union-by-weight” optimization. Draw the forest at each stage with corresponding ranks for each tree.

• union(2, 13)
• union(4, 12)
• union(2, 8)

CSE 373 23SU

29

Practice

Given the following disjoint-set what would be the result of the following calls on union if we add the “union-by-weight” optimization. Draw the forest at each stage with corresponding ranks for each tree.

• Does this improve the worst case runtimes?
• findSet is more likely to be O(log(n)) than O(n)

• union(2, 13)
• union(4, 12)
• union(2, 8)

CSE 373 23SU

30

Disjoint Set Implementation

Weighted Union

Path Compression

Array Implementation

​

​

CSE 373 23SU

31

WeightedUnion

Goal: Always pick the smaller tree to go under the larger tree

Implementation: Store the number of nodes (or “weight”) of each tree in the root

• Constant-time lookup instead of having to traverse the entire tree to count

union(A, B):

rootA = find(A)

rootB = find(B)

put lighter root under heavier root

A

union(A, B)

union(B, C)

union(C, D)

find(A)

weight: 1

B

weight: 1

C

weight: 1

D

weight: 1

2

3

4

O(1) runtime :)

CSE 373 23SU

32

WeightedUnion: Performance

Consider the worst case where the tree height grows as fast as possible

0

CSE 373 23SU

33

WeightedUnion: Performance

Consider the worst case where the tree height grows as fast as possible

0

1

CSE 373 23SU

34

WeightedUnion: Performance

Consider the worst case where the tree height grows as fast as possible

0

1

2

3

CSE 373 23SU

35

WeightedUnion: Performance

Consider the worst case where the tree height grows as fast as possible

0

1

2

3

CSE 373 23SU

36

WeightedUnion: Performance

Consider the worst case where the tree height grows as fast as possible

0

1

2

3

4

5

6

7

CSE 373 23SU

37

WeightedUnion: Performance

Consider the worst case where the tree height grows as fast as possible

0

1

2

3

4

5

6

7

CSE 373 23SU

38

WeightedUnion: Performance

Consider the worst case where the tree height grows as fast as possible

Worst case tree height is O(log N)

​

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

CSE 373 23SU

39

Runtime so far…

This is pretty good! But there’s one final optimization we can make:

path compression����

​

​

kruskalMST(G graph)

DisjointSets<V> msts; Set finalMST;

initialize msts with each vertex as single-element MST

sort all edges by weight (smallest to largest)

​

for each edge (u,v) in ascending order:

uMST = msts.find(u)

vMST = msts.find(v)

if (uMST != vMST):

finalMST.add(edge (u, v))

msts.union(uMST, vMST);

O(ElogV)

CSE 373 23SU

40

Disjoint Set Implementation

Weighted Union

Path Compression

Array Implementation

​

​

CSE 373 23SU

41

Modifying Data Structures for Future Gains

• Thus far, the modifications we’ve studied are designed to preserve invariants
• E.g. Performing rotations to preserve the AVL invariant
• We rely on those invariants always being true so every call is fast
• Path compression is entirely different: we are modifying the tree structure to improve future performance
• Not adhering to a specific invariant
• The first call may be slow, but will optimize so future calls can be fast

​

CSE 373 23SU

42

Path Compression: Idea

This is the worst-case topology if we use WeightedUnion�������

Key Idea: When we do find(15), move all visited nodes under the root

• Additional cost is insignificant (we already have to visit those nodes, just constant time work to point to root too)

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

CSE 373 23SU

43

Path Compression: Idea

This is the worst-case topology if we use WeightedUnion�������

Key Idea: When we do find(15), move all visited nodes under the root

• Additional cost is insignificant (we already have to visit those nodes, just constant time work to point to root too)

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

Perform Path Compression on every find(), so future calls to find() are faster!

CSE 373 23SU

44

Path Compression: Details and Runtime

Run path compression on every find()!

• Including the find()s that are invoked as part of a union()����

Understanding the performance of M>1 operations requires amortized analysis

• Effectively averaging out rare events over many common ones
• Typically used for “In-Practice” case
• E.g. when we assume an array doesn’t resize “in practice”, we can do that because the rare resizing calls are amortized over many faster calls
• In 373 we don’t go in-depth on amortized analysis

CSE 373 23SU

45

Path Compression: Runtime

M find()s on WeightedUnion requires takes O(M log N)����

​

… but M find()s using the WeightedUnion and PathCompression optimizations takes O(M log*N)!

• log*n is the “iterated log”: the number of times you need to apply log to n before it’s <= 1
• Note: log* is a loose bound�

CSE 373 23SU

46

Path Compression: Runtime

Path compression results in find()s and union()s that are very very close to (amortized) constant time

• log* is less than 5 for any realistic input
• If M find()s/union()s on N nodes is O(M log*N)�and log*N ≈ 5, then find()/union()s amortizes�to O(1)! 🤯

2¹⁶

Number of atoms in the known universe is 2²⁵⁶ish

CSE 373 23SU

47

Kruskal’s Runtime

Find and union are log|V| in worst case, but amortized constant “in practice”

Either way, dominated by time to sort the edges ☹

• For an MST to exist, E can’t be smaller than V, so assume it dominates
• Note: some people write |E|log|V|, which is the same (within a constant factor)

kruskalMST(G graph)

DisjointSets<V> msts; Set finalMST;

initialize msts with each vertex as single-element MST

sort all edges by weight (smallest to largest)

​

for each edge (u,v) in ascending order:

uMST = msts.find(u)

vMST = msts.find(v)

if (uMST != vMST):

finalMST.add(edge (u, v))

msts.union(uMST, vMST)

CSE 373 23SU

48

Disjoint Set Implementation

Weighted Union

Path Compression

Array Implementation

​

​

CSE 373 23SU

49

Using Arrays for Up-Trees

Since every node can have at most one parent, what if we use an array to store the parent relationships?

Proposal: each node corresponds to an index, where we store the index of the parent (or –1 for roots). Use the root index as the representative ID!

Just like with heaps, tree picture still conceptually correct, but exists in our minds!

Paul

CSE 373 23SU

50

Using Arrays: Find

Initial jump to element still done with extra Map

But traversing up the tree can be done purely within the array!

Paul

find(A):

index = jump to A node’s index

while array[index] > 0:

index = array[index]

path compression

return index

1

2

find(Alex)

1

2

= 0

Can still do path compression by setting all indices along the way to the root index!

3

3

CSE 373 23SU

51

Using Arrays: Union

For WeightedUnion, we need to store the number of nodes in each tree (the weight)

Instead of just storing -1 to indicate a root, we can store -1 * weight!

union(A, B):

rootA = find(A)

rootB = find(B)

use -1 * array[rootA] and -1 *

array[rootB] to determine weights

put lighter root under heavier root

weight 4

weight 2

union(Ken, Santino)

Paul

weight 1

Paul

CSE 373 23SU

52

Using Arrays: Union

For WeightedUnion, we need to store the number of nodes in each tree (the weight)

Instead of just storing -1 to indicate a root, we can store -1 * weight!

union(A, B):

rootA = find(A)

rootB = find(B)

use -1 * array[rootA] and -1 *

array[rootB] to determine weights

put lighter root under heavier root

weight 6

Paul

weight 1

Aileen

union(Ken, Santino)

CSE 373 23SU

53

Array Implementation Practice

weight = 1

weight = 8

weight = 10

Fill in the array representing this DisJoint set. Remember to Store (weight * -1) - 1 as the “parent” of the root nodes

Each “node” now only takes 4 bytes of memory instead of 32

CSE 373 23SU

54

Array Implementation Practice

55

weight = 1

weight = 8

weight = 6

weight = 2

Update the Array with the correct values after a call of union(14, 11) using WeightedUnion and PathCompression

CSE 373 23SU

55

Array Implementation Practice

56

weight = 1

weight = 14

weight = 2

Update the Array with the correct values after a call of union(14, 11) using WeightedUnion and PathCompression

CSE 373 23SU

56

That’s all!

CSE 373 23SU

57