Depth-first search
Revision as of 01:18, 10 September 2014 by Luedecke (talk | contribs) (Luedecke moved page Depth First Search to Depth-First Search)
Definition
Pseudocode
DFS(G)
- for each vertex u ∈ V [G]
- do color[u] ← WHITE
- π[u] ← NIL
- do color[u] ← WHITE
- time ← 0
- do if color[u] == WHITE
- then DFS-VISiT(u)
- do if color[u] == WHITE
DFS-VISIT(u)
- color[u] ← GRAY
- time ← time + 1
- d[u] ← time
- for each v ∈ Adj[u]
- do if color[v] = WHITE
- then π [v] ← u
- DFS-VISIT(v)
- then π [v] ← u
- do if color[v] = WHITE
- color[u] ← BLACK
- f[u] ← time ← time + 1