Coding Interview Club

Prepare for coding interviews in simple and structured steps

Depth First Search (DFS) Graph Algorithm

Category: 
Problem: 

Provide Depth First Search (DFS) Graph Algorithm.

Approach: 

Depth First Search (DFS) is a graph traversal algorithm where we scan until we reach the depth (leaf node) through any path and then the next path and so on. Forms of tree traversals such as inorder, preorder and post order are a forms of DFS. 

Solution: 

void search (Node root){

  if(root == null)

    return;

  visit(root);

  root.visited = true;

 

  for each (Node n in root.adjacent){

    if(n.visited ==false)

      search(n);

   }

}

 

Unlike trees, Grahs nodes can have path to any other node even forming cycles. Hence, when working with Graph, we must also check if the node has been already visited to avoid infinite loops. In our DFS algorithm we check this using the visited flag. 

 

Usage

DFS is easiest if we want to visit every node in the graph or every node until we find what we want.

DFS is not ideal, if we have a large tree and want to quit when we are too far from the original node.

Back to Top