Depth-first search: Difference between revisions
Jump to navigation
Jump to search
| Line 13: | Line 13: | ||
:: '''do if''' ''color''[''u''] == WHITE | :: '''do if''' ''color''[''u''] == WHITE | ||
::: '''then''' DFS-VISiT(''u'') | ::: '''then''' DFS-VISiT(''u'') | ||
====DFS-VISIT(''u'')==== | ====DFS-VISIT(''u'')==== | ||
| Line 19: | Line 21: | ||
: ''d''[''u''] ← ''time'' | : ''d''[''u''] ← ''time'' | ||
: '''for''' each ''v'' ∈ ''Adj''[''u''] | : '''for''' each ''v'' ∈ ''Adj''[''u''] | ||
:: '''do if''' ''color''[''v''] = WHITE | |||
::: ''' then ''' π [''v''] ← ''u'' | |||
:::: DFS-VISIT(''v'') | |||
:''color''[''u''] ← BLACK | |||
:''f''[''u''] ← ''time'' ← ''time'' + 1 | |||
Revision as of 17:11, 14 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