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

-The time complexity is [clr98].

		Next
		Bibliography