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.
3
1
6
0
4
2
5
datastructur.es
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.
3 1
0
2
4
5
6
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).
datastructur.es
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.
3 1
0
2
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.
4
5
6
Worst case runtime: O(V + E log* V) if we have path compression.
datastructur.es
CS61B, 2019
Lecture 26: Minimum Spanning Trees
¡ñ MST, Cut Property, Generic MST Algorithm
¡ñ Prim¡¯s Algorithm
¡ñ Kruskal¡¯s Algorithm
datastructur.es
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. This makes it spanning.
Example:
¡ñ Spanning tree is the black edges and vertices.
These two properties make it a tree.
A minimum spanning tree is a spanning tree of minimum total weight. ¡ñ Example: Directly connecting buildings by power lines.
datastructur.es
Spanning Trees
datastructur.es
How Many are Spanning Trees? http://yellkey.com/now
datastructur.es
MST Applications
Old school handwriting recognition (left (link))
Medical imaging (e.g. arrangement of nuclei in cancer cells (right)) For more, see: http://www.ics.uci.edu/~eppstein/gina/mst.html
datastructur.es
MST
Find the MST for the graph.
B
C
2
2
2
s
A
3
D
datastructur.es
MST
Find the MST for the graph.
B
C
2
2
2
s
A
3
D
datastructur.es
MST vs. SPT, http://yellkey.com/sit
Is the MST for this graph also a shortest paths tree? If so, using which node as
the starting node for this SPT?
A. A
B. B
C. C
D. D
E. No SPT is an MST.
B
C
2
2
2
s
A
3
D
datastructur.es
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. A
B. B
C. C
D. D
E. No SPT is an MST.
2
B
C
2
2
A
3
D
s= D
Doesn¡¯t work for s = D!
datastructur.es
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?
2
B
A. A
B. B
C. C
D. D
E. No SPT is an MST.
SPT from A s
SPT from B, MST
s
C
2
2
A
3
D
B
C
2
2
2
A
2
3
D
s
B
SPT from C SPT from D
s
s
C
2
2
A
3
D
datastructur.es
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.
datastructur.es
1
1
1
1
1
1
2
2
2
2
0
0
1
1
1
1
1
1
Spanning Tree, http://yellkey.com/both Give a valid MST for the graph below.
¡ñ Hard B level question: Is there a node whose SPT is also the MST?
A. Yes B. No
datastructur.es
1
1
1
1
1
1
2
2
2
2
0
0
1
1
1
1
1
1
Spanning Tree
Give a valid MST for the graph below.
¡ñ Is there a node whose SPT is also the MST? [see next slide]
datastructur.es
1
1
1
1
1
1
2
2
2
2
0
0
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
0
1
0
1
1
1
1
1
1
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.
Example SPT from bottom left vertex:
datastructur.es
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.
datastructur.es
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.
Operation
Number of Times
Time per Operation
Total Time
Insert
V
O(log V)
O(V log V)
Delete minimum
V
O(log V)
O(V log V)
Decrease priority
E
O(log V)
O(E log V)
datastructur.es
Cut Property in Action: http://yellkey.com/drive
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
datastructur.es
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
datastructur.es
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!
datastructur.es
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.
datastructur.es
Prim¡¯s Algorithm
datastructur.es
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.
Conceptual Prim¡¯s Algorithm Demo (Link)
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).
datastructur.es
Prim¡¯s vs. Dijkstra¡¯s (visual)
Prim¡¯s Algorithm
Dijkstra¡¯s Algorithm Demos courtesy of Kevin Wayne, Princeton University
datastructur.es
Prim¡¯s Algorithm Implementation
The natural implementation of the conceptual version of Prim¡¯s algorithm is highly inefficient.
¡ñ Example: Iterating over purple edges shown is unnecessary and slow.
Can use some cleverness and a PQ to speed things up.
3
11
1
2
Realistic Implementation Demo (Link) ¡ñ Very similar to Dijkstra¡¯s!
s
1
3
2
6
5
3
4
0
1
1
4
1
2
15
5
datastructur.es
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.
datastructur.es
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.
datastructur.es
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
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);
} }
…
Prim¡¯s Implementation (Pseudocode, 2/2)
while (!fringe.isEmpty()) { int v = fringe.delMin(); scan(G, v);
}
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.
Vertex is closest, so add to MST.
Already in MST, so go to next edge.
Better path to a particular vertex found, so update current best known for that vertex.
datastructur.es
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.
while (!fringe.isEmpty()) { int v = fringe.delMin(); scan(G, v);
}
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]);
} }
}
datastructur.es
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*logV). ¡ñ Assuming E > V, this is just O(E log V).
# Operations
Cost per operation
Total cost
PQ add
V
O(log V)
O(V log V)
PQ delMin
V
O(log V)
O(V log V)
PQ decreasePriority
O(E)
O(log V)
O(E log V)
datastructur.es
Kruskal¡¯s Algorithm
datastructur.es
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.
Conceptual Kruskal¡¯s Algorithm Demo (Link)
Realistic Kruskal¡¯s Algorithm Implementation Demo (Link)
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).
datastructur.es
Prim¡¯s vs. Kruskal¡¯s
Prim¡¯s Algorithm
Kruskal¡¯s Algorithm Demos courtesy of Kevin Wayne, Princeton University
datastructur.es
Kruskal¡¯s Implementation (Pseudocode)
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.
public class KruskalMST {
private List
public KruskalMST(EdgeWeightedGraph G) { MinPQ
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);
} }} }
datastructur.es
Kruskal¡¯s Runtime
Kruskal¡¯s algorithm on previous slide is O(E log E).
Fun fact: In HeapSort lecture, we discuss how do this step in O(E) time using ¡°bottom-up heapification¡±.
Operation
Number of Times
Time per Operation
Total Time
Insert
E
O(log E)
O(E log E)
Delete minimum
O(E)
O(log E)
O(E log E)
union
O(V)
O(log* V)
O(V log* V)
isConnected
O(E)
O(log* V)
O(E log*V)
Note: 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).
datastructur.es
Shortest Paths and MST Algorithms Summary
Problem
Algorithm
Runtime (if E > V)
Notes
Shortest Paths
Dijkstra¡¯s
O(E log V)
Fails for negative weight edges.
MST
Prim¡¯s
O(E log V)
Analogous to Dijkstra¡¯s.
MST
Kruskal¡¯s
O(E log E)
Uses WQUPC.
MST
Kruskal¡¯s with pre-sorted edges
O(E log* V)
Uses WQUPC.
Question: Can we do better than O(E log* V)?
datastructur.es
170 Spoiler: State of the Art Compare-Based MST Algorithms
year
1975
1984
1986
1997
worst case
E log log V
E log* V
E log (log* V)
discovered by
Yao
Fredman-Tarjan
Gabow-Galil-Spencer-Tarjan
E ¦Á(V) log ¦Á(V)
Chazelle
2000
E ¦Á(V)
2002
???
optimal ( )
E ???
link
Chazelle
Pettie-Ramachandran
???
(Slide Courtesy of Kevin Wayne, Princeton University) datastructur.es
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
datastructur.es