Depth First Search – DFS

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

dfs

  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 C++ Code

Output

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.

admin

I am a B.tech IT Student from India. Technology and programming is the most enthusiastic thing for me in this world. I like learning new techniques and use them for real-world application because I feel tech is future. Let's learn and grow TOGETHER.

Leave a Reply

Close Menu
shares