Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 16 Prof. Charles E. Leiserson Introduction to Algorithms Day 27 L16.2? 2001 by Charles E. Leiserson Graphs (review) Definition. A directed graph (digraph) G = (V, E) is an ordered pair consisting of ? a set V of vertices (singular: vertex), ? a set E ? V × V of edges. In an undirected graph G = (V, E), the edge set E consists of unordered pairs of vertices. In either case, we have |E| = O(V 2 ). Moreover, if G is connected, then |E| ≥ |V| –1, which implies that lg |E| = Θ(lg V). (Review CLRS, Appendix B.) Introduction to Algorithms Day 27 L16.3? 2001 by Charles E. Leiserson Adjacency-matrix representation The adjacency matrix of a graph G = (V, E), where V = {1, 2, …, n}, is the matrix A[1 . . n, 1 . . n] given by A[i, j] = 1 if (i, j) ∈ E, 0 if (i, j) ? E. 2 2 1 1 3 3 4 4 A 1234 1 2 3 4 0110 0010 0000 0010 Θ(V 2 ) storage ? dense representation. Introduction to Algorithms Day 27 L16.4? 2001 by Charles E. Leiserson Adjacency-list representation An adjacency list of a vertex v ∈ V is the list Adj[v] of vertices adjacent to v. 2 2 1 1 3 3 4 4 Adj[1] = {2, 3} Adj[2] = {3} Adj[3] = {} Adj[4] = {3} For undirected graphs, |Adj[v]| = degree(v). For digraphs, |Adj[v]| = out-degree(v). Handshaking Lemma: ∑ v∈V = 2|E| for undirected graphs ? adjacency lists use Θ(V + E) storage — a sparse representation (for either type of graph). Introduction to Algorithms Day 27 L16.5? 2001 by Charles E. Leiserson Minimum spanning trees Input: A connected, undirected graph G = (V, E) with weight function w : E →R. ? For simplicity, assume that all edge weights are distinct. (CLRS covers the general case.) ∑ ∈ = Tvu vuwTw ),( ),()( . Output: A spanning tree T — a tree that connects all vertices — of minimum weight: Introduction to Algorithms Day 27 L16.6? 2001 by Charles E. Leiserson Example of MST 612 5 14 3 8 10 15 9 7 Introduction to Algorithms Day 27 L16.7? 2001 by Charles E. Leiserson u v Remove any edge (u, v) ∈ T. . Then, T is partitioned into two subtrees T 1 and T 2 . T 1 T 2 Optimal substructure MST T: (Other edges of G are not shown.) Theorem. The subtree T 1 is an MST of G 1 = (V 1 , E 1 ), the subgraph of G induced by the vertices of T 1 : V 1 = vertices of T 1 , E 1 = { (x, y) ∈ E : x, y ∈ V 1 }. Similarly for T 2 . Introduction to Algorithms Day 27 L16.8? 2001 by Charles E. Leiserson Proof of optimal substructure w(T) = w(u, v) + w(T 1 ) + w(T 2 ). Proof. Cut and paste: If T 1 ′were a lower-weight spanning tree than T 1 for G 1 , then T′ = {(u, v)} ∪ T 1 ′∪T 2 would be a lower-weight spanning tree than T for G. Do we also have overlapping subproblems? ?Yes. Great, then dynamic programming may work! ?Yes, but MST exhibits another powerful property which leads to an even more efficient algorithm. Introduction to Algorithms Day 27 L16.9? 2001 by Charles E. Leiserson Hallmark for “greedy” algorithms Greedy-choice property A locally optimal choice is globally optimal. Theorem. Let T be the MST of G = (V, E), and let A ? V. Suppose that (u, v) ∈ E is the least-weight edge connecting A to V – A. Then, (u, v) ∈ T. Introduction to Algorithms Day 27 L16.10? 2001 by Charles E. Leiserson Proof of theorem Proof. Suppose (u, v) ? T. Cut and paste. ∈ A ∈ V – A T: u v (u, v) = least-weight edge connecting A to V – A Introduction to Algorithms Day 27 L16.11? 2001 by Charles E. Leiserson Proof of theorem Proof. Suppose (u, v) ? T. Cut and paste. ∈ A ∈ V – A T: u Consider the unique simple path from u to v in T. (u, v) = least-weight edge connecting A to V – A v Introduction to Algorithms Day 27 L16.12? 2001 by Charles E. Leiserson Proof of theorem Proof. Suppose (u, v) ? T. Cut and paste. ∈ A ∈ V – A T: u (u, v) = least-weight edge connecting A to V – A v Consider the unique simple path from u to v in T. Swap (u, v) with the first edge on this path that connects a vertex in A to a vertex in V – A. Introduction to Algorithms Day 27 L16.13? 2001 by Charles E. Leiserson Proof of theorem Proof. Suppose (u, v) ? T. Cut and paste. ∈ A ∈ V – A T′: u (u, v) = least-weight edge connecting A to V – A v Consider the unique simple path from u to v in T. Swap (u, v) with the first edge on this path that connects a vertex in A to a vertex in V – A. A lighter-weight spanning tree than T results. Introduction to Algorithms Day 27 L16.14? 2001 by Charles E. Leiserson Prim’s algorithm IDEA: Maintain V – A as a priority queue Q. Key each vertex in Q with the weight of the least- weight edge connecting it to a vertex in A. 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) ? DECREASE-KEY π[v] ← u At the end, {(v, π[v])} forms the MST. Introduction to Algorithms Day 27 L16.15? 2001 by Charles E. Leiserson Example of Prim’s algorithm ∈ A ∈ V – A ∞ ∞ ∞ ∞ 0 0 ∞ ∞ ∞ 612 5 14 3 8 10 15 9 7 Introduction to Algorithms Day 27 L16.16? 2001 by Charles E. Leiserson Example of Prim’s algorithm ∈ A ∈ V – A ∞ ∞ ∞ ∞ 0 0 ∞ ∞ ∞ 612 5 14 3 8 10 15 9 7 Introduction to Algorithms Day 27 L16.17? 2001 by Charles E. Leiserson Example of Prim’s algorithm ∈ A ∈ V – A ∞ ∞ 7 7 ∞ 0 0 10 10 ∞ 15 15 612 5 14 3 8 10 15 9 7 Introduction to Algorithms Day 27 L16.18? 2001 by Charles E. Leiserson Example of Prim’s algorithm ∈ A ∈ V – A ∞ ∞ 7 7 ∞ 0 0 10 10 ∞ 15 15 612 5 14 3 8 10 15 9 7 Introduction to Algorithms Day 27 L16.19? 2001 by Charles E. Leiserson Example of Prim’s algorithm ∈ A ∈ V – A 12 12 5 5 7 7 ∞ 0 0 10 10 9 9 15 15 612 5 14 3 8 10 15 9 7 Introduction to Algorithms Day 27 L16.20? 2001 by Charles E. Leiserson Example of Prim’s algorithm ∈ A ∈ V – A 12 12 5 5 7 7 ∞ 0 0 10 10 9 9 15 15 612 5 14 3 8 10 15 9 7 Introduction to Algorithms Day 27 L16.21? 2001 by Charles E. Leiserson Example of Prim’s algorithm ∈ A ∈ V – A 6 6 5 5 7 7 14 14 0 0 8 8 9 9 15 15 612 5 14 3 8 10 15 9 7 Introduction to Algorithms Day 27 L16.22? 2001 by Charles E. Leiserson Example of Prim’s algorithm ∈ A ∈ V – A 6 6 5 5 7 7 14 14 0 0 8 8 9 9 15 15 612 5 14 3 8 10 15 9 7 Introduction to Algorithms Day 27 L16.23? 2001 by Charles E. Leiserson Example of Prim’s algorithm ∈ A ∈ V – A 6 6 5 5 7 7 14 14 0 0 8 8 9 9 15 15 612 5 14 3 8 10 15 9 7 Introduction to Algorithms Day 27 L16.24? 2001 by Charles E. Leiserson Example of Prim’s algorithm ∈ A ∈ V – A 6 6 5 5 7 7 3 3 0 0 8 8 9 9 15 15 612 5 14 3 8 10 15 9 7 Introduction to Algorithms Day 27 L16.25? 2001 by Charles E. Leiserson Example of Prim’s algorithm ∈ A ∈ V – A 6 6 5 5 7 7 3 3 0 0 8 8 9 9 15 15 612 5 14 3 8 10 15 9 7 Introduction to Algorithms Day 27 L16.26? 2001 by Charles E. Leiserson Example of Prim’s algorithm ∈ A ∈ V – A 6 6 5 5 7 7 3 3 0 0 8 8 9 9 15 15 612 5 14 3 8 10 15 9 7 Introduction to Algorithms Day 27 L16.27? 2001 by Charles E. Leiserson Example of Prim’s algorithm ∈ A ∈ V – A 6 6 5 5 7 7 3 3 0 0 8 8 9 9 15 15 612 5 14 3 8 10 15 9 7 Introduction to Algorithms Day 27 L16.28? 2001 by Charles E. Leiserson Handshaking Lemma ?Θ(E) 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 |V | times Θ(V) total Time = Θ(V)·T EXTRACT - MIN + Θ(E)·T DECREASE - KEY Introduction to Algorithms Day 27 L16.29? 2001 by Charles E. Leiserson Analysis of Prim (continued) Time = Θ(V)·T EXTRACT - MIN + Θ(E)·T DECREASE - KEY QT EXTRACT - MIN T DECREASE - KEY Total array O(V) O(1) O(V 2 ) binary heap O(lg V) O(lg V) O(E lg V) Fibonacci heap O(lg V) amortized O(1) amortized O(E + V lg V) worst case Introduction to Algorithms Day 27 L16.30? 2001 by Charles E. Leiserson MST algorithms Kruskal’s algorithm (see CLRS): ? Uses the disjoint-set data structure (Lecture 20). ? Running time = O(E lg V). Best to date: ? Karger, Klein, and Tarjan [1993]. ? Randomized algorithm. ? O(V + E) expected time.