9/15/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Adam Smith Algorithm Design and Analysis LECTURE 10 • Implementing MST Algorithms9/15/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Minimum spanning tree (MST) Input: A connected undirected graph G = (V, E) with weight function w : E → R. • For now, assume all edge weights are distinct. . Output: A spanning tree T — a tree that connects all vertices — of minimum weight:9/15/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Greedy Algorithms for MST • Kruskal's: Start with T = φ. Consider edges in ascending order of weights. Insert edge e in T unless doing so would create a cycle. • Reverse-Delete: Start with T = E. Consider edges in descending order of weights. Delete edge e from T unless doing so would disconnect T. • Prim's: Start with some root node s. Grow a tree T from s outward. At each step, add to T the cheapest edge e with exactly one endpoint in T.9/15/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Cut and Cycle Properties • Cut property. Let S be a subset of nodes. Let e be the min weight edge with exactly one endpoint in S. Then the MST contains e. • Cycle property. Let C be a cycle, and let f be the max weight edge in C. Then the MST does not contain f. f C S e is in the MST e f is not in the MST9/15/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Prim's Algorithm: Correctness • Prim's algorithm. [Jarník 1930, Prim 1959] – Initialize S = any node. – Apply cut property to S. – When edge weights are distinct, the edge that is added must be in the MST – Thus, Prim’s alg. outputs the MST S9/15/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Correctness of Kruskal • [Kruskal, 1956]: Consider edges in ascending order of weight. – Case 1: If adding e to T creates a cycle, discard e according to cycle property. – Case 2: Otherwise, insert e = (u, v) into T according to cut property where S = set of nodes in u's connected component. Case 1 e v u Case 2 e SNon-distinct edges? 9/15/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne9/15/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Implementation of Prim(G,w) IDEA: Maintain V – S as a priority queue Q (as in Dijkstra). Key each vertex in Q with the weight of the least-weight edge connecting it to a vertex in S. Q ← V key[v] ← ∞ for all v ∈ V key[s] ← 0 for some arbitrary s ∈ V while Q ≠ ∅ do u ← EXTRACT-MIN(Q) for each v ∈ Adjacency-list[u] do if v ∈ Q and w(u, v) < key[v] then key[v] ← w(u, v) ⊳ DECREASE-KEY π[v] ← u At the end, {(v, π[v])} forms the MST.9/15/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Handshaking Lemma ⇒ Θ(m) implicit DECREASE-KEY’s. Q ← V key[v] ← ∞ for all v ∈ V key[s] ← 0 for some arbitrary s ∈ V while Q ≠ ∅ do u ← EXTRACT-MIN(Q) for each v ∈ Adj[u] do if v ∈ Q and w(u, v) < key[v] then key[v] ← w(u, v) π[v] ← u Analysis of Prim degree(u) times n times Θ(n) total Time: as in Dijkstra9/15/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Handshaking Lemma ⇒ Θ(m) implicit DECREASE-KEY’s. while Q ≠ ∅ do u ← EXTRACT-MIN(Q) for each v ∈ Adj[u] do if v ∈ Q and w(u, v) < key[v] then key[v] ← w(u, v) π[v] ← u Analysis of Prim degree(u) times n times † Individual ops are amortized bounds PQ Operation ExtractMin DecreaseKey Binary heap log n log n Fib heap † log n 1 Array n 1 Total m log n m + n log n n2 Prim n m d-way Heap HW3 HW3 m log m/n n9/15/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Greedy Algorithms for MST • Kruskal's: Start with T = φ. Consider edges in ascending order of weights. Insert edge e in T unless doing so would create a cycle. • Reverse-Delete: Start with T = E. Consider edges in descending order of weights. Delete edge e from T unless doing so would disconnect T. • Prim's: Start with some root node s. Grow a tree T from s outward. At each step, add to T the cheapest edge e with exactly one endpoint in T.Union-Find Data Structures Operation\ Implementation Array + linked-lists and sizes Balanced Trees Find (worst-case) ϴ(1) ϴ(log n) Union of sets A,B (worst-case) ϴ(min(|A|,|B|) (could be as large as ϴ(n) ϴ(log n) Amortized analysis: k unions and k finds, starting from singletons ϴ(k log k) ϴ(k log k) 9/15/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne • With modifications, amortized time for tree structure is O(n Ack(n)), where Ack(n), the Ackerman function grows much more slowly than log n. • See KT Chapter