CSE 373 SU23 Section 7

MSTs + Disjoint Sets

Agenda

• Announcements

​

• Disjoint Set ADT

​

• Representing Disjoint Sets

​

• MSTs

​

​

​

Announcements

• P4 is released
• Last project, due Aug 18 at 11:59pm
• Its is hard, so please start as soon as possible!!!
• Final is on the last day of class, Friday August 18th
• 1:10 - 2:10 PM in Smith 120

MicroTeach: Disjoint Sets

Disjoint Set ADT

• makeSet(x): creates a new set within the disjoint set where the only member is x (also representative for set).�
• findSet(x): looks up the set containing element x, returns representative of that set.�
• union(x, y): looks up set containing x and set containing y, combines two sets into one. Picks new representative for resulting set.

​

��

� �

​

13

11

12

7

1

8

2

Representative

Representative

Disjoint Set Uses

• Big Idea: find out if two elements are in the same set!�
• Example below: findSet(1) = findSet(7) = 8. So 1 and 7 are in the same set!

��� �

​

​

13

11

12

7

1

8

2

Representative

Representative

Example: union(1, 2)

findSet(1)

​

��

� �

​

findSet(2)

​

��

� �

​

13

11

12

7

1

8

2

13

11

12

7

1

8

2

Step 1: Use findSet twice to find the two representatives.

Step 2: Stick one representative under the other.

Optimization 1: Union By Size

Problem: Trees can be unbalanced!�

• size(x) upper bounds the height of x (so size(x) >= height(x)).�
• Keep track of size of all trees.�
• When unioning make the tree with larger size the root.�
• If it’s a tie, pick one to be the root arbitrarily.

size = 1

size = 4

Optimization 2: Path Compression

Clever idea: When we do findSet(15), tie all nodes seen to the root!

• Additional cost is insignificant (same complexity class).

​

15

11

5

12

13

6

1

7

14

8

2

9

10

3

0

4

Optimization 2: Path Compression

Clever idea: When we do findSet(15), tie all nodes seen to the root!

• Additional cost is insignificant (same complexity class).

​

15

11

5

12

13

6

1

7

14

8

2

9

0

4

10

3

Array Disjoint Set Implementation

• Map stores item→index in our array representing disjoint sets

​

• Array in which each index represents an item (from map)
• Value at the index is either the index of that item's parent OR, if the item is the representative of the set, -1 * size

Map:

​

0

1

2

apple

carrot

banana

Array:

Disjoint Set:

​

0

0

-3

Problem 1B: Disjoint Sets

Problem 1B: Disjoint Sets

union(2, 13)

5

1

3

4

0

6

2

12

11

10

9

8

13

7

Size 6

Size 1

Size 5

Size 2

Problem 1B: Disjoint Sets

union(2, 13)

5

1

3

4

0

6

2

12

11

10

9

8

13

7

Size 6

Size 1

Size 5

Size 2

Problem 1B: Disjoint Sets

union(2, 13)

5

1

3

4

0

6

2

12

11

10

9

8

13

7

Size 6

Size 1

Size 5

Size 2

Problem 1B: Disjoint Sets

union(2, 13) ✅

5

1

3

4

0

6

2

12

11

10

9

8

13

7

Size 3

Size 6

Size 5

Problem 1B: Disjoint Sets

union(4, 12)

5

1

3

4

0

6

2

12

11

10

9

8

13

7

Size 3

Size 6

Size 5

Problem 1B: Disjoint Sets

union(4, 12)

5

1

3

4

0

6

2

12

11

10

9

8

13

7

Size 3

Size 6

Size 5

Call findSet(12)

Problem 1B: Disjoint Sets

union(4, 12)

5

1

3

4

0

6

2

12

11

10

9

8

13

7

Path compression! 😎

Size 3

Size 6

Size 5

Problem 1B: Disjoint Sets

union(4, 12)

5

1

3

4

0

6

2

12

11

10

9

8

13

7

Size 3

Size 6

Size 5

Problem 1B: Disjoint Sets

union(4, 12) ✅

5

1

3

4

0

6

2

12

11

10

9

8

13

7

Size 11

Size 3

Problem 1B: Disjoint Sets

union(2, 8)

5

1

3

4

0

6

2

12

11

10

9

8

13

7

Size 11

Size 3

Problem 1B: Disjoint Sets

union(2, 8)

5

1

3

4

0

6

2

12

11

10

9

8

13

7

