Announcements

Project 3 will be out this weekend.

• Significant project so don’t put off starting until the last minute!
• Try to get the starter code compiling by the end of the weekend!
• Larger than project 1, but not as big as project 2.
• This project will be the closest to what you might do at an internship.
• Using datasets.
• Working with and improving upon an existing code base.
• Reading javadocs and documentation.
• Use of many tools at once (webbrowser, Maven, IntelliJ).

​

Midterm 2 Friday. Lecture Friday will be review time. Bring questions. I’ll mostly focus on things that can be answered in ~5 minutes or so or less I think.

​

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.

1

2

3

4

5

6

0

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: Θ(V + E) -- do study guide problems to reinforce this.

1

2

3

4

5

6

0

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 log* V) if we have path compression.

1

2

3

4

5

6

0

CS61B

Lecture 30: Graphs IV: Minimum Spanning Trees

• MST, Cut Property, Generic MST Algorithm
• Prim’s Algorithm
• Kruskal’s Algorithm�

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: Directly connecting buildings by power lines.

These two properties make it a tree.

This makes it spanning.

Spanning Trees

How Many are Spanning Trees? http://shoutkey.com/too

MST Applications

Network design (e.g. bicycle routes in Seattle (left))

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

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

​

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, http://shoutkey.com/were

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, http://shoutkey.com/were

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

MST vs. SPT, http://shoutkey.com/were

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://shoutkey.com/were

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 vertrex.�

​

Spanning Tree, http://shoutkey.com/degree

Give a valid MST for the tree below.

• Hard B level question: Is there a node for which this is also the SPT?
• Rephrased: 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 tree below.

• Is there a node for which this is also the SPT?
• 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:

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://shoutkey.com/went

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.

Prim’s Algorithm

Prim’s Algorithm. Demo: Link or alternate demo: Link

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).

Prim’s vs. Dijkstra’s (visual)

Prim’s Algorithm

Dijkstra’s Algorithm

Demos courtesy of Kevin Wayne, Princeton University

Prim’s vs. Dijkstra’s

Prim’s and Dijkstra’s algorithms are exactly the same, except for the following:

​

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.

​

Visitation:

• Visiting a vertex in Dijkstra’s algorithm means to relax all of its edges.
• Visiting a vertex in Prim’s algorithm means relaxing all of its edges, but under the metric of distance from tree instead of distance from source.

Prim’s Implementation (Pseudocode, 1/2)

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)

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 (not shown in demo).

Vertex is closest, so add to MST.

Prim’s Runtime

What is the runtime of Prim’s algorithm?

• Assume all priority queue operations take log(V) time.

Prim’s Runtime

Exactly like Dijkstra’s runtime:

• Insertions: V, each costing O(log V) time.
• Delete-min: V, each costing O(log V) time.
• DecreasePriority: E, each costing O(log V) time.
• Data structure not discussed in class.

​

Overall runtime, assuming E > V, we have O(E log V) runtime.

Kruskal’s Algorithm

Kruskal’s Algorithm. Demo: Link, or alternate demo Link

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).

​

Prim’s vs. Kruskal’s

Prim’s Algorithm

Demos courtesy of Kevin Wayne, Princeton University

Kruskal’s Algorithm

Kruskal’s Implementation (Pseudocode)

Kruskal’s Runtime

Kruskal’s algorithm is O(E log E).

​

​

​

​

​

​

​

​

Note: If edges are already sorted (e.g. stored in an ordered linked list), then we can skip Build-PQ and deletion is constant time, so overall runtime is O(E log* V).

E log E if we insert repeatedly, E if we use “bottom up heapification” see HeapSort lecture.

Shortest Paths and MST Algorithms Summary

Question: Can we do better than O(E log* V)?

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

Citations

Tree fire: http://www.miamidade.gov/fire/library/hotlines/2011-december_files/tree-fire.jpg

​

Bicycle routes in Seattle: https://www.flickr.com/photos/ewedistrict/21980840

​

Cancer MST: http://www.bccrc.ca/ci/ta01_archlevel.html

​

​