DFS: Depth-first search Properties of depth-first search F-To search as" deeper as possible Ea Theorem 22.7(Parenthesis theorem) for If there is more edges can explore during the any different vertices u and v in a graph, search, explore it. 2-DFS result The(d[u, fu) and (d(vl, fvI are disjoint or aIt compo DFS forest by a predecessor one contains another entirely 1. If(dqu, fu) contains(d[v fvn entirely, then v is (rvv)v∈ V and=nu the descendent of u in a depth- first tree,反之亦 the depth-first forest I the tree edges f(du fu) and (dv. fiv) are disjoint, then u and Theorem 22.9(White path theorem) Classification of edges S-Vertex v is a descendent of u. if at the ≥: Tree edges discovery time d[u of u, vertex v can be - Back edges reached from u along a path consisting entirely of white vertices Forward edges Cross edges Concepts on topological sort Topological sort ErOn a DAG-directed acyclic graph, it can Topological-sort(G) sort the vertices in an ordered sequence such that all of the edges is a subset of 1. Call DFS(G) l(u,v): u appears earlier than v At each vertex is finished, insert it onto the front of a linked list 3 Return the linked list8 清华大学 宋斌恒 43 DFS: Depth DFS: Depth-first search first search To search as “deeper” as possible: If there is more edges can explore during the search, explore it. DFS result: It composes a DFS forest by a predecessor π. Gπ=(V,Eπ), where Eπ={(π[v],v): v ∈ V and π[v] != null} Gπ call the depth-first forest Eπ call the tree edges 清华大学 宋斌恒 44 Properties of depth Properties of depth-first search first search Theorem 22.7 (Parenthesis theorem) for any different vertices u and v in a graph, after a DFS, it satisfies: 1. The (d[u],f[u]) and (d[v],f[v]) are disjoint or one contains another entirely. 1. If (d[u],f[u]) contains (d[v],f[v]) entirely, then v is the descendent of u in a depth-first tree，反之亦 然 2. If (d[u],f[u]) and (d[v],f[v]) are disjoint, then u and v are not descendent each other. 清华大学 宋斌恒 45 Theorem 22.9 (White path Theorem 22.9 (White path theorem) theorem) Vertex v is a descendent of u, if at the discovery time d[u] of u, vertex v can be reached from u along a path consisting entirely of white vertices. 清华大学 宋斌恒 46 Classification of edges Classification of edges Tree edges Back edges Forward edges Cross edges 1/8 2/7 9/12 4/5 3/6 10/11 清华大学 宋斌恒 47 Concepts on topological sort Concepts on topological sort On a DAG – directed acyclic graph, it can sort the vertices in an ordered sequence such that all of the edges is a subset of {(u,v): u appears earlier than v} 1/8 2/7 9/12 4/5 3/6 10/11 1/8 2/7 9/12 4/5 3/6 10/11 清华大学 宋斌恒 48 Topological sort Topological sort Topological-sort(G) 1. Call DFS(G) 2. At each vertex is finished, insert it onto the front of a linked list 3. Return the linked list