Size 11

Size 3

Problem 1B: Disjoint Sets

union(2, 8)

5

1

3

4

0

6

2

12

11

10

9

8

13

7

Size 3

Size 11

Problem 1B: Disjoint Sets

union(2, 8) ✅

5

1

3

4

0

6

2

12

11

10

9

8

13

7

Size 14

Problem 1B: Disjoint Sets

5

1

3

4

0

6

2

12

11

10

9

8

13

7

Size 14

Problems 3-5: Disjoint Sets as Arrays

​

​

Q3: Disjoint Sets Array Representation

Q3: DJS Array Representation [PRESENT for Animations]

Given a mapping of items->their index,

fill out the pointers array representation for this disjoint set

8

11

7

50

4

3

2

1

Size 8

14

10

9

6

Size 4

Array Representation

Items:

Index:

Value:

Acts as “pointers”. Stores parent index or -size if element is set representative.

-8

-8

1

1

-4

1

1

Same parent as 50 and 7, so same index mapping!

1

1

2

2

Same parent!

5

5

5

5

7

7

Now try it yourself on the other set!

Click to next slide for the answer.

9

10

9

Q4: Disjoint Sets Array Find Set

Q4: DJS Array Find [PRESENT for Animations]

Call findSet(2) on the following disjoint sets. Give the return value of the call, and the updated array representation. Draw the resulting disjoint sets.

Items:

Index:

Value:

8

11

7

50

4

3

2

1

Size 8

3

2

5

1

Return Value:

1

14

10

9

6

Size 4

Q5: Disjoint Sets Array Union

Q5: Disjoint Sets Array Union

union(3, 14) on the array representation of this Disjoint Set

8

11

7

50

4

3

2

1

Size 8

14

10

9

6

Size 4

Q5: Disjoint Sets Array Union

union(3, 14)

8

11

7

50

4

3

2

1

Size 8

14

10

9

6

Size 4

Array Representation

Items:

Index:

Value:

Acts as “pointers”. Stores parent index or -size if element is set representative.

Q5: Disjoint Sets Array Union

union(3, 14)

Items:

Index:

Value:

Q5: Disjoint Sets Array Union

union(3, 14)

findSet(3)

Items:

Index:

Value:

Q5: Disjoint Sets Array Union

union(3, 14)

findSet(3)

Items:

Index:

Value:

Q5: Disjoint Sets Array Union

union(3, 14)

findSet(3)

Items:

Index:

Value:

Q5: Disjoint Sets Array Union

union(3, 14)

findSet(3) = 1

Items:

Index:

Value:

Found representative!

Q5: Disjoint Sets Array Union

union(3, 14)

findSet(3) = 1

Items:

Index:

Value:

Time to do path compression!

Q5: Disjoint Sets Array Union

union(3, 14)

findSet(3) = 1

Items:

Index:

Value:

Time to do path compression!

Q5: Disjoint Sets Array Union

union(3, 14)

findSet(3) = 1

Items:

Index:

Value:

Q5: Disjoint Sets Array Union

union(3, 14)

findSet(3) = 1

findSet(14)

Items:

Index:

Value:

Q5: Disjoint Sets Array Union

union(3, 14)

findSet(3) = 1

findSet(14)

Items:

Index:

Value:

Q5: Disjoint Sets Array Union

union(3, 14)

findSet(3) = 1

findSet(14)

Items:

Index:

Value:

Q5: Disjoint Sets Array Union

union(3, 14)

findSet(3) = 1

findSet(14) = 9

Items:

Index:

Value:

Found representative!

Q5: Disjoint Sets Array Union

union(3, 14)

findSet(3) = 1

findSet(14) = 9

Items:

Index:

Value:

Time to do path compression!

Q5: Disjoint Sets Array Union

union(3, 14)

findSet(3) = 1

findSet(14) = 9

Items:

Index:

Value:

Time to do path compression!

Q5: Disjoint Sets Array Union

union(3, 14)

findSet(3) = 1

findSet(14) = 9

Items:

Index:

Value:

Q5: Disjoint Sets Array Union

union(3, 14)

findSet(3) = 1

findSet(14) = 9

findSet(3) == findSet(14)

No! 3 and 14 belong to different sets within our disjoint set.

Items:

Index:

Value:

?

⁇

︖

¿

?

Q5: Disjoint Sets Array Union

union(3, 14)

findSet(3) = 1 → get set’s size

findSet(14) = 9 → get set’s size

