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; }
Next | ||
Bibliography |