Home » Graphs(We Run Facebook) » Depth-First Search

# Depth-First Search

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 (uv) such that u is gray and v is white when edge (uv) 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 (uv)
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 );
}
}

return false;
}

&nbsp;

```

### Website #### arpit tak

I like JAVA . I code. I chill. I blog.I eat. I sleep. I dream.