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. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.

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.

The following diagram illustrate depth first search traversal of a tree.

dfs
depth first search visualization

The red color indicates visited nodes, while the yellow circle movement is illustrating the backtracking process.

DFS algorithm uses stack to keep track of the visited nodes.

We add the visited node to the stack during the process of exploring the depth and use it to traverse back to the root node or any other sub-root node for the need of exploring the next unvisited branch.

DFS using Stack
DFS using Stack

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

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.

Here is the implementation of the DFS algorithm in C, C++, and Java.

C

C++

Java

The tree connection which 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