Depth First Search (DFS)
The DFS method performs a depth--first search [clr98] of a graph. A depth--first search visits vertices that are further to the source before visiting vertices that are closer away. In this context `distance' is defined as the number of edges in the shortest path from the source vertex.
Figure 1. Pseudocode for the DFS algorithm
DFS(G)
{
For each v in V,
{
color[v]=white;
pred[u]=NULL
}
time=0;
For each u in V
If (color[u]=white) DFSVISIT(u)
}
DFSVISIT(u)
{
color[u]=gray;
d[u] = ++time;
For each v in Adj(u) do
If (color[v] = white)
{
pred[v] = u;
DFSVISIT(v);
}
color[u] = black; f[u]=++time;
}
[clr98].