麻省理工学院：《算法导论》（英文版） Lecture 16 Prof charles e. leiserson

Introduction to algorithms 6.046J/18,401J/SMA5503 Lecture 16 Prof charles e. leiserson

Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 16 Prof. Charles E. Leiserson

Graphs(review) Definition. a directed graph(digraph G=(, E)is an ordered pair consisting of a set y of vertices(singular: vertex) a sete c× of edges. In an undirected graphG=(V, E), the edge set e consists of unordered pairs of vertices In either case, we have El=O(v2).Moreover if G is connected, then E2v-l, which implies that lg el=o(g n) (Review Clrs, appendix B) c 2001 by Charles E Leiserson Introduction to Agorithms Day 27 L16.2

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 27 L16.2 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| = Θ(lgV). (Review CLRS, Appendix B.)

Adiacencv-matrix representation The adjacency matrix of a grap oh G=(v, E), where V=(1, 2,.,n), is the matrix A[l.n,1.n gIven lif(2)∈E, 0 if(i,D) e A1234 D 10 110 0(2) storage 20010> dense 3H430000 representation 4|0010 c 2001 by Charles E Leiserson Introduction to Agorithms Day 27 L16.3

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 27 L16.3 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. 22 11 33 44 A 1234 1 2 3 4 0110 0010 0000 0010 Θ(V 2) storage ⇒ dense representation

Adjacency-list representation An adjacency list of a vertex E v is the list Adilv of vertices adjacent to y Ad[1]={2,3} Ady2]={3} Ady3]={} 4 Adj4]={3} For undirected graphs, Adjlvll-degree(v) For digraphs, Adilv- out-de greely Handshaking Lemma: vey=2 E for undirected graphs= adjacency lists use o(v+ E) storage a sparse representation (for either type of graph) c 2001 by Charles E Leiserson Introduction to Agorithms Day 27 L16.4

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 27 L16.4 Adjacency-list representation An adjacency list of a vertex v ∈ V is the list Adj[v] of vertices adjacent to v. 22 11 33 44 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)

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. Output: a spanning tree T-a tree that connects all vertices-of minimum weight W(7)= (l2y) (u,v)∈eT c 2001 by Charles E Leiserson Introduction to Agorithms Day 27 L16.5

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 27 L16.5 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.) ∑ ∈ = u v T w T w u v ( , ) ( ) ( , ). Output: A spanning tree T — a tree that connects all vertices — of minimum weight:

Example of Mst 6 12 14 15 10 c 2001 by Charles E Leiserson Introduction to Agorithms Day 27 L16.6

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 27 L16.6 Example of MST 6 12 5 14 3 8 10 15 9 7

Optimal substructure MST T (Other edges ofG are not shown. Remove any edge(u, v)E T. Then, T is partitioned into two subtrees t, and t' Theorem. The subtree T, is an MST,=(V1,El the subgraph of G induced by the vertices of Ti V= vertices of t' E1={(x2y)∈E:x,y∈V1} Similarly ly for T' c 2001 by Charles E Leiserson Introduction to Agorithms Day27L16.7

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 27 L16.7 u v Remove any edge Remove any edge (u, v) ∈ T. Then, T is partitioned into two subtrees T1 and T2. T1 T2 u v Optimal substructure MST T: (Other edges of G are not shown.) Theorem. The subtree T1 is an MST of G1 = (V1, E1), the subgraph of G induced by the vertices of T1: V1 = vertices of T1, E1 = { (x, y) ∈ E : x, y ∈ V1 }. Similarly for T2

Proof of optimal substructure Proof. Cut and paste ()=(l23y)+w(71)+w(72) If Ti were a lower-weight spanning tree than T, for 1, then T'=l(u,DUTUT2 would be a lower-weight spanning tree than T for G. L Do we also have overlapping subproblems? Y es Great then dynamic programming may work Yes, but MsT exhibits another powerful property which leads to an even more efficient algorithm c 2001 by Charles E Leiserson Introduction to Agorithms Day 27 L16.8

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 27 L16.8 Proof of optimal substructure w(T) = w(u, v) + w(T1) + w(T2). Proof. Cut and paste: If T1′ were a lower-weight spanning tree than T1 for G1, then T′ = {(u, v)} ∪ T1′ ∪ T2 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

Hallmark for“ greedy” algorithms Greedy-choice property a locally optimal choice is globally optimal Theorem. Let t'be the MstofG-(v, e) and let A cv. Suppose that(u, v)E E is the least-weight edge connecting A to V-A Then,(23y)∈T c 2001 by Charles E Leiserson Introduction to Agorithms Day 27 L16.9

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 27 L16.9 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

Proof of theorem Proof Suppose(u,v)E T. Cut and paste T ∈A d8(u, v)=least- weight edge ∈ connecting a to v-A c 2001 by Charles E Leiserson Introduction to Agorithms Day 27 L16.10

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 27 L16.10 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