Assign the smaller set’s rep. to point to the larger set’s rep. for the union by size optimization.

Items:

Index:

Value:

Q5: Disjoint Sets Array Union

union(3, 14)

findSet(3) = 1 → -1 * array.get(1) = 8

findSet(14) = 9 → -1 * array.get(9) = 4

Assign the smaller set’s rep. to point to the larger set’s rep. for the union by size optimization.

Items:

Index:

Value:

Q5: Disjoint Sets Array Union

union(3, 14)

findSet(3) = 1 → -1 * array.get(1) = 8

findSet(14) = 9 → -1 * array.get(9) = 4

Assign the smaller set’s rep. to point to the larger set’s rep. for the union by size optimization.

Items:

Index:

Value:

Update larger set’s size

Update smaller set’s parent

Q5: Disjoint Sets Array Union

union(3, 14)

Final Result!

Items:

Index:

Value:

Q5: Disjoint Sets Array Union

union(3, 14)

8

11

7

50

4

3

2

1

Size 12

14

10

9

6

Array Representation

Items:

Index:

Value:

MicroTeach: MSTs

MSTs

• Tree: (when talking about graphs) An connected acyclic graph.�
• Spanning Tree: A set of edges connecting all nodes of the graph in a Tree.�
• Minimum Spanning Tree: The Spanning Tree of lowest possible total weight.�
• Multiple algorithms that are used to find MSTs!

��� �

​

​

1

A

B

C

D

3

4

2

5

1

A

B

C

D

3

4

2

5

1

A

B

C

D

3

4

2

5

MSTs vs. SPTs: A Key Difference

A shortest paths tree depends on the source vertex. There is no source vertex for a minimum spanning tree. The SPT for every other vertex is different from the MST!

Minimizes each node’s distance from source

Minimizes tree’s total edge weight

A

2

4

3

1

D

B

C

SPT from A

A

2

4

3

1

D

B

C

MST

MST Finding Algorithms

Prim’s

​

Start a tree from a single node.��Each iteration, connect a node in the tree to a node not in the tree with the cheapest edge possible. ��(Slowly builds up one, connected tree).

Kruskal’s

​

Repeatedly add the smallest edge that doesn’t cause a cycle in the tree you are building. ��(Can build a few disconnected trees before they all merge).

[Thinks about nodes!]

[Thinks about edges!]

Prim’s Algorithm Pseudocode

PrimMST(Graph G)

initialize distances to ∞

mark source as distance 0

mark all vertices unprocessed

foreach (edge (source, v) ) {

v.dist = weight(source,v)

v.bestEdge = (source,v)

}

while (there are unprocessed vertices) {

let u be the closest unprocessed vertex

add u.bestEdge to spanning tree

foreach (edge (u,v) leaving u) {

if (weight(u,v) < v.dist && v unprocessed ) {

V.dist = weight(u,v)

v.bestEdge = (u,v)

}

}

mark u as processed

}

Prim’s

Creates a tree starting from a single node. During each iteration, connect a node in the tree to a node not in the tree with the lowest edge weight. Iterate until we have a spanning tree.��Thinks about what nodes we are adding and why.

Kruskal’s Algorithm Pseudocode

Kruskal’s pseudocode(Graph G):

Create disjoint sets for each vertex in G

Sort the edges by weight

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

If u is not in the same set as v:

Join set u and v

Add edge(u,v) to mst

Kruskal’s

Start by adding the smallest edge.

During each iteration add the lowest weight edge that does not create a cycle to build the tree.

It will not be a connected tree until we finish�

Thinks about what edges we are adding and why.

Q6A + Q6C + Q7:

MST Practice

Problem 6A: Prim’s

Problem 6A: Prim’s

A

C

B

D

2

7

1

4

3

E

5

G

F

9

10

0

6

8

Problem 6A: Prim’s

A

C

B

D

2

7

1

4

3

E

5

G

F

9

10

0

6

8

Problem 6A: Prim’s

A

C

B

D

2

7

1

4

3

E

5

G

F

9

10

0

6

8

Problem 6A: Prim’s

A

C

B

D

2

7

1

4

3

E

5

G

F

9

10

0

6

8

Problem 6A: Prim’s

A

C

B

D

2

7

1

4

3

E

5

G

F

9

10

0

6

8

Problem 6A: Prim’s

A

C

B

D

2

7

1

4

3

E

5

G

F

9

10

0

6

8

