程序代写代做代考 C algorithm graph COMP251: Elementary graph algorithms

COMP251: Elementary graph algorithms
Jérôme Waldispühl School of Computer Science
McGill University
Based on (Cormen et al., 2002) Based on slides from D. Plaisted (UNC)

Graphs
• GraphG=(V,E)
– V = set of vertices
– E=setofedgesÍ(V ́V)
• Typesofgraphs
bc a
def
– 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) 5 b7c 1 a 11 3 d1e2f 3 Properties • If(u,v)ÎE,thenvertexvisadjacenttovertexu. • Adjacencyrelationshipis: – Symmetric if G is undirected. – Not necessarily so if G is directed. • IfGisconnected: – There is a path between every pair of vertices. – |E| 3 |V| – 1. – Furthermore, if |E| = |V| – 1, then G is a tree. Vocabulary bc a def • Ingoingedgesofu:{(v,u)∈E} (e.g.in(e)={(b,e),(d,e)}) • Outgoingedgesofu:{(u,v)∈E}(e.g.out(d)={(d,e)}) • In-degree(u): | in(u) | • Out-degree(u): | out(u) | Representation of Graphs • Two standard ways. – Adjacency Lists. ab b c d 1234 10111 21010 31101 41010 a b d c a c d a b cd – Adjacency Matrix. 1a b2 3c d4 a c Adjacency Lists • ConsistsofanarrayAdjof|V|lists. • Onelistpervertex. • ForuÎV,Adj[u]consistsofallverticesadjacenttou. ab cd ab cd a b c d a b c d Note: If weighted, store weights also in adjacency lists. b c d b a d c d c c d a b a c Storage Requirement • Fordirectedgraphs: – Sum of lengths of all adj. lists is åout-degree(v) = |E| vÎV – Total storage: Q(V+E) • Forundirectedgraphs: – Sum of lengths of all adj. lists is ådegree(v) = 2|E| vÎV – Total storage: Q(V+E) No. of edges leaving v No. 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) ÎE is not efficient. • Have to search in u’s adjacency list. Q(degree(u)) time. • Q(V) in the worst case. Adjacency Matrix • |V| ́|V|matrixA. • Numberverticesfrom1to|V|insomearbitrary manner. • A is then given by: 1 if(i,j)ÎE A[i, j] = aij = ìíî0 otherwise 1a b2 1234 10111 20010 30001 40000 3c d4 1a b2 1234 10111 21010 31101 41010 A = AT for undirected graphs. 3c d4 Space and Time • Space:Q(V2). – Not memory efficient for large sparse graphs. • Time:tolistallverticesadjacenttou:Q(V). • Time:todetermineif(u,v)ÎE:Q(1). • Canstoreweightsinsteadofbitsforweightedgraph. abcdef a b c d e 5 b7c 0 5 0 11 0 0 0 0 7 0 3 0 0 0 0 0 0 3 0 0 0 0 1 0 0 0 1 0 0 2 0 0 0 0 0 0 a313 11 def f12 Graph-searching Algorithms (COMP250) • Searchingagraph: – Systematically follow the edges of a graph to visit the vertices of the graph. • Usedtodiscoverthestructureofagraph. • Standardgraph-searchingalgorithms. – Breadth-first Search (BFS). – Depth-first Search (DFS). Breadth-first Search • Expandsthefrontierbetweendiscoveredand 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. • Colorstheverticestokeeptrackofprogress. – White – Undiscovered. – Gray – Discovered but not finished. – Black – Finished. • Colors are required only to reason about the algorithm. Can be implemented without colors. 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. – p[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. rs tu Example (BFS) ¥0¥¥ ¥¥¥¥ vwxy Q: s 0 rs 10 tu ¥¥ Example (BFS) ¥1¥¥ vwxy Q: w r 11 rs 10 tu 2¥ Example (BFS) ¥12¥ vwxy Q: r t x 122 Example (BFS) rs 10 2¥ vwxy tu 2¥ 21 Q: t x v 222 rs tu Example (BFS) 1023 2¥ vwxy 21 Q: x v u 223 rs tu Example (BFS) 1023 23 vwxy 21 Q: v u y 233 rs tu Example (BFS) 1023 23 vwxy 21 Q: u y 33 rs tu Example (BFS) 1023 23 vwxy 21 Q: y 3 rs tu Example (BFS) 1023 21 23 vwxy Q: Æ rs tu Example (BFS) 1023 21 23 vwxy BF Tree Analysis of BFS • InitializationtakesO(V). • TraversalLoop – After initialization, each vertex is enqueued and dequeued at most once, and each operation takes O(1). So, total time for queuing is O(V). – The adjacency list of each vertex is scanned at most once. The sum of lengths of all adjacency lists is Q(E). • Summingupoverallvertices⇒totalrunningtimeof BFS is O(V+E), linear in the size of the adjacency list representation of graph. Depth-first Search (DFS) • Exploreedgesoutofthemostrecentlydiscovered vertex v. • Whenalledgesofvhavebeenexplored,backtrackto explore other edges leaving the vertex from which v was discovered (its predecessor). • “Search as deep as possible first.” • Continueuntilallverticesreachablefromtheoriginal source are discovered. • Ifanyundiscoveredverticesremain,thenoneofthem is chosen as a new source and search is repeated from that source. Depth-first Search • Input:G=(V,E),directedorundirected.Nosourcevertex given. • Output: – 2timestampsoneachvertex.Integersbetween1and2|V|. • d[v] = discovery time (v turns from white to gray) • f [v] = finishing time (v turns from gray to black) – p[v] : predecessor of v = u, such that v was discovered during the scan of u’s adjacency list. • UsesthesamecoloringschemeforverticesasBFS. Pseudo-code DFS-Visit(u) 1. 2. 3. 4. 5. 6. 7. 8. 9. color[u] ¬ GRAY # White vertex u has been discovered time ¬ time + 1 d[u] ¬ time for each v Î Adj[u] do if color[v] = WHITE then p[v] ¬ u DFS-Visit(v) color[u] ¬ BLACK # Blacken u; it is finished. f[u] ¬ time ¬ time + 1 DFS(G) 1. 2. 3. 4. 5. 6. 7. for each vertex u Î V[G] do color[u] ¬ white p[u] ¬ NIL time¬0 for each vertex u Î V[G] do if color[u] = white then DFS-Visit(u) Uses a global timestamp time. Example (DFS) uv 1/ w xyz Example (DFS) uv 1/ w 2/ xyz Example (DFS) uv 1/ w 2/ 3/ xyz Example (DFS) uv 1/ w 2/ 4/ 3/ xyz Example (DFS) uv 1/ B w 2/ 4/ 3/ xyz Example (DFS) uv 1/ B w 2/ 4/5 3/ Starting time d(x) xyz Finishing time f(x) Example (DFS) uv 1/ B 4/5 3/6 xyz w 2/ Example (DFS) uv 1/ B 4/5 3/6 xyz w 2/7 Example (DFS) uv 1/ B 4/5 3/6 xyz w 2/7 F Example (DFS) uv 1/8 B 4/5 3/6 xyz w 2/7 F Example (DFS) uv 1/8 F w 2/7 9/ B 4/5 3/6 xyz Example (DFS) uv 1/8 F w 2/7 9/ BC 4/5 3/6 xyz Example (DFS) uv 1/8 F w 2/7 9/ BC 4/5 3/6 10/ xyz Example (DFS) uv 1/8 F w 2/7 9/ BC 4/5 3/6 10/ xyz B Example (DFS) uv 1/8 F w 2/7 9/ BC 4/5 3/6 10/11 B xyz Example (DFS) uv w 1/8 F 2/7 9/12 BC 4/5 3/6 10/11 B xyz Analysis of DFS • Loopsonlines1-2&5-7takeQ(V)time,excludingtime to execute DFS-Visit. • DFS-VisitiscalledonceforeachwhitevertexvÎVwhen it’s painted gray the first time. Lines 3-6 of DFS-Visit is executed |Adj[v]| times. The total cost of executing DFS-Visit is åvÎV|Adj[v]| = Q(E) • TotalrunningtimeofDFSisQ(V+E). Example (DFS) uv w 1/8 F 2/7 9/12 BC 4/5 3/6 10/11 B Starting time d(x) xyz Finishing time f(x) Parenthesis Theorem Theorem 1: For all u, v, exactly one of the following holds: 1. d[u] < f [u] < d[v] < f [v] or d[v] < f [v] < d[u] < f [u] and neither u nor v is a descendant of the other. 2. d[u] < d[v] < f [v] < f [u] and v is a descendant of u. 3. d[v] < d[u] < f [u] < f [v] and u is a descendant of v. w So d[u] < d[v] < f [u] < f [v] cannot happen. w Like parentheses: w OK: ( ) [ ] ( [ ] ) [ ( ) ] w Not OK: ( [ ) ] [ ( ] ) Corollary v is a proper descendant of u if and only if d[u] < d[v] < f [v] < f [u]. Example (Parenthesis Theorem) yzst 3/6 2/9 1/10 11/16 B 14/15 u BF 4/5 C 7/8 C 12/13 C C xwv (s (z (y (x x) y) (w w) z) s) (t (v v) (u u) t)