Depth-first search: Difference between revisions
Jump to navigation
Jump to search
| Line 8: | Line 8: | ||
==== DFS(''G'') ==== | ==== DFS(''G'') ==== | ||
:'''for''' each vertex ''u'' ∈ ''V'' [''G''] | :'''for''' each vertex ''u'' ∈ ''V'' [''G''] | ||
::'''do''' color[ | ::'''do''' color[''u''] ← WHITE | ||
::: ''π''[''u''] ← NIL | ::: ''π''[''u''] ← NIL | ||
:''time'' ← 0 | :''time'' ← 0 | ||
Revision as of 11:03, 15 August 2014
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