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