Elementary Graph AlgorithmsGraphsSlide 3Representation of GraphsAdjacency ListsStorage RequirementPros and Cons: adj listAdjacency MatrixSpace and TimeGraph-searching AlgorithmsBreadth-first SearchSlide 12Slide 14Example (BFS)Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Analysis of BFSBreadth-first TreeDepth-first Search (DFS)Depth-first SearchPseudo-codeExample (DFS)Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Analysis of DFSParenthesis TheoremExample (Parenthesis Theorem)Depth-First TreesWhite-path TheoremDFS: Kinds of edgesClassification of EdgesIdentification of EdgesSlide 54DFS: Kinds Of EdgesSlide 56Slide 57Directed Acyclic GraphExampleCharacterizing a DAGSlide 61Topological SortSlide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70Slide 71Slide 72Slide 73Correctness ProofStrongly Connected ComponentsComponent GraphGSCC is a DAGTranspose of a Directed GraphAlgorithm to determine SCCsSlide 80Slide 81Slide 82How does it work?SCCs and DFS finishing timesSlide 85Slide 86Correctness of SCCSlide 88Elementary Graph AlgorithmsElementary Graph AlgorithmsMany of the slides are from Prof. Plaisted’s resources at University of North Carolina at Chapel HillGraphsGraph G = (V, E)»V = set of vertices»E = set of edges (VV)Types of graphs»Undirected: edge (u, v) = (v, u); for all v, (v, v) E (No self loops.)»Directed: (u, v) is edge from u to v, denoted as u v. Self loops are allowed.»Weighted: each edge has an associated weight, given by a weight function w : E R.»Dense: |E| |V|2.»Sparse: |E| << |V|2.|E| = O(|V|2)GraphsIf (u, v) E, then vertex v is adjacent to vertex u.Adjacency relationship is:»Symmetric if G is undirected.»Not necessarily so if G is directed.If G is connected:»There is a path between every pair of vertices.»|E| |V| – 1.»Furthermore, if |E| = |V| – 1, then G is a tree.Other definitions in Appendix B (B.4 and B.5) as needed.Representation of GraphsTwo standard ways.»Adjacency Lists.»Adjacency Matrix.adcb abcdb a d d c c a b a c adcb1 23 4 1 2 3 41 0 1 1 12 1 0 1 03 1 1 0 14 1 0 1 0Adjacency ListsConsists of an array Adj of |V| lists.One list per vertex.For u V, Adj[u] consists of all vertices adjacent to u.adcb abcdb c d d c adcb abcdb a d d c c a b a c If weighted, store weights also in adjacency lists.Storage RequirementFor directed graphs:»Sum of lengths of all adj. lists is out-degree(v) = |E| vV »Total storage: (V+E)For undirected graphs:»Sum of lengths of all adj. lists is degree(v) = 2|E| vV »Total storage: (V+E)No. of edges leaving vNo. of edges incident on v. Edge (u,v) is incident on vertices u and v.Pros and Cons: adj list Pros»Space-efficient, when a graph is sparse.»Can be modified to support many graph variants.Cons»Determining if an edge (u,v) G is not efficient.•Have to search in u’s adjacency list. (degree(u)) time.(V) in the worst case.Adjacency Matrix|V| |V| matrix A.Number vertices from 1 to |V| in some arbitrary manner.A is then given by:otherwise0),( if1],[EjiajiAijadcb1234 1 2 3 41 0 1 1 12 0 0 1 03 0 0 0 14 0 0 0 0adcb1 23 4 1 2 3 41 0 1 1 12 1 0 1 03 1 1 0 14 1 0 1 0A = AT for undirected graphs.Space and TimeSpace: (V2).»Not memory efficient for large graphs.Time: to list all vertices adjacent to u: (V).Time: to determine if (u, v) E: (1).Can store weights instead of bits for weighted graph.Graph-searching AlgorithmsSearching a graph:»Systematically follow the edges of a graph to visit the vertices of the graph.Used to discover the structure of a graph.Standard graph-searching algorithms.»Breadth-first Search (BFS).»Depth-first Search (DFS).Breadth-first SearchInput: Graph G = (V, E), either directed or undirected, and source vertex s V.Output: »d[v] = distance (smallest # of edges, or shortest path) from s to v, for all v V. d[v] = if v is not reachable from s.[v] = u such that (u, v) is last edge on shortest path s v.•u is v’s predecessor.»Builds breadth-first tree with root s that contains all reachable vertices.Definitions:Path between vertices u and v: Sequence of vertices (v1, v2, …, vk) such that u=v1 and v =vk, and (vi,vi+1) E, for all 1 i k-1.Length of the path: Number of edges in the path.Path is simple if no vertex is repeated.Breadth-first SearchExpands the frontier between discovered and undiscovered vertices uniformly across the breadth of the frontier.»A vertex is “discovered” the first time it is encountered during the search.»A vertex is “finished” if all vertices adjacent to it have been discovered.Colors the vertices to keep track of progress.»White – Undiscovered.»Gray – Discovered but not finished.»Black – Finished.•Colors are required only to reason about the algorithm. Can be implemented without colors.BFS(G,s)1. for each vertex u in V[G] – {s}2 do color[u] white3 d[u] 4 [u] nil5 color[s] gray6 d[s] 07 [s] nil8 Q 9 enqueue(Q,s)10 while Q 11 do u dequeue(Q)12 for each v in Adj[u]13 do if color[v] = white14 then color[v] gray15 d[v] d[u] + 116 [v] u17 enqueue(Q,v)18 color[u] blackBFS(G,s)1. for each vertex u in V[G] – {s}2 do color[u] white3 d[u] 4 [u] nil5 color[s] gray6 d[s] 07 [s] nil8 Q 9 enqueue(Q,s)10 while Q 11 do u dequeue(Q)12 for each v in Adj[u]13 do if color[v] = white14 then color[v] gray15 d[v] d[u] + 116 [v] u17 enqueue(Q,v)18 color[u] blackwhite: undiscoveredgray: discoveredblack: finishedQ: a queue of discovered verticescolor[v]: color of vd[v]: distance from s to v[u]: predecessor of vExample (BFS)0rstuvwxyQ: s 0(Courtesy of Prof. Jim Anderson)Example (BFS)101rstuvwxyQ: w r 1 1Example (BFS)10122rstuvwxyQ: r t x 1 2 2Example (BFS)101222rstuvwxyQ: t x v
View Full Document