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:
1. |E| = |V|-1
2. G is connected
3. 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: 1) Testing every edge every iteration. 2) 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|))