Announcements
Announcements
Homework 4 due on Friday
Slight correction to original problem 3. If you downloaded before Monday, you should check out the latest version.
Exam 2 solutions on course webpage
Last Time
Greedy Algorithms
Minimum Spanning Tree
Given a weighted graph G, find a collection of edges that connect G and have no cycles with as little weight as possible (i.e. a minimum spanning tree)
Basic Facts about Trees
Lemma: For an undirected graph G, any two of the below imply the third:
|E| = |V|-1
G is connected
G has no cycles
Corollary: If G is a tree, then |E| = |V|-1.
Greedy Idea
Proposition: In a graph G, let e be an edge of lightest weight. Then there exists an MST of G containing e. Furthermore, if e is the unique lightest edge, then all MSTs contain e.
Today
MST Algorithms
Example
Lightest edge in MST.
Then what?
Merge those vertices & repeat.
1
2
3
4
5
Algorithm
When more than one vertex, add lightest edge, and merge.
Repeat and then undo merges.
Easier: An edge hasn’t been merged away iff it does not create a cycle with already chosen edges.
Algorithm
Kruskal(G)
T ← {}
While(|T| < |V|-1)
Find lightest edge e that
doesn’t create cycle with T
Add e to T
Return T
O(|V|) Iterations
O(|E|) edges
O(|V|+|E|) time to check for cycle
Runtime:
O(|V||E|2)
Optimizations
Two things are slow here:
Testing every edge every iteration.
Needing to test connectivity for every edge.
To improve (1), if an edge forms a cycle, it will never later become viable.
Sort edges once and use in order.
Kruskal Version 2
Kruskal(G)
Sort edges by weight
T ← {}
For e ∈ E in increasing order
If e does not form cycle
Add e to T
Return T
O(|E|) Iterations
Runtime: O(|E|2)
O(|E| log|E|)
O(|V|+|E|)
Better Cycle Testing
How do we test if edge (v,w) forms a cycle?
If v and w are in the same connected component of the graph formed by T.
Need a data structure. That can:
Add edges to T.
Test if two vertices in same CC.
Components
Union Find Data Structure
Maintains several sets. Each has a representative element.
Operations:
New(e) – Creates a new set with element e.
Rep(a) – Returns the representative element of a’s set.
Join(a,b) – Merges a’s set with b’s.
Note: Check of v & w in same set by testing if Rep(v) = Rep(w).
Kruskal Version 3
Kruskal(G)
Sort edges by weight
T ← {}
Create Union Find
For v ∈ V, New(v)
For (v,w) ∈ E in increasing order
If Rep(v) ≠ Rep(w)
Add (v,w) to T
Join(v,w)
Return T
O(|E|) Iterations
Runtime:O(|E|log|E|)
+|E|(Union-Find Ops)
O(|E| log|E|)
O(|V|) New’s
O(1) Join + Rep
Union Find Implementation
Basic Idea: Each set is a rooted tree with edges pointing towards the representative.
New: Create new node – O(1)
Rep: Follow pointers to root
- O(depth)
Join: Have one Rep point to other.
- O(depth)
Depth
Need to ensure depth isn’t too big.
Idea: Always have shallower tree point to deeper one.
Proposition: With the above rule any tree of depth n must have at least 2n nodes.
Proof: Induction on n. n = 0, done.
To get a tree of depth n, need to join two trees of depth n-1. Total of at least 2n-1+2n-1 = 2n nodes.
Runtime
Union-Find on n nodes runs operations in O(log(n)) time.
Kruskal runs in time O(|E| log|E|).
Note: Using path compressions, union-find actually runs in α(n) time per operation.
Other Algorithms
There are many other ways to create MST algorithms. Kruskal searches the whole graph for light edges, but you can also grow from a point.
Proposition: In a graph G, with vertex v, let e be an edge of lightest weight adjacent to v. Then there exists an MST of G containing e. Furthermore, if e is the unique lightest edge, then all MSTs contain e.
Proof
Consider tree T not containing e.
With extra edge, no longer a tree, must contain a cycle.
Remove other edge e’ adjacent to v from cycle to get T’.
|T’|=|V|-1, and connected, so T’ is a tree.
wt(T’) = wt(T)+wt(e)-wt(e’)
≤ wt(T)
(because wt(e) is minimal).
e
e’
v
Prim’s Algorithm
So instead of checking all edges, you can just check edges from v.
You can then contract edge and repeat.
Prim’s Algorithm: Add lightest edge that connects v to a new vertex.
Implementation very similar to Dijkstra.
Prim’s Algorithm
Prim(G,w)
Pick vertex s \\ doesn’t matter which
For v ∈ V, b(v) ← ∞ \\ lightest edge into v
T ← {}, b(s) ← 0
Priority Queue Q, add all v with key=b(v)
While(Q not empty)
u ← DeleteMin(Q)
If u ≠ s, add (u,Prev(u)) to T
For (u,v) ∈ E
If w(u,v) < b(v)
b(v) ← w(u,v)
Prev(v) ← u
DecreaseKey(v)
Return T
Runtime:
O(|V|log|V| + |E|)
Slightly better than Kruskal
Analysis
At any stage, have some set S of vertices connected to s. Find cheapest edge connecting S to SC.
Proposition: In a graph G, with a cut C, let e be an edge of lightest weight crossing C. Then there exists an MST of G containing e. Furthermore, if e is the unique lightest edge, then all MSTs contain e.
Proof
e
e’
Cycle must have e’ crossing cut!
Notes on MST
Minimum Spanning Tree is one of the best-studied algorithmic problems and there are many known algorithms.
Randomized O(|V|+|E|)
by [Karger-Klein-Tarjan]
O(|E| α(|E|)) by Chazelle
Best algorithm known
(not known whether it is O(|V|+|E|))