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: