DOC PREVIEW
FIU COT 5407 - Elementary Graph Algorithms

This preview shows page 1-2-3-4-5-6-40-41-42-43-44-82-83-84-85-86-87 out of 87 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 87 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 HillGraphsGraph G = (V, E)»V = set of vertices»E = set of edges  (VV)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)GraphsIf (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 GraphsTwo 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 ListsConsists 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 RequirementFor directed graphs:»Sum of lengths of all adj. lists is out-degree(v) = |E| vV »Total storage: (V+E)For undirected graphs:»Sum of lengths of all adj. lists is degree(v) = 2|E| vV »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 TimeSpace: (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 AlgorithmsSearching 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 SearchInput: 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 SearchExpands 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)0rstuvwxyQ: s 0(Courtesy of Prof. Jim Anderson)Example (BFS)101rstuvwxyQ: w r 1 1Example (BFS)10122rstuvwxyQ: r t x 1 2 2Example (BFS)101222rstuvwxyQ: t x v


View Full Document

FIU COT 5407 - Elementary Graph Algorithms

Download Elementary Graph Algorithms
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Elementary Graph Algorithms and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Elementary Graph Algorithms 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?