Problem 6A: Prim’s

A

C

B

D

2

7

1

4

3

E

5

G

F

9

10

0

6

8

Problem 6A: Prim’s

A

C

B

D

2

1

3

E

5

G

F

0

6

Problem 6C: Unique MSTs

Problem 6C: Prim’s

A

C

B

D

2

1

3

E

5

G

F

0

6

Problem 6C: Prim’s

Only 1 MST!

A

C

B

D

2

1

3

E

5

G

F

0

6

Problem 6C: Prim’s

Only 1 MST!

(All edge weights are unique.)

A

C

B

D

2

1

3

E

5

G

F

0

6

Problem 6C: Prim’s

Only 1 MST!

(All edge weights are unique.)

Intuition: Doing a swap like this would make MST more expensive!

A

C

B

D

2

1

3

E

5

G

F

0

6

8

Problem 7: Kruskal’s

Ex. Kruskal’s

A

B

E

C

D

G

F

4

2

3

5

1

6

9

3

2

Kruskal’s pseudocode(Graph G):

Create disjoint sets for each vertex in G

Sort the edges by weight

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

If u is not in the same set as v:

Join set u and v)

Add edge(u,v) to mst

​

4

Ex. Kruskal’s

A

B

E

C

D

G

F

4

2

3

5

1

6

9

3

2

Kruskal’s pseudocode(Graph G):

Create disjoint sets for each vertex in G

Sort the edges by weight

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

If u is not in the same set as v:

Join set u and v)

Add edge(u,v) to mst

​

4

Ex. Kruskal’s

A

B

E

C

D

G

F

4

2

3

5

1

6

9

3

2

Kruskal’s pseudocode(Graph G):

Create disjoint sets for each vertex in G

Sort the edges by weight

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

If u is not in the same set as v:

Join set u and v)

Add edge(u,v) to mst

​

4

Ex. Kruskal’s

A

B

E

C

D

G

F

4

2

3

5

1

6

9

3

2

4

Kruskal’s pseudocode(Graph G):

Create disjoint sets for each vertex in G

Sort the edges by weight

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

If u is not in the same set as v:

Join set u and v)

Add edge(u,v) to mst

​

Ex. Kruskal’s

A

B

E

C

D

G

F

4

2

3

5

1

6

9

3

2

4

Kruskal’s pseudocode(Graph G):

Create disjoint sets for each vertex in G

Sort the edges by weight

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

If u is not in the same set as v:

Join set u and v)

Add edge(u,v) to mst

​

Ex. Kruskal’s

A

B

E

C

D

G

F

4

2

3

5

1

6

9

3

2

4

Kruskal’s pseudocode(Graph G):

Create disjoint sets for each vertex in G

Sort the edges by weight

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

If u is not in the same set as v:

Join set u and v)

Add edge(u,v) to mst

​

Ex. Kruskal’s

A

B

E

C

D

G

F

4

2

3

5

1

6

9

3

2

4

Kruskal’s pseudocode(Graph G):

Create disjoint sets for each vertex in G

Sort the edges by weight

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

If u is not in the same set as v:

Join set u and v)

Add edge(u,v) to mst

​

Ex. Kruskal’s

A

B

E

C

D

G

F

4

2

3

5

1

6

9

3

2

4

Kruskal’s pseudocode(Graph G):

Create disjoint sets for each vertex in G

Sort the edges by weight

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

If u is not in the same set as v:

Join set u and v)

Add edge(u,v) to mst

​

Ex. Kruskal’s

A

B

E

C

D

G

F

4

2

3

5

1

6

9

3

2

4

Kruskal’s pseudocode(Graph G):

Create disjoint sets for each vertex in G

Sort the edges by weight

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

If u is not in the same set as v:

Join set u and v)

Add edge(u,v) to mst

​

Ex. Kruskal’s

A

B

E

C

D

G

F

4

2

3

5

1

6

9

3

2

4

Kruskal’s pseudocode(Graph G):

Create disjoint sets for each vertex in G

Sort the edges by weight

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

If u is not in the same set as v:

Join set u and v)

Add edge(u,v) to mst

​

Ex. Kruskal’s

A

B

E

C

D

G

F

4

2

3

5

1

6

9

3

2

4

Kruskal’s pseudocode(Graph G):

Create disjoint sets for each vertex in G

Sort the edges by weight

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

If u is not in the same set as v:

Join set u and v)

Add edge(u,v) to mst

​