Algorithm Depth-First Search
The DFS forms a depth-first forest comprised of more than one depth-first trees. Each tree is made of edges (u, v) such that u is gray and v is white when edge (u, v) is explored. The following pseudocode for DFS uses a global timestamp time.
DFS (V, E)
1. for each vertex u in V[G]
2. do color[u] ← WHITE
3. π[u] ← NIL
4. time ← 0
5. for each vertex u in V[G]
6. do if color[u] ← WHITE
7. then DFS-Visit(u) ▷ build a new DFS-tree from u
DFS-Visit(u)
1. color[u] ← GRAY ▷ discover u
2. time ← time + 1
3. d[u] ← time
4. for each vertex v adjacent to u ▷ explore (u, v)
5. do if color[v] ← WHITE
6. then π[v] ← u
7. DFS-Visit(v)
8. color[u] ← BLACK
9. time ← time + 1
10. f[u] ← time ▷ we are done with u
Example (CLRS): In the following figure, the solid edge represents discovery or tree edge and the dashed edge shows the back edge. Furthermore, each vertex has two time stamps: the first time-stamp records when vertex is first discovered and second time-stamp records when the search finishes examining adjacency list of vertex.
Analysis
The analysis is similar to that of BFS analysis. The DFS-Visit is called (from DFS or from itself) once for each vertex in V[G] since each vertex is changed from white to gray once. The for-loop in DFS-Visit is executed a total of |E| times for a directed graph or 2|E| times for an undirected graph since each edge is explored once. Moreover, initialization takes Θ(|V|) time. Therefore, the running time of DFS is Θ(V + E).
public static boolean search( Node node, int value ) { // Check if it's an empty tree. if( node == null ) { return false; } Stack<Node> stack = new Stack<Node>( ); stack.push( node ); Node nn = stack.peek( ); System.out.print(" current node"+nn.data); while( ! stack.isEmpty( ) ) { Node currentNode = stack.pop( ); // To remove and return the top element, call pop(). System.out.print(" "+currentNode.data); if( currentNode.data == value ) { // Found the value! return true; } if( currentNode.right != null ) { stack.push( currentNode.right ); } if( currentNode.left != null ) { stack.push( currentNode.left ); } } // Not found. return false; }