Summary: In this tutorial, we will learn what is Depth First Search and how to traverse a graph or tree using Depth First Search in C, C++, and Java.

Introduction to Depth First Search

Depth First Search (DFS) is an algorithm for traversing or searching tree or graph data structures.

Wikipedia

DFS starts from the root node (or any arbitrary node as the root node) and explores as far as possible along each branch in depth before backtracking.

dfs
depth first search visualization

Depth First Search uses stack to keep track of the visited nodes.

We add the visited node to the stack in the process of exploring the depth.

Using the same stack we traverse back to the root node or any other sub-root node for the need of exploring the next unvisited branch.

Although we can use an explicit stack to store visited nodes, it is recommended to use recursion to implement DFS because recursion implements backtracking in easy way.

Here is the DFS algorithm that describes the process of traversing any graph or tree.

Depth First Search Algorithm

  1. Visit the 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 its child.
  4. Repeat the process (Step 3) until you reach the node which does not have any child i.e. leaf node.
  5. At the leaf node traverse back 1 level to its 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. End if all nodes are visited.

Depth First Search Program

C

C++

Java

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.

In this tutorial, we learned Depth First Seach and its implementation in C, C++, and Java. Check out Breadth-first search tutorial if you haven’t.

Leave a Reply