Depth-first search

From Algowiki
Revision as of 22:43, 11 September 2014 by Luedecke (talk | contribs)
Jump to navigation Jump to search

Definition

Pseudocode

DFS(G)

for each vertex uV [G]
do color[u] ← WHITE
π[u] ← NIL
time ← 0
do if color[u] == WHITE
then DFS-VISiT(u)


DFS-VISIT(u)

color[u] ← GRAY
timetime + 1
d[u] ← time
for each vAdj[u]
do if color[v] = WHITE
then π [v] ← u
DFS-VISIT(v)
color[u] ← BLACK
f[u] ← timetime + 1