Page 1 Introduction to Algorithms, Lecture 16 November 7, 2001 © 2001 by Charles E. Leiserson 1 Graphs and Minimum spanning trees Graphs 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. (Review CLRS, Appendix B.4 and B.5.) u v w x y 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 1 3 4 A 1 2 3 4 1 2 3 4 0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 T(|V| 2 ) storage dense representation. Adjacency-list representation An adjacency list of a vertex v ? V is the list Adj[v] of vertices adjacent to v. 2 1 3 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). Adjacency-list representation Handshaking Lemma: • For undirected graphs: v?V degree(v) = 2|E| • For digraphs: v?V in-degree(v) + v?V out-degree(v) = 2 | E | •Claim: In any party, there is an even number of people that shake an odd number of hand. adjacency lists use T(|V| + |E|) storage a sparse representation Paths in a graph •A simple path between vertices u and v is a list of edges, each edge is ordered, each consecutive pair share a vertex (the last vertex of one edge is the first vertex of the following edge) and a each vertex is used by at most two edges. •A graph is connected if there is a path between every pair of vertices. •The length of the path is the number of edges in the path. Page 2 Introduction to Algorithms, Lecture 16 November 7, 2001 © 2001 by Charles E. Leiserson 1 Graphs and Minimum spanning trees Graphs 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. (Review CLRS, Appendix B.4 and B.5.) u v w x y 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 1 3 4 A 1 2 3 4 1 2 3 4 0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 T(|V| 2 ) storage dense representation. Adjacency-list representation An adjacency list of a vertex v ? V is the list Adj[v] of vertices adjacent to v. 2 1 3 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). Adjacency-list representation Handshaking Lemma: • For undirected graphs: v?V degree(v) = 2|E| • For digraphs: v?V in-degree(v) + v?V out-degree(v) = 2 | E | •Claim: In any party, there is an even number of people that shake an odd number of hand. adjacency lists use T(|V| + |E|) storage a sparse representation Paths in a graph •A simple path between vertices u and v is a list of edges, each edge is ordered, each consecutive pair share a vertex (the last vertex of one edge is the first vertex of the following edge) and a each vertex is used by at most two edges. •A graph is connected if there is a path between every pair of vertices. •The length of the path is the number of edges in the path. Introduction to Algorithms, Lecture 16 November 7, 2001 © 2001 by Charles E. Leiserson 2 Trees •A tree is a connected graph without cycles. •A graph is a tree is there is a unique path between every pair of vertices. •In a tree |E|=|V|-1 Minimum spanning trees Input: A connected, undirected graph G = (V, E) with weights assign to each edge (a real value). • For simplicity, assume that all edge weights are distinct. (CLRS covers the general case.) ? = T v u v u w T w ) , ( ) , ( ) ( . Output: A spanning tree T — a tree that connects all vertices — of minimum weight: The weight of the graph is the sum of weights of its edges Example of MST 6 12 5 14 3 8 10 15 9 7 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. A V\A 5 9 14 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 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 Page 3 Introduction to Algorithms, Lecture 16 November 7, 2001 © 2001 by Charles E. Leiserson 1 Graphs and Minimum spanning trees Graphs 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. (Review CLRS, Appendix B.4 and B.5.) u v w x y 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 1 3 4 A 1 2 3 4 1 2 3 4 0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 T(|V| 2 ) storage dense representation. Adjacency-list representation An adjacency list of a vertex v ? V is the list Adj[v] of vertices adjacent to v. 2 1 3 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). Adjacency-list representation Handshaking Lemma: • For undirected graphs: v?V degree(v) = 2|E| • For digraphs: v?V in-degree(v) + v?V out-degree(v) = 2 | E | •Claim: In any party, there is an even number of people that shake an odd number of hand. adjacency lists use T(|V| + |E|) storage a sparse representation Paths in a graph •A simple path between vertices u and v is a list of edges, each edge is ordered, each consecutive pair share a vertex (the last vertex of one edge is the first vertex of the following edge) and a each vertex is used by at most two edges. •A graph is connected if there is a path between every pair of vertices. •The length of the path is the number of edges in the path. Introduction to Algorithms, Lecture 16 November 7, 2001 © 2001 by Charles E. Leiserson 2 Trees •A tree is a connected graph without cycles. •A graph is a tree is there is a unique path between every pair of vertices. •In a tree |E|=|V|-1 Minimum spanning trees Input: A connected, undirected graph G = (V, E) with weights assign to each edge (a real value). • For simplicity, assume that all edge weights are distinct. (CLRS covers the general case.) ? = T v u v u w T w ) , ( ) , ( ) ( . Output: A spanning tree T — a tree that connects all vertices — of minimum weight: The weight of the graph is the sum of weights of its edges Example of MST 6 12 5 14 3 8 10 15 9 7 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. A V\A 5 9 14 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 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, Lecture 16 November 7, 2001 © 2001 by Charles E. Leiserson 3 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. 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. Prim’s alg – main ideas V\A 9 14 A 2 9 7 •Maintain a MST for the set A of vertices •Maintains for each vertex of V\A the edge with min-weight connecting it to A. •Add at each iteration the vertex with min weight. 14 2 9 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] ? 8 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 p[v] ? u At the end, {(v, p[v])} forms the MST. Example of Prim’s algorithm ? A ? V \ A 8 8 8 8 0 8 8 8 6 12 5 14 3 8 10 15 9 7 Example of Prim’s algorithm ? A ? V \ A 8 8 8 8 0 8 8 8 6 12 5 14 3 8 10 15 9 7 Page 4 Introduction to Algorithms, Lecture 16 November 7, 2001 © 2001 by Charles E. Leiserson 1 Graphs and Minimum spanning trees Graphs 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. (Review CLRS, Appendix B.4 and B.5.) u v w x y 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 1 3 4 A 1 2 3 4 1 2 3 4 0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 T(|V| 2 ) storage dense representation. Adjacency-list representation An adjacency list of a vertex v ? V is the list Adj[v] of vertices adjacent to v. 2 1 3 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). Adjacency-list representation Handshaking Lemma: • For undirected graphs: v?V degree(v) = 2|E| • For digraphs: v?V in-degree(v) + v?V out-degree(v) = 2 | E | •Claim: In any party, there is an even number of people that shake an odd number of hand. adjacency lists use T(|V| + |E|) storage a sparse representation Paths in a graph •A simple path between vertices u and v is a list of edges, each edge is ordered, each consecutive pair share a vertex (the last vertex of one edge is the first vertex of the following edge) and a each vertex is used by at most two edges. •A graph is connected if there is a path between every pair of vertices. •The length of the path is the number of edges in the path. Introduction to Algorithms, Lecture 16 November 7, 2001 © 2001 by Charles E. Leiserson 2 Trees •A tree is a connected graph without cycles. •A graph is a tree is there is a unique path between every pair of vertices. •In a tree |E|=|V|-1 Minimum spanning trees Input: A connected, undirected graph G = (V, E) with weights assign to each edge (a real value). • For simplicity, assume that all edge weights are distinct. (CLRS covers the general case.) ? = T v u v u w T w ) , ( ) , ( ) ( . Output: A spanning tree T — a tree that connects all vertices — of minimum weight: The weight of the graph is the sum of weights of its edges Example of MST 6 12 5 14 3 8 10 15 9 7 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. A V\A 5 9 14 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 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, Lecture 16 November 7, 2001 © 2001 by Charles E. Leiserson 3 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. 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. Prim’s alg – main ideas V\A 9 14 A 2 9 7 •Maintain a MST for the set A of vertices •Maintains for each vertex of V\A the edge with min-weight connecting it to A. •Add at each iteration the vertex with min weight. 14 2 9 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] ? 8 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 p[v] ? u At the end, {(v, p[v])} forms the MST. Example of Prim’s algorithm ? A ? V \ A 8 8 8 8 0 8 8 8 6 12 5 14 3 8 10 15 9 7 Example of Prim’s algorithm ? A ? V \ A 8 8 8 8 0 8 8 8 6 12 5 14 3 8 10 15 9 7 Introduction to Algorithms, Lecture 16 November 7, 2001 © 2001 by Charles E. Leiserson 4 Example of Prim’s algorithm ? A ? V \ A 8 8 7 8 0 10 8 15 6 12 5 14 3 8 10 15 9 7 Example of Prim’s algorithm ? A ? V \ A 8 8 7 8 0 10 8 15 6 12 5 14 3 8 10 15 9 7 Example of Prim’s algorithm ? A ? V \ A 12 5 7 8 0 10 9 15 6 12 5 14 3 8 10 15 9 7 Example of Prim’s algorithm ? A ? V \ A 12 5 7 8 0 10 9 15 6 12 5 14 3 8 10 15 9 7 Example of Prim’s algorithm ? A ? V \ A 6 5 7 14 0 8 9 15 6 12 5 14 3 8 10 15 9 7 Example of Prim’s algorithm ? A ? V \ A 6 5 7 14 0 8 9 15 6 12 5 14 3 8 10 15 9 7 Page 5 Introduction to Algorithms, Lecture 16 November 7, 2001 © 2001 by Charles E. Leiserson 1 Graphs and Minimum spanning trees Graphs 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. (Review CLRS, Appendix B.4 and B.5.) u v w x y 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 1 3 4 A 1 2 3 4 1 2 3 4 0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 T(|V| 2 ) storage dense representation. Adjacency-list representation An adjacency list of a vertex v ? V is the list Adj[v] of vertices adjacent to v. 2 1 3 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). Adjacency-list representation Handshaking Lemma: • For undirected graphs: v?V degree(v) = 2|E| • For digraphs: v?V in-degree(v) + v?V out-degree(v) = 2 | E | •Claim: In any party, there is an even number of people that shake an odd number of hand. adjacency lists use T(|V| + |E|) storage a sparse representation Paths in a graph •A simple path between vertices u and v is a list of edges, each edge is ordered, each consecutive pair share a vertex (the last vertex of one edge is the first vertex of the following edge) and a each vertex is used by at most two edges. •A graph is connected if there is a path between every pair of vertices. •The length of the path is the number of edges in the path. Introduction to Algorithms, Lecture 16 November 7, 2001 © 2001 by Charles E. Leiserson 2 Trees •A tree is a connected graph without cycles. •A graph is a tree is there is a unique path between every pair of vertices. •In a tree |E|=|V|-1 Minimum spanning trees Input: A connected, undirected graph G = (V, E) with weights assign to each edge (a real value). • For simplicity, assume that all edge weights are distinct. (CLRS covers the general case.) ? = T v u v u w T w ) , ( ) , ( ) ( . Output: A spanning tree T — a tree that connects all vertices — of minimum weight: The weight of the graph is the sum of weights of its edges Example of MST 6 12 5 14 3 8 10 15 9 7 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. A V\A 5 9 14 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 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, Lecture 16 November 7, 2001 © 2001 by Charles E. Leiserson 3 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. 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. Prim’s alg – main ideas V\A 9 14 A 2 9 7 •Maintain a MST for the set A of vertices •Maintains for each vertex of V\A the edge with min-weight connecting it to A. •Add at each iteration the vertex with min weight. 14 2 9 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] ? 8 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 p[v] ? u At the end, {(v, p[v])} forms the MST. Example of Prim’s algorithm ? A ? V \ A 8 8 8 8 0 8 8 8 6 12 5 14 3 8 10 15 9 7 Example of Prim’s algorithm ? A ? V \ A 8 8 8 8 0 8 8 8 6 12 5 14 3 8 10 15 9 7 Introduction to Algorithms, Lecture 16 November 7, 2001 © 2001 by Charles E. Leiserson 4 Example of Prim’s algorithm ? A ? V \ A 8 8 7 8 0 10 8 15 6 12 5 14 3 8 10 15 9 7 Example of Prim’s algorithm ? A ? V \ A 8 8 7 8 0 10 8 15 6 12 5 14 3 8 10 15 9 7 Example of Prim’s algorithm ? A ? V \ A 12 5 7 8 0 10 9 15 6 12 5 14 3 8 10 15 9 7 Example of Prim’s algorithm ? A ? V \ A 12 5 7 8 0 10 9 15 6 12 5 14 3 8 10 15 9 7 Example of Prim’s algorithm ? A ? V \ A 6 5 7 14 0 8 9 15 6 12 5 14 3 8 10 15 9 7 Example of Prim’s algorithm ? A ? V \ A 6 5 7 14 0 8 9 15 6 12 5 14 3 8 10 15 9 7 Introduction to Algorithms, Lecture 16 November 7, 2001 © 2001 by Charles E. Leiserson 5 Example of Prim’s algorithm ? A ? V \ A 6 5 7 14 0 8 9 15 6 12 5 14 3 8 10 15 9 7 Example of Prim’s algorithm ? A ? V \ A 6 5 7 3 0 8 9 15 6 12 5 14 3 8 10 15 9 7 Example of Prim’s algorithm ? A ? V \ A 6 5 7 3 0 8 9 15 6 12 5 14 3 8 10 15 9 7 Example of Prim’s algorithm ? A ? V \ A 6 5 7 3 0 8 9 15 6 12 5 14 3 8 10 15 9 7 Example of Prim’s algorithm ? A ? V \ A 6 5 7 3 0 8 9 15 6 12 5 14 3 8 10 15 9 7 Handshaking Lemma T(|E|) implicit DECREASE-KEY’s. Q ? V key[v] ? 8 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) p[v] ? u Analysis of Prim degree(u) times |V | times T(|V|) total Time = T(|V|)·T EXTRACT-MIN + T(|E|)·T DECREASE-KEYRead More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!