Minimum Spanning Trees

1

Lecture 25 (Graphs 4)

CS61B, Fall 2023 @ UC Berkeley

Slides credit: Josh Hug

Graph Problem Warmup

Lecture 25, CS61B, Fall 2023

Graph Problem Warmup

Minimum Spanning Trees

• Intro
• The Cut Property

Prim’s Algorithm

• Basic Prim's (Demo)
• Optimized Prim's (Demo)
• Prim’s Algorithm Code and Runtime

Kruskal’s Algorithm:

• Basic Kruskal’s (Demo)
• Optimized Kruskal’s (Demo)
• Kruskal's vs. Prim's
• Kruskal's Algorithm Code and Runtime

Warm-up Problem

Given a undirected graph, determine if it contains any cycles.

• May use any data structure or algorithm from the course so far.

B

C

D

E

F

G

A

Warm-up Problem

Given a undirected graph, determine if it contains any cycles.

• May use any data structure or algorithm from the course so far.

​

​

​

Approach 1: Do DFS from 0 (arbitrary vertex).

• Keep going until you see a marked vertex.
• Potential danger:
• 1 looks back at 0 and sees marked.
• Solution: Just don’t count the node you came from.

Worst case runtime: O(V + E) -- do study guide problems to reinforce this.

• With some cleverness, can give a tighter bound of O(V) (the number of edges we check is at most V, so O(V+E) = O(V))

B

C

D

E

F

G

A

Warm-up Problem

Given a undirected graph, determine if it contains any cycles.

• May use any data structure or algorithm from the course so far.

​

​

​

​

Approach 2: Use a WeightedQuickUnionUF object.

• For each edge, check if the two vertices are connected.
• If not, union them.
• If so, there is a cycle.

Worst case runtime: O(V + E α(V)) if we have path compression.

• Here α(V) is the inverse Ackermann function from Disjoint Sets.
• With similar reasoning from before, we can reduce to O(V α(V))

B

C

D

E

F

G

A

Minimum Spanning Trees Intro

Lecture 25, CS61B, Fall 2023

Graph Problem Warmup

Minimum Spanning Trees

• Intro
• The Cut Property

Prim’s Algorithm

• Basic Prim's (Demo)
• Optimized Prim's (Demo)
• Prim’s Algorithm Code and Runtime

Kruskal’s Algorithm:

• Basic Kruskal’s (Demo)
• Optimized Kruskal’s (Demo)
• Kruskal's vs. Prim's
• Kruskal's Algorithm Code and Runtime

Spanning Trees

Given an undirected graph, a spanning tree T is a subgraph of G, where T:

• Is connected.
• Is acyclic.
• Includes all of the vertices.

​

Example:

• Spanning tree is the black edges and vertices.

A minimum spanning tree is a spanning tree of minimum total weight.

• Example: Network of power lines that connect a bunch of buildings.

These two properties make it a tree.

This makes it spanning.

Spanning Trees

Which are Spanning Trees? yellkey.com/TODO

A

B

C

MST Applications

Left: Old school handwriting recognition (link)

Right: Medical imaging (e.g. arrangement of nuclei in cancer cells)

For more, see: http://www.ics.uci.edu/~eppstein/gina/mst.html

​

Extra: Minimum Spanning Trees vs. Shortest Paths Trees

Lecture 25, CS61B, Fall 2023

These slides are covered in the web videos, but we won't cover them live.

Graph Problem Warmup

Minimum Spanning Trees

• Intro
• The Cut Property

Prim’s Algorithm

• Basic Prim's (Demo)
• Optimized Prim's (Demo)
• Prim’s Algorithm Code and Runtime

Kruskal’s Algorithm:

• Basic Kruskal’s (Demo)
• Optimized Kruskal’s (Demo)
• Kruskal's vs. Prim's
• Kruskal's Algorithm Code and Runtime

MST

Find the MST for the graph.

B

C

A

s

2

3

2

2

D

MST

Find the MST for the graph.

B

C

A

s

2

3

2

2

D

MST vs. SPT

Is the MST for this graph also a shortest paths tree? If so, using which node as the starting node for this SPT?

1. A
2. B
3. C
4. D
5. No SPT is an MST.

B

C

A

s

2

3

2

2

D

MST vs. SPT

Is the MST for this graph also a shortest paths tree? If so, using which node as the starting node for this SPT?

• A
• B
• C
• D
• No SPT is an MST.

B

C

A

2

3

2

2

D

s = D

Doesn’t work for s = D!

MST vs. SPT, http://yellkey.com/approach

Is the MST for this graph also a shortest paths tree? If so, using which node as the starting node for this SPT?

• A
• B
• C
• D
• No SPT is an MST.

B

C

A

s

2

3

2

2

D

SPT from A

B

C

A

2

3

2

2

D

SPT from B,

MST

B

C

A

s

2

3

2

2

D

SPT from C

SPT from D

s

s

s

MST vs. SPT, http://yellkey.com/approach

A shortest paths tree depends on the start vertex:

• Because it tells you how to get from a source to EVERYTHING.

​

There is no source for a MST.

​

Nonetheless, the MST sometimes happens to be an SPT for a specific vertex.�

​

Spanning Tree

Give a valid MST for the graph below.

• Hard B level question: Is there a node whose SPT is also the MST?

​

​

​

​

​

1. Yes
2. No

2

2

2

2

1

1

1

1

1

1

1

1

1

1

1

1

0

0

Spanning Tree

Give a valid MST for the graph below.

• Is there a node whose SPT is also the MST? [see next slide]

2

2

2

2

1

1

1

1

1

1

1

1

1

1

1

1

0

0

Spanning Tree

Give a valid MST for the graph below.

• Is there a node whose SPT is also the MST?
• No! Minimum spanning tree must include only 2 of the 2 weight edges, but the SPT always includes at least 3 of the 2 weight edges.

2

2

2

2

1

1

1

1

1

1

1

1

1

1

1

1

0

0

2

2

2

2

1

1

1

