Depth first search

Each vertex is initially white, is grayed when it is "discovered" and is blacken when it is "finished", that is, when its adjacency list has been examined completely. Each vertex ends up in exactly one depth-first tree, these trees are disjoint.

Each vertex is timestamps, each vertex has two timestamps : d[v] records when v is first discovered (and grayed), f[v] records when the search finishes examining v's adjacency list (and blackens v). The variable time is a global variable for timestamping.

DFS(G)
1 for each vertex u in V[G]
2   do color[u] = WHITE
3      pi[u] = NIL
4 time = 0
5 for each vertex u in V[G]
6   do if color[u] = WHITE
7        then DFS-visit(u)

DFS-visit(u)
1 color[u] = GRAY // white vertex has just been discovered
2 d[u] = time; time = time + 1
3 for each v in Adj[u]   // explore eage (u,v)
4   do if color[v] = WHITE
5        then pi[v] = u
6             DFS-visit(v)
7 color[u] = BLACK // blacken u; it is finished
8 f[u] = time; time = time + 1