Lecture 14 Graphs II: DFS 6.006 Fall 2011 Lecture 14: Graphs II: Depth-First Search Lecture Overview • Depth-First Search • Edge Classification • Cycle Testing • Topological Sort Recall: • graph search: explore a graph e.g., find a path from start vertex s to a desired vertex • adjacency lists: array Adj of |V | linked lists – for each vertex u ∈ V , Adj[u] stores u’s neighbors, i.e., {v ∈ V | (u, v) ∈ E} (just outgoing edges if directed) For example: a b c a c b c c b Adj Figure 1: Adjacency Lists Breadth-first Search (BFS): Explore level-by-level from s — find shortest paths 1 a Lecture 14 Graphs II: DFS 6.006 Fall 2011 Depth-First Search (DFS) This is like exploring a maze. s Figure 2: Depth-First Search Frontier Depth First Search Algorithm • follow path until you get stuck • backtrack along breadcrumbs until reach unexplored neighbor • recursively explore • careful not to repeat a vertex } parent = {s: None} DFS-visit (V, Adj, s): start for v in Adj [s]: if v not in parent: v parent [v] = s finish DFS-visit (V, Adj, v) v DFS (V, Adj) parent = { } for s in V: if s not in parent: parent [s] = None DFS-visit (V, Adj, s) } search from start vertex s (only see stuff reachable from s) explore entire graph (could do same to extend BFS) Figure 3: Depth-First Search Algorithm 2 Lecture 14 Graphs II: DFS 6.006 Fall 2011 Example S1 forward edge 1 a b 5 c 2 4 back edge 8 d 3 cross edge S2 6 f e 7 back edge Figure 4: Depth-First Traversal Edge Classification tree edges (formed by parent) nontree edges back edge: to ancestor forward edge: to descendant cross edge (to another subtree) Figure 5: Edge Classification • to compute this classification (back or not), mark nodes for duration they are “on the stack” • only tree and back edges in undirected graph Analysis • DFS-visit gets called withX a vertex s only once (because then parent[s] set) =⇒ time in DFS-visit = |Adj[s]| = O(E) s∈V • DFS outer loop adds just O(V ) =⇒ O(V + E) time (linear time) 3 Lecture 14 Graphs II: DFS 6.006 Fall 2011 Cycle Detection Graph G has a cycle ⇔ DFS has a back edge Proof (<=) tree edges is a cycle back edge: to tree ancestor (=>) consider first visit to cycle: v3 v2 vk v1 v0 FIRST! • before visit to vi finishes, will visit vi+1 (& finish): will consider edge (vi , vi+1 ) =⇒ visit vi+1 now or already did • =⇒ before visit to v0 finishes, will visit vk (& didn’t before) • =⇒ before visit to vk (or v0 ) finishes, will see (vk , v0 ) as back edge Job scheduling Given Directed Acylic Graph (DAG), where vertices represent tasks & edges represent dependencies, order tasks without violating dependencies 4 Lecture 14 Graphs II: DFS 8 G H 7 I 4 A 6.006 Fall 2011 9 2 3 C B D F 1 E 6 5 Figure 6: Dependence Graph: DFS Finishing Times Source: Source = vertex with no incoming edges = schedulable at beginning (A,G,I) Attempt: BFS from each source: • from A finds A, BH, C, F • from D finds D, BE, CF ← slow . . . and wrong! • from G finds G, H • from I finds I Topological Sort Reverse of DFS finishing times (time at which DFS-Visit(v) finishes)                  5 DFS-Visit(v) ... order.append(v) order.reverse() Lecture 14 Graphs II: DFS Correctness For any edge (u, v) — u ordered before v, i.e., v finished before u u v • if u visited before v: – before visit to u finishes, will visit v (via (u, v) or otherwise) – =⇒ v finishes before u • if v visited before u: – graph is acyclic – =⇒ u cannot be reached from v – =⇒ visit to v finishes before visiting u 6 6.006 Fall 2011