1

1

1

1

1

1

1

1

1

0

0

Example SPT from bottom left vertex:

The Cut Property

Lecture 25, CS61B, Fall 2023

Graph Problem Warmup

Minimum Spanning Trees

• Intro
• The Cut Property

Prim’s Algorithm

• Basic Prim's (Demo)
• Optimized Prim's (Demo)
• Prim’s Algorithm Code and Runtime

Kruskal’s Algorithm:

• Basic Kruskal’s (Demo)
• Optimized Kruskal’s (Demo)
• Kruskal's vs. Prim's
• Kruskal's Algorithm Code and Runtime

A Useful Tool for Finding the MST: Cut Property

• A cut is an assignment of a graph’s nodes to two non-empty sets.
• A crossing edge is an edge which connects a node from one set to a node from the other set.

​

​

​

​

​

​

​

​

Cut property: Given any cut, minimum weight crossing edge is in the MST.

• For rest of today, we’ll assume edge weights are unique.

Cut Property in Action: http://yellkey.com/TODO

Which edge is the minimum weight edge crossing the cut {2, 3, 5, 6}?

0-7 0.16

2-3 0.17

1-7 0.19

0-2 0.26

5-7 0.28

1-3 0.29

1-5 0.32

2-7 0.34

4-5 0.35

1-2 0.36

4-7 0.37

0-4 0.38

6-2 0.40

3-6 0.52

6-0 0.58

6-4 0.93

Cut Property in Action

Which edge is the minimum weight edge crossing the cut {2, 3, 5, 6}?

• 0-2. Must be part of the MST!

0-7 0.16

2-3 0.17

1-7 0.19

0-2 0.26

5-7 0.28

1-3 0.29

1-5 0.32

2-7 0.34

4-5 0.35

1-2 0.36

4-7 0.37

0-4 0.38

6-2 0.40

3-6 0.52

6-0 0.58

6-4 0.93

Cut Property Proof

Suppose that the minimum crossing edge e were not in the MST.

• Adding e to the MST creates a cycle.
• Some other edge f must also be a crossing edge.
• Removing f and adding e is a lower weight spanning tree.
• Contradiction!

Generic MST Finding Algorithm

Start with no edges in the MST.

• Find a cut that has no crossing edges in the MST.
• Add smallest crossing edge to the MST.
• Repeat until V-1 edges.

​

This should work, but we need some way of finding a cut with no crossing edges!

• Random isn’t a very good idea.

Basic Prim's (Demo)

Lecture 25, CS61B, Fall 2023

Graph Problem Warmup

Minimum Spanning Trees

• Intro
• The Cut Property

Prim’s Algorithm

• Basic Prim's (Demo)
• Optimized Prim's (Demo)
• Prim’s Algorithm Code and Runtime

Kruskal’s Algorithm:

• Basic Kruskal’s (Demo)
• Optimized Kruskal’s (Demo)
• Kruskal's vs. Prim's
• Kruskal's Algorithm Code and Runtime

Prim’s Demo (Conceptual)

Start from some arbitrary start node.

• Add shortest edge (mark black) that has one node inside the MST under construction. Repeat until V-1 edges.

B

C

D

E

F

G

A

s

Node edgeTo

A -

B -

C -

D -

E -

F -

G -

5

2

1

15

3

2

11

3

1

1

4

1

Prim’s Demo (Conceptual)

Start from some arbitrary start node.

• Add shortest edge (mark black) that has one node inside the MST under construction. Repeat until V-1 edges.

B

C

D

E

F

G

A

s

Node edgeTo

A -

B -

C -

D -

E -

F -

G -

5

2

1

15

3

2

11

3

1

1

4

1

Prim’s Demo (Conceptual)

Start from some arbitrary start node.

• Add shortest edge (mark black) that has one node inside the MST under construction. Repeat until V-1 edges.

B

C

D

E

F

G

A

s

Node edgeTo

A -

B -

C A

D -

E -

F -

G -

5

2

1

15

3

2

11

3

1

1

4

1

Prim’s Demo (Conceptual)

Start from some arbitrary start node.

• Add shortest edge (mark black) that has one node inside the MST under construction. Repeat until V-1 edges.

B

C

D

E

F

G

A

s

Node edgeTo

A -

B -

C A

D -

E -

F -

G -

5

2

1

15

3

2

11

3

1

1

4

1

Prim’s Demo (Conceptual)

Start from some arbitrary start node.

• Add shortest edge (mark black) that has one node inside the MST under construction. Repeat until V-1 edges.

B

C

D

E

F

G

A

s

Node edgeTo

A -

B -

C A

D -

E C

F -

G -

5

2

1

15

3

2

11

3

1

1

4

1

Prim’s Demo (Conceptual)

Start from some arbitrary start node.

• Add shortest edge (mark black) that has one node inside the MST under construction. Repeat until V-1 edges.

B

C

D

E

F

G

A

s

Node edgeTo

A -

B -

C A

D -

E C

F -

G -

5

2

1

15

3

2

11

3

1

1

4

1

Which edge is added next?

Prim’s Demo (Conceptual)

Start from some arbitrary start node.

• Add shortest edge (mark black) that has one node inside the MST under construction. Repeat until V-1 edges.

B

C

D

E

F

G

A

s

Node edgeTo

A -

B -

C A

D E

E C

F -

G -

5

2

1

15

3

2

11

3

1

1

4

1

Which edge is added next?

• Either A-B or D-E are guaranteed to work (see exercises for proof)!
• Note: They are not both guaranteed to be in the MST.

Prim’s Demo (Conceptual)

Start from some arbitrary start node.

• Add shortest edge (mark black) that has one node inside the MST under construction. Repeat until V-1 edges.

B

C

D

E

F

G

A

s

Node edgeTo

A -

B -

C A

D E

E C

F -

G -

5

2

1

15

3

2

11

3

1

1

4

1

Prim’s Demo (Conceptual)

Start from some arbitrary start node.

• Add shortest edge (mark black) that has one node inside the MST under construction. Repeat until V-1 edges.

B

C

D

E

F

G

A

s

Node edgeTo

A -

B -

C A

D E

E C

F -

G D

5

2

1

15

3

2

11

3

1

1

4

1

Prim’s Demo (Conceptual)

Start from some arbitrary start node.

• Add shortest edge (mark black) that has one node inside the MST under construction. Repeat until V-1 edges.

B

C

D

E

F

G

A

s

Node edgeTo

A -

B -

C A

D E

E C

F -

G D

5

2

1

15

3

2

11

3

1

1

4

1

Prim’s Demo (Conceptual)

Start from some arbitrary start node.

• Add shortest edge (mark black) that has one node inside the MST under construction. Repeat until V-1 edges.

B

C

D

E

F

G

A

s

Node edgeTo

A -

B -

C A

D E

E C

F G

G D

5

2

1

15

3

2

11

3

1

1

4

1

Prim’s Demo (Conceptual)

Start from some arbitrary start node.

• Add shortest edge (mark black) that has one node inside the MST under construction. Repeat until V-1 edges.

B

C

D

E

F

G

A

s

Node edgeTo

A -

B -

C A

D E

E C

F G

G D

5

2

1

15

3

2

11

3

1

1

4

1

Prim’s Demo (Conceptual)

Start from some arbitrary start node.

• Add shortest edge (mark black) that has one node inside the MST under construction. Repeat until V-1 edges.

B

C

D

E

F

G

A

s

Node edgeTo

A -

B A

C A

D E

E C

F G

G D

5

2

1

15

3

2

11

3

1

1

4

1

Prim’s Algorithm

Start from some arbitrary start node.

• Repeatedly add shortest edge (mark black) that has one node inside the MST under construction.
• Repeat until V-1 edges.

​

​

​

Why does Prim’s work? Special case of generic algorithm.

• Suppose we add edge e = v->w.
• Side 1 of cut is all vertices connected to start, side 2 is all the others.
• No crossing edge is black (all connected edges on side 1).
• No crossing edge has lower weight (consider in increasing order).

Optimized Prim's (Demo)

Lecture 25, CS61B, Fall 2023

Graph Problem Warmup

Minimum Spanning Trees

• Intro
• The Cut Property

Prim’s Algorithm

• Basic Prim's (Demo)
• Optimized Prim's (Demo)
• Prim’s Algorithm Code and Runtime

Kruskal’s Algorithm:

• Basic Kruskal’s (Demo)
• Optimized Kruskal’s (Demo)
• Kruskal's vs. Prim's
• Kruskal's Algorithm Code and Runtime

Prim’s Algorithm Implementation

The natural implementation of the conceptual version of Prim’s algorithm is highly inefficient.

• Example: Iterating over all purple edges shown is unnecessary and slow.

​

Can use some cleverness and a PQ to speed things up.

​

Realistic Implementation Demo

• Very similar to Dijkstra’s!

B

C

D

E

F

G

A

s

5

2

1

15

3

2

11

3

1

1

4

1

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

B

C

D

E

F

G

A

s

Node distTo edgeTo

A 0 -

B ∞ -

C ∞ -

D ∞ -

E ∞ -

F ∞ -

G ∞ -

5

2

1

15

3

2

11

3

1

1

Fringe: [(A: 0), (B: ∞), (C: ∞), (D: ∞), (E: ∞), (F: ∞), (G: ∞)]

4

0

∞

∞

∞

∞

∞

∞

1

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

B

C

D

E

F

G

A

s

Node distTo edgeTo

A 0 -

B ∞ -

C ∞ -

D ∞ -

E ∞ -

F ∞ -

G ∞ -

5

2

1

15

3

2

11

3

1

1

4

0

∞

∞

∞

∞

∞

∞

1

Fringe: [(B: ∞), (C: ∞), (D: ∞), (E: ∞), (F: ∞), (G: ∞)]

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

B

C

D

E

F

G

A

s

Node distTo edgeTo

A -

B 2 A

C 1 A

D ∞ -

E ∞ -

F ∞ -

G ∞ -

5

2

1

15

3

2

11

3

1

1

Fringe: [(C: 1), (B: 2), (D: ∞), (E: ∞), (F: ∞), (G: ∞)]

4

∞

∞

∞

∞

∞

∞

1

2

1

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

B

C

D

E

F

G

A

s

Node distTo edgeTo

A 0 -

B 2 A

C 1 A

D ∞ -

E ∞ -

F ∞ -

G ∞ -

5

2

1

15

3

2

11

3

1

1

Fringe: [(C: 1), (B: 2), (D: ∞), (E: ∞), (F: ∞), (G: ∞)]

4

∞

∞

∞

∞

1

2

1

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

B

C

D

E

F

G

A

s

Node distTo edgeTo

A -

B 2 A

C A

D ∞ -

E ∞ -

F ∞ -

G ∞ -

5

2

1

15

3

2

11

3

1

1

Fringe: [(B: 2), (D: ∞), (E: ∞), (F: ∞), (G: ∞)]

4

∞

∞

∞

∞

1

2

Note: Vertex removal in this implementation of Prim’s is equivalent to edge addition in the conceptual version of Prim’s.

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

B

C

D

E

F

G

A

s

Node distTo edgeTo

A -

B 2 A

C A

D ∞ -

E 1 C

F 15 C

G ∞ -

5

2

1

15

3

2

11

3

1

1

Fringe: [(E: 1), (B: 2), (F: 15), (D: ∞), (G: ∞)]

4

∞

∞

∞

∞

1

2

1

15

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

B

C

D

E

F

G

A

s

Node distTo edgeTo

A -

B 2 A

C A

D ∞ -

E 1 C

F 15 C

G ∞ -

5

2

1

15

3

2

11

3

1

1

Fringe: [(E: 1), (B: 2), (F: 15), (D: ∞), (G: ∞)]

4

∞

∞

1

2

1

15

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

• Show distTo, edgeTo, and fringe after next relaxation.

B

C

D

E

F

G

A

s

Node distTo edgeTo

A -

B 2 A

C A

D ∞ -

E 1 C

F 15 C

G ∞ -

5

2

1

15

3

2

11

3

1

1

Fringe: [(E: 1), (B: 2), (F: 15), (D: ∞), (G: ∞)]

4

∞

∞

1

2

1

15

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

B

C

D

E

F

G

A

s

Node distTo edgeTo

A -

B 2 A

C A

D ∞ -

E C

F 15 C

G ∞ -

5

2

1

15

3

2

11

3

1

1

Fringe: [(B: 2), (F: 15), (D: ∞), (G: ∞)]

4

∞

∞

1

2

15

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

B

C

D

E

F

G

A

s

Node distTo edgeTo

A -

B 2 A

C A

D 2 E

E C

F 4 E

G 3 E

5

2

1

15

3

2

11

3

1

1

Fringe: [(B: 2), (D: 2), (G: 3), (F: 4)]

4

∞

∞

1

2

15

2

3

4

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

B

C

D

E

F

G

A

s

Node distTo edgeTo

A -

B 2 A

C A

D 2 E

E C

F 4 E

G 3 E

5

2

1

15

3

2

11

3

1

1

Fringe: [(B: 2), (D: 2), (G: 3), (F: 4)]

4

1

2

2

3

4

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

B

C

D

E

F

G

A

s

Node distTo edgeTo

A -

B A

C A

D 2 E

E C

F 4 E

G 3 E

5

2

1

15

3

2

11

3

1

1

Fringe: [(D: 2), (G: 3), (F: 4)]

4

1

2

3

4

No need to consider edges with weight 5 and 3 since other side is already marked!

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

B

C

D

E

F

G

A

s

Node distTo edgeTo

A -

B A

C A

D 2 E

E C

F 4 E

G 3 E

5

2

1

15

3

2

11

3

1

1

Fringe: [(D: 2), (G: 3), (F: 4)]

4

1

2

3

4

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

B

C

D

E

F

G

A

s

Node distTo edgeTo

A -

B A

C A

D E

E C

F 4 E

G 3 E

5

2

1

15

3

2

11

3

1

1

Fringe: [(G: 3), (F: 4)]

4

1

3

4

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

B

C

D

E

F

G

A

s

Node distTo edgeTo

A -

B A

C A

D E

E C

F 4 E

G 1 D

5

2

1

15

3

2

11

3

1

1

Fringe: [(G: 1), (F: 4)]

4

1

3

4

1

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

B

C

D

E

F

G

A

s

Node distTo edgeTo

A -

B A

C A

D E

E C

F 4 E

G 1 D

5

2

1

15

3

2

11

3

1

1

Fringe: [(G: 1), (F: 4)]

4

1

4

1

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

B

C

D

E

F

G

A

s

Node distTo edgeTo

A -

B A

C A

D E

E C

F 1 G

G D

5

2

1

15

3

2

11

3

1

1

Fringe: [(F: 1)]

4

1

4

1

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

B

C

D

E

F

G

A

s

Node distTo edgeTo

A -

B A

C A

D E

E C

F 1 G

G D

5

2

1

15

3

2

11

3

1

1

Fringe: [(F: 1)]

4

1

1

Prim’s Demo

Insert all vertices into fringe PQ, storing vertices in order of distance from tree.

Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.

B

C

D

E

F

G

A

s

Node distTo edgeTo

A -

B A

C A

D E

E C

F G

G D

5

2

1

15

3

2

11

3

1

1

Fringe: []

4

1

Prim’s Algorithm Code and Runtime

Lecture 25, CS61B, Fall 2023

Graph Problem Warmup

Minimum Spanning Trees

• Intro
• The Cut Property

Prim’s Algorithm

• Basic Prim's (Demo)
• Optimized Prim's (Demo)
• Prim’s Algorithm Code and Runtime

Kruskal’s Algorithm:

• Basic Kruskal’s (Demo)
• Optimized Kruskal’s (Demo)
• Kruskal's vs. Prim's
• Kruskal's Algorithm Code and Runtime

Prim’s vs. Dijkstra’s

Prim’s and Dijkstra’s algorithms are exactly the same, except Dijkstra’s considers “distance from the source”, and Prim’s considers “distance from the tree.”

​

Visit order:

• Dijkstra’s algorithm visits vertices in order of distance from the source.
• Prim’s algorithm visits vertices in order of distance from the MST under construction.

​

Relaxation:

• Relaxation in Dijkstra’s considers an edge better based on distance to source.
• Relaxation in Prim’s considers an edge better based on distance to tree.

Prim’s vs. Dijkstra’s (visual)

Demos courtesy of Kevin Wayne, Princeton University

Prim’s Implementation (Pseudocode, 1/2)

public class PrimMST {

public PrimMST(EdgeWeightedGraph G) {

edgeTo = new Edge[G.V()];

distTo = new double[G.V()];

marked = new boolean[G.V()];

fringe = new SpecialPQ<Double>(G.V());

distTo[s] = 0.0;

setDistancesToInfinityExceptS(s);

insertAllVertices(fringe);

/* Get vertices in order of distance from tree. */

while (!fringe.isEmpty()) {

int v = fringe.delMin();

scan(G, v);

}

}

...

Fringe is ordered by distTo tree. Must be a specialPQ like Dijkstra’s.

Get vertex closest to tree that is unvisited.

Scan means to consider all of a vertices outgoing edges.

Prim’s Implementation (Pseudocode, 2/2)

private void scan(EdgeWeightedGraph G, int v) {

marked[v] = true;

for (Edge e : G.adj(v)) {

int w = e.other(v);

if (marked[w]) { continue; }

if (e.weight() < distTo[w]) {

distTo[w] = e.weight();

edgeTo[w] = e;

pq.decreasePriority(w, distTo[w]);

}

}

}

​

Important invariant, fringe must be ordered by current best known distance from tree.

Already in MST, so go to next edge.

Better path to a particular vertex found, so update current best known for that vertex.

Vertex is closest, so add to MST.

while (!fringe.isEmpty()) {

int v = fringe.delMin();

scan(G, v);

}

Prim’s Runtime

What is the runtime of Prim’s algorithm?

• Assume all PQ operations take O(log(V)) time.
• Give your answer in Big O notation.

private void scan(EdgeWeightedGraph G, int v) {

marked[v] = true;

for (Edge e : G.adj(v)) {

int w = e.other(v);

if (marked[w]) { continue; }

if (e.weight() < distTo[w]) {

distTo[w] = e.weight();

edgeTo[w] = e;

pq.decreasePriority(w, distTo[w]);

}

}

}

​

while (!fringe.isEmpty()) {

int v = fringe.delMin();

scan(G, v);

}

Prim’s Algorithm Runtime

Priority Queue operation count, assuming binary heap based PQ:

• Insertion: V, each costing O(log V) time.
• Delete-min: V, each costing O(log V) time.
• Decrease priority: O(E), each costing O(log V) time.
• Operation not discussed in lecture, but it was in lab 10.

​

Overall runtime: O(V*log(V) + V*log(V) + E*log(V)).

• Assuming E > V, this is just O(E log V) (Same as Dijkstra's).

Basic Kruskal’s (Demo)

Lecture 25, CS61B, Fall 2023

Graph Problem Warmup

Minimum Spanning Trees

• Intro
• The Cut Property

Prim’s Algorithm

• Basic Prim's (Demo)
• Optimized Prim's (Demo)
• Prim’s Algorithm Code and Runtime

Kruskal’s Algorithm:

• Basic Kruskal’s (Demo)
• Optimized Kruskal’s (Demo)
• Kruskal's vs. Prim's
• Kruskal's Algorithm Code and Runtime

Kruskal’s Demo

Consider edges in order of increasing weight. Add to MST unless a cycle is created.�Repeat until V-1 edges.

​

B

C

D

E

F

G

A

s

MST: []

5

2

1

15

3

3

11

3

1

1

A-C 1

C-E 1

D-G 1

F-G 1

A-B 2

E-B 3

D-E 3

G-E 3

E-F 4

B-C 5

B-D 11

C-F 15

4

1

Kruskal’s Demo

Consider edges in order of increasing weight. Add to MST unless a cycle is created.�Repeat until V-1 edges.

​

B

C

D

E

F

G

A

s

MST: []

5

2

1

15

3

3

11

3

1

1

A-C 1

C-E 1

D-G 1

F-G 1

A-B 2

E-B 3

D-E 3

G-E 3

E-F 4

B-C 5

B-D 11

C-F 15

4

1

Cycle?

White and green colorings for vertices show cut being implicitly utilized by Kruskal’s algorithm.

Kruskal’s Demo

Consider edges in order of increasing weight. Add to MST unless a cycle is created.�Repeat until V-1 edges.

​

B

C

D

E

F

G

A

s

MST: [A-C]

5

2

1

15

3

3

11

3

1

1

A-C 1

C-E 1

D-G 1

F-G 1

A-B 2

E-B 3

D-E 3

G-E 3

E-F 4

B-C 5

B-D 11

C-F 15

4

1

Cycle? No.

Kruskal’s Demo

Consider edges in order of increasing weight. Add to MST unless a cycle is created.�Repeat until V-1 edges.

​

B

C

D

E

F

G

A

s

MST: [A-C]

5

2

1

15

3

3

11

3

1

1

A-C 1

C-E 1

D-G 1

F-G 1

A-B 2

E-B 3

D-E 3

G-E 3

E-F 4

B-C 5

B-D 11

C-F 15

4

1

Cycle? No.

White and green colorings for vertices show cut being implicitly utilized by Kruskal’s algorithm.

Kruskal’s Demo

Consider edges in order of increasing weight. Add to MST unless a cycle is created.�Repeat until V-1 edges.

​

B

C

D

E

F

G

A

s

MST: [A-C, C-E]

5

2

1

15

3

3

11

3

1

1

A-C 1

C-E 1

D-G 1

F-G 1

A-B 2

E-B 3

D-E 3

G-E 3

E-F 4

B-C 5

B-D 11

C-F 15

4

1

Cycle? No.

Kruskal’s Demo

Consider edges in order of increasing weight. Add to MST unless a cycle is created.�Repeat until V-1 edges.

​

B

C

D

E

F

G

A

s

MST: [A-C, C-E]

5

2

1

15

3

3

11

3

1

1

A-C 1

C-E 1

D-G 1

F-G 1

A-B 2

E-B 3

D-E 3

G-E 3

E-F 4

B-C 5

B-D 11

C-F 15

4

1

Cycle?

White and green colorings for vertices show cut being implicitly utilized by Kruskal’s algorithm.

Kruskal’s Demo

Consider edges in order of increasing weight. Add to MST unless a cycle is created.�Repeat until V-1 edges.

​

B

C

D

E

F

G

A

s

MST: [A-C, C-E, D-G]

5

2

1

15

3

3

11

3

1

1

A-C 1

C-E 1

D-G 1

F-G 1

A-B 2

E-B 3

D-E 3

G-E 3

E-F 4

B-C 5

B-D 11

C-F 15

4

1

Cycle? No.

Kruskal’s Demo

Consider edges in order of increasing weight. Add to MST unless a cycle is created.�Repeat until V-1 edges.

​

B

C

D

E

F

G

A

s

MST: [A-C, C-E, D-G]

5

2

1

15

3

3

11

3

1

1

A-C 1

C-E 1

D-G 1

F-G 1

A-B 2

E-B 3

D-E 3

G-E 3

E-F 4

B-C 5

B-D 11

C-F 15

4

1

Cycle?

White and green colorings for vertices show cut being implicitly utilized by Kruskal’s algorithm.

Kruskal’s Demo

Consider edges in order of increasing weight. Add to MST unless a cycle is created.�Repeat until V-1 edges.

​

B

C

D

E

F

G

A

s

MST: [A-C, C-E, D-G, F-G]

5

2

1

15

3

3

11

3

1

1

A-C 1

C-E 1

D-G 1

F-G 1

A-B 2

E-B 3

D-E 3

G-E 3

E-F 4

B-C 5

B-D 11

C-F 15

4

1

Cycle? No.

Kruskal’s Demo

Consider edges in order of increasing weight. Add to MST unless a cycle is created.�Repeat until V-1 edges.

​

B

C

D

E

F

G

A

s

MST: [A-C, C-E, D-G, F-G]

5

2

1

15

3

3

11

3

1

1

A-C 1

C-E 1

D-G 1

F-G 1

A-B 2

E-B 3

D-E 3

G-E 3

E-F 4

B-C 5

B-D 11

C-F 15

4

1

Cycle?

White and green colorings for vertices show cut being implicitly utilized by Kruskal’s algorithm.

Kruskal’s Demo

Consider edges in order of increasing weight. Add to MST unless a cycle is created.�Repeat until V-1 edges.

​

B

C

D

E

F

G

A

s

MST: [A-C, C-E, D-G, F-G, A-B]

5

2

1

15

3

3

11

3

1

1

A-C 1

C-E 1

D-G 1

F-G 1

A-B 2

E-B 3

D-E 3

G-E 3

E-F 4

B-C 5

B-D 11

C-F 15

4

1

Cycle? No.

Kruskal’s Demo

Consider edges in order of increasing weight. Add to MST unless a cycle is created.�Repeat until V-1 edges.

​

B

C

D

E

F

G

A

s

MST: [A-C, C-E, D-G, F-G, A-B]

5

2

1

15

3

3

11

3

1

1

A-C 1

C-E 1

D-G 1

F-G 1

A-B 2

E-B 3

D-E 3

G-E 3

E-F 4

B-C 5

B-D 11

C-F 15

4

1

Cycle?

White and green colorings for vertices show cut being implicitly utilized by Kruskal’s algorithm.

Kruskal’s Demo

Consider edges in order of increasing weight. Add to MST unless a cycle is created.�Repeat until V-1 edges.

​

B

C

D

E

F

G

A

s

MST: [A-C, C-E, D-G, F-G, A-B]

5

2

1

15

3

3

11

3

1

1

A-C 1

C-E 1

D-G 1

F-G 1

A-B 2

E-B 3

D-E 3

G-E 3

E-F 4

B-C 5

B-D 11

C-F 15

4

1

Cycle? Yes. Reject!

Kruskal’s Demo

Consider edges in order of increasing weight. Add to MST unless a cycle is created.�Repeat until V-1 edges.

​

B

C

D

E

F

G

A

s

MST: [A-C, C-E, D-G, F-G, A-B]

5

2

1

15

3

3

11

3

1

1

A-C 1

C-E 1

D-G 1

F-G 1

A-B 2

E-B 3

D-E 3

G-E 3

E-F 4

B-C 5

B-D 11

C-F 15

4

1

Cycle?

White and green colorings for vertices show cut being implicitly utilized by Kruskal’s algorithm.

Kruskal’s Demo

Consider edges in order of increasing weight. Add to MST unless a cycle is created.�Repeat until V-1 edges.

​

B

C

D

E

F

G

A

s

MST: [A-C, C-E, D-G, F-G, A-B, D-E]

5

2

1

15

3

3

11

3

1

1

A-C 1

C-E 1

D-G 1

F-G 1

A-B 2

E-B 3

D-E 3

G-E 3

E-F 4

B-C 5

B-D 11

C-F 15

4

1

Cycle? No.

V-1 edges, so we’re done!

Kruskal’s Algorithm

Initially mark all edges gray.

• Consider edges in increasing order of weight.
• Add edge to MST (mark black) unless doing so creates a cycle.
• Repeat until V-1 edges.

​

​

​

�Why does Kruskal’s work? Special case of generic MST algorithm.

• Suppose we add edge e = v->w.
• Side 1 of cut is all vertices connected to v, side 2 is everything else.
• No crossing edge is black (since we don’t allow cycles).
• No crossing edge has lower weight (consider in increasing order).

​

Optimized Kruskal’s (Demo)

Lecture 25, CS61B, Fall 2023

Graph Problem Warmup

Minimum Spanning Trees

• Intro
• The Cut Property

Prim’s Algorithm

• Basic Prim's (Demo)
• Optimized Prim's (Demo)
• Prim’s Algorithm Code and Runtime

Kruskal’s Algorithm:

• Basic Kruskal’s (Demo)
• Optimized Kruskal’s (Demo)
• Kruskal's vs. Prim's
• Kruskal's Algorithm Code and Runtime

Kruskal’s Demo

Insert all edges into PQ.

Repeat: Remove smallest weight edge. Add to MST if no cycle created.

B

C

D

E

F

G

A

s

MST: []

5

2

1

15

3

3

11

3

1

1

Fringe: (A-C: 1), (C-E: 1),

(D-G: 1), (F-G: 1),

(A-B: 2), (E-B: 3),

(D-E: 3), (G-E: 3),

(E-F: 4), (B-C: 5),

(B-D: 11), (C-F: 15)

4

1

WQU: []

Kruskal’s Demo

Insert all edges into PQ.

Repeat: Remove smallest weight edge. Add to MST if no cycle created.

B

C

D

E

F

G

A

s

MST: []

5

2

1

15

3

3

11

3

1

1

Fringe: (A-C: 1), (C-E: 1),

(D-G: 1), (F-G: 1),

(A-B: 2), (E-B: 3),

(D-E: 3), (G-E: 3),

(E-F: 4), (B-C: 5),

(B-D: 11), (C-F: 15)

4

1

Cycle? isConnected(A, C)

WQU: []

Removed edge: A-C

Kruskal’s Demo

Insert all edges into PQ.

Repeat: Remove smallest weight edge. Add to MST if no cycle created.

B

C

D

E

F

G

A

s

MST: [A-C]

5

2

1

15

3

3

11

3

1

1

Fringe: (A-C: 1), (C-E: 1),

(D-G: 1), (F-G: 1),

(A-B: 2), (E-B: 3),

(D-E: 3), (G-E: 3),

(E-F: 4), (B-C: 5),

(B-D: 11), (C-F: 15)

4

1

Cycle? No. union(A, C). add(A-C).

WQU: [A-C]

Removed edge: A-C

Kruskal’s Demo

Insert all edges into PQ.

Repeat: Remove smallest weight edge. Add to MST if no cycle created.

B

C

D

E

F

G

A

s

MST: [A-C]

5

2

1

15

3

3

11

3

1

1

Fringe: (A-C: 1), (C-E: 1),

(D-G: 1), (F-G: 1),

(A-B: 2), (E-B: 3),

(D-E: 3), (G-E: 3),

(E-F: 4), (B-C: 5),

(B-D: 11), (C-F: 15)

4

1

Cycle? isConnected(C, E)

WQU: [A-C]

Removed edge: C-E

Kruskal’s Demo

Insert all edges into PQ.

Repeat: Remove smallest weight edge. Add to MST if no cycle created.

B

C

D

E

F

G

A

s

MST: [A-C, C-E]

5

2

1

15

3

3

11

3

1

1

Fringe: (A-C: 1), (C-E: 1),

(D-G: 1), (F-G: 1),

(A-B: 2), (E-B: 3),

(D-E: 3), (G-E: 3),

(E-F: 4), (B-C: 5),

(B-D: 11), (C-F: 15)

4

1

Cycle? No. union(C, E). add(C-E)

WQU: [A-C-E]

Removed edge: C-E

Kruskal’s Demo

Insert all edges into PQ.

Repeat: Remove smallest weight edge. Add to MST if no cycle created.

B

C

D

E

F

G

A

s

MST: [A-C, C-E]

5

2

1

15

3

3

11

3

1

1

Fringe: (A-C: 1), (C-E: 1),

(D-G: 1), (F-G: 1),

(A-B: 2), (E-B: 3),

(D-E: 3), (G-E: 3),

(E-F: 4), (B-C: 5),

(B-D: 11), (C-F: 15)

4

1

Cycle? isConnected(D, G)

WQU: [A-C-E]

Removed edge: D-G

Kruskal’s Demo

Insert all edges into PQ.

Repeat: Remove smallest weight edge. Add to MST if no cycle created.

B

C

D

E

F

G

A

s

MST: [A-C, C-E, D-G]

5

2

1

15

3

3

11

3

1

1

Fringe: (A-C: 1), (C-E: 1),

(D-G: 1), (F-G: 1),

(A-B: 2), (E-B: 3),

(D-E: 3), (G-E: 3),

(E-F: 4), (B-C: 5),

(B-D: 11), (C-F: 15)

4

1

Cycle? No. union(D, G). add(D-G).

​

WQU: [A-C-E, D-G]

Removed edge: D-G

Kruskal’s Demo

Insert all edges into PQ.

Repeat: Remove smallest weight edge. Add to MST if no cycle created.

B

C

D

E

F

G

A

s

MST: [A-C, C-E, D-G]

5

2

1

15

3

3

11

3

1

1

Fringe: (A-C: 1), (C-E: 1),

(D-G: 1), (F-G: 1),

(A-B: 2), (E-B: 3),

(D-E: 3), (G-E: 3),

(E-F: 4), (B-C: 5),

(B-D: 11), (C-F: 15)

4

1

Cycle? isConnected(F, G)

WQU: [A-C-E, D-G]

Removed edge: F-G

Kruskal’s Demo

Insert all edges into PQ.

Repeat: Remove smallest weight edge. Add to MST if no cycle created.

B

C

D

E

F

G

A

s

MST: [A-C, C-E, D-G, F-G]

5

2

1

15

3

3

11

3

1

1

Fringe: (A-C: 1), (C-E: 1),

(D-G: 1), (F-G: 1),

(A-B: 2), (E-B: 3),

(D-E: 3), (G-E: 3),

(E-F: 4), (B-C: 5),

(B-D: 11), (C-F: 15)

4

1

Cycle? No. union(F, G). add(F-G).

​

WQU: [A-C-E, D-G-F]

Removed edge: F-G

Kruskal’s Demo

Insert all edges into PQ.

Repeat: Remove smallest weight edge. Add to MST if no cycle created.

B

C

D

E

F

G

A

s

MST: [A-C, C-E, D-G, F-G]

5

2

1

15

3

3

11

3

1

1

Fringe: (A-C: 1), (C-E: 1),

(D-G: 1), (F-G: 1),

(A-B: 2), (E-B: 3),

(D-E: 3), (G-E: 3),

(E-F: 4), (B-C: 5),

(B-D: 11), (C-F: 15)

4

1

Cycle? isConnected(A, B)

WQU: [A-C-E, D-G-F]

Removed edge: A-B

Kruskal’s Demo

Insert all edges into PQ.

Repeat: Remove smallest weight edge. Add to MST if no cycle created.

B

C

D

E

F

G

A

s

MST: [A-C, C-E, D-G, F-G, A-B]

5

2

1

15

3

3

11

3

1

1

Fringe: (A-C: 1), (C-E: 1),

(D-G: 1), (F-G: 1),

(A-B: 2), (E-B: 3),

(D-E: 3), (G-E: 3),

(E-F: 4), (B-C: 5),

(B-D: 11), (C-F: 15)

4

1

Cycle? No. union(A, B). add(A-B)

​

WQU: [A-C-E-B, D-G-F]

Removed edge: A-B

Kruskal’s Demo

Insert all edges into PQ.

Repeat: Remove smallest weight edge. Add to MST if no cycle created.

B

C

D

E

F

G

A

s

MST: [A-C, C-E, D-G, F-G, A-B]

5

2

1

15

3

3

11

3

1

1

Fringe: (A-C: 1), (C-E: 1),

(D-G: 1), (F-G: 1),

(A-B: 2), (E-B: 3),

(D-E: 3), (G-E: 3),

(E-F: 4), (B-C: 5),

(B-D: 11), (C-F: 15)

4

1

Cycle? isConnected(E, B)

WQU: [A-C-E-B, D-G-F]

Removed edge: E-B

Kruskal’s Demo

Insert all edges into PQ.

Repeat: Remove smallest weight edge. Add to MST if no cycle created.

B

C

D

E

F

G

A

s

MST: [A-C, C-E, D-G, F-G, A-B]

5

2

1

15

3

3

11

3

1

1

Fringe: (A-C: 1), (C-E: 1),

(D-G: 1), (F-G: 1),

(A-B: 2), (E-B: 3),

(D-E: 3), (G-E: 3),

(E-F: 4), (B-C: 5),

(B-D: 11), (C-F: 15)

4

1

Cycle? Yes. Do nothing.

WQU: [A-C-E-B, D-G-F]

Removed edge: E-B

Kruskal’s Demo

Insert all edges into PQ.

Repeat: Remove smallest weight edge. Add to MST if no cycle created.

B

C

D

E

F

G

A

s

MST: [A-C, C-E, D-G, F-G, A-B]

5

2

1

15

3

3

11

3

1

1

Fringe: (A-C: 1), (C-E: 1),

(D-G: 1), (F-G: 1),

(A-B: 2), (E-B: 3),

(D-E: 3), (G-E: 3),

(E-F: 4), (B-C: 5),

(B-D: 11), (C-F: 15)

4

1

Cycle? isConnected(D, E)

WQU: [A-C-E-B, D-G-F]

Removed edge: D-E

Kruskal’s Demo

Insert all edges into PQ.

Repeat: Remove smallest weight edge. Add to MST if no cycle created.

B

C

D

E

F

G

A

s

MST: [A-C, C-E, D-G, F-G, A-B, D-E]

5

2

1

15

3

3

11

3

1

1

Fringe: (A-C: 1), (C-E: 1),

(D-G: 1), (F-G: 1),

(A-B: 2), (E-B: 3),

(D-E: 3), (G-E: 3),

(E-F: 4), (B-C: 5),

(B-D: 11), (C-F: 15)

4

1

Cycle? No. union(D, E). add(D-E).

V-1 edges, so done.

WQU: [A-C-E-B-D-G-F]

Removed edge: D-E

Kruskal's vs. Prim's

Lecture 25, CS61B, Fall 2023

Graph Problem Warmup

Minimum Spanning Trees

• Intro
• The Cut Property

Prim’s Algorithm

• Basic Prim's (Demo)
• Optimized Prim's (Demo)
• Prim’s Algorithm Code and Runtime

Kruskal’s Algorithm:

• Basic Kruskal’s (Demo)
• Optimized Kruskal’s (Demo)
• Kruskal's vs. Prim's
• Kruskal's Algorithm Code and Runtime

Prim’s vs. Kruskal’s (visual)

Demos courtesy of Kevin Wayne, Princeton University

Kruskal's Algorithm Code and Runtime

Lecture 25, CS61B, Fall 2023

Graph Problem Warmup

Minimum Spanning Trees

• Intro
• The Cut Property

Prim’s Algorithm

• Basic Prim's (Demo)
• Optimized Prim's (Demo)
• Prim’s Algorithm Code and Runtime

Kruskal’s Algorithm:

• Basic Kruskal’s (Demo)
• Optimized Kruskal’s (Demo)
• Kruskal's vs. Prim's
• Kruskal's Algorithm Code and Runtime

Kruskal’s Implementation (Pseudocode)

public class KruskalMST {

private List<Edge> mst = new ArrayList<Edge>();

public KruskalMST(EdgeWeightedGraph G) {

MinPQ<Edge> pq = new MinPQ<Edge>();

for (Edge e : G.edges()) {

pq.insert(e);

}

WeightedQuickUnionPC uf =

new WeightedQuickUnionPC(G.V());

while (!pq.isEmpty() && mst.size() < G.V() - 1) {

Edge e = pq.delMin();

int v = e.from();

int w = e.to();

if (!uf.connected(v, w)) {

uf.union(v, w);

mst.add(e);

} } } }

​

What is the runtime of Kruskal’s algorithm?

• Assume all PQ operations take O(log(V)) time.
• Assume all WQU operations take O(log* V) time.
• Give your answer in Big O notation.

Kruskal’s Runtime

Kruskal’s algorithm on previous slide is O(E log E).

​

​

​

​

​

​

​

​

Note 1: If we use a pre-sorted list of edges (instead of a PQ), then we can simply iterate through the list in O(E) time, so overall runtime is O(E + V log* V + E log* V) = O(E log* V).

Note 2: E < V², so log E < log V² = 2 log V, so O(E log E) = O(E log V). So while Kruskal's algorithm will be slower than Prim's algorithm for a worst-case unsorted set of edges, it won't be asymptotically slower.

Fun fact: In HeapSort lecture, we will discuss how do this step in O(E) time using “bottom-up heapification”.

Shortest Paths and MST Algorithms Summary

Question: Can we do better than O(E log V)? See bonus slides.

Extra: MST Algorithm History

Lecture 25, CS61B, Fall 2023

These slides are covered in the web videos, but we won't cover them live.

Graph Problem Warmup

Minimum Spanning Trees

• Intro
• The Cut Property

Prim’s Algorithm

• Basic Prim's (Demo)
• Optimized Prim's (Demo)
• Prim’s Algorithm Code and Runtime

Kruskal’s Algorithm:

• Basic Kruskal’s (Demo)
• Optimized Kruskal’s (Demo)
• Kruskal's vs. Prim's
• Kruskal's Algorithm Code and Runtime

170 Spoiler: State of the Art Compare-Based MST Algorithms

(Slide Courtesy of Kevin Wayne, Princeton University)