Depth first search is an algorithm for traversing or searching tree or graph. In DFS we start from the root node and go as far as possible in each branch before going back (backtracking).

Depth first search is basically the implementation of the stack. We add visited node to the stack in the process of exploring the depth until we reach the leaf node (end of a branch). And using the same stack we traverse back to the root node or any other sub-root node for the exploring next unvisited branch.

In this program, we have used recursion to implement Depth first search because recursion implements the stack.

Depth First Search Algorithm


  1. Choose a root node.
  2. check if the root has any neighbor/child. If yes then visit the child.
  3. Check whether the current node has any neighbor/child. If yes then visit the child.
  4. Repeat the process (Step 3) until you reach the node which does not have any child i.e leaf node.
  5. If you get the leaf node, traverse back 1 level to the parent node and check if it has any child unvisited. If yes then visit the node and repeat step 3 for this node. If not then go back 1 level i.e (repeat step 4).
  6. By doing this you will visit all the node.
  7. End if all nodes are visited.

Depth First Search Program Code




The tree connection we have used in the program:
Depth First Searsh Traversal

Output of Program

depth first search C++

Note: In this tutorial, we are assuming that the graph is connected. For the unconnected graph, this code will give unwanted output.

That’s all for depth-first search algorithm and C++ implementation. Check out Breadth-first search tutorial if you haven’t yet.

Leave a Reply