Depth-first search algorithm DFSI(G 1. for each vertex u∈G do color←WHTE x[←NIL 4.time←-0 5. for each vertex u∈G do if color[u]=WHITE LO( then dfS-Visit(u times
Depth-f hl h irst search algorithm DFS(G) 1. for each vertex u ∈ V[G] 2. do color[u] ← WHITE 3. π[u] ← NIL 4. time ← 0 5. for each vertex u ∈ V[G] 6 d if l [ ] WHITE O(V) 6. do if color[u] = WHITE 7. then DFS-VISIT(u) ( ) times
Depth-first search algorithm DFS-VISIT(u 1. color[a←GRAY 2.tine←time+1 3.al←time 4. for each vertex v E Adjlu 567 do if color[v]=WHITE O(E) then v]←l times DFS-VISIT(v 8. color[]← BLACK 9.ful←time←time+1 Running time is O(+ E)
Depth-f hl h irst search algorithm DFS-VISIT(u) 1. color[u] ← GRAY 2. time ← time + 1 3. d[u] ← time 4. for each t ver ex v ∈ Adj[u] 5. do if color[v] = WHITE 6 th [ ] O(E) 6. then π[v] ← u i 7. DFS-VISIT(v) 8 l [ ] BLACK times 8. color[u] ← BLACK 9. f[u] ← time ← time + 1 Running time is O(V + E)
Predecessor subgraph of DFS B Predecessor subgraph of dfs is Gr-V, Er, where En={(x[vv)v∈ and v≠NIL
Pred b hf S decessor su bgrap h o f DF S u w v z C B y F B Pd b h f DFS i y Pre decessor su bgrap h o f DFS is G π = ( V, Eπ ), where x Eπ = { ( π [ v], v): v ∈ V an d π [ v] ≠ NIL }
Predecessor subgraph of DFS Each edge(u, v)can be classified by the color of the b vertex y that is reached when the edge is first explored F WHITE indicates a tree edge, B GRAY indicates a back edge BLACK indicates a forward (if du< dlv) or cross edge (if d[u>dvD
Pred b hf S decessor su bgrap h o f DF S u w Each edge ( u, v ) can be classified by the color of the v z C B vertex v that is reached when the edge is first explored: y F B y WHITE indicates a tree edge; y GRAY indicates a back edge; i di f d y y BLAC K i ndicates a forwar d (if d [ u] < d [ v ]) or cross edge x (if d [ u ] > d [ v ] )
Precedence among events Underwear Socks Watch Pants Shoes Shirt Belt Tie Jacket
Precedence among events Underwear Socks Watch Pants Shoes Shirt Belt Tie Jacket