DFS: Depth-first search 1. DFS(G) For each vertex u∈vl S-visit(u white then7 清华大学 宋斌恒 37 DFS: Depth DFS: Depth-first search first search 1/12 2/11 4/5 3/10 15/16 13/14 6/7 8/9 清华大学 宋斌恒 38 1. DFS(G) 1. For each vertex u ∈ V[G] 1. color[u]Åwhite 2. π[u]Ånull 2. timeÅ0 3. For each vertex u ∈ V[G] 1. If color[u] == white then DFS-Visit(u) 2. DFS-Visit(u) 1. color[u]Ågrey 2. time++ 3. d[u]Åtime 4. For each v ∈ Adj[u] 1. If color[v] == white then 1. π[v]Åu 2. DFS-Visit(v) 5. color[u]Åblack 6. time++ 7. f(u)Åtime 清华大学 宋斌恒 39 1/ 1/ 2/ 1/ 2/ 3/ 1/ 2/ 4/ 3/ 清华大学 宋斌恒 40 1/ 2/ 4/ 3/ 1/ 2/ 4/5 1/ 2/ 4/5 3/6 1/ 2/7 3/ 4/5 3/6 清华大学 宋斌恒 41 1/ 2/7 4/5 3/6 1/8 2/7 4/5 3/6 1/8 2/7 9/ 4/5 3/6 1/8 2/7 9/ 4/5 3/6 清华大学 宋斌恒 42 1/8 2/7 9/ 4/5 3/6 10/ 1/8 2/7 9/ 4/5 3/6 10/ 1/8 2/7 9/ 4/5 3/6 10/11 1/8 2/7 9/12 4/5 3/6 10/11