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

#include <stdio.h>
#include <stdlib.h>
#define MAX 10

//DFS using Adjacency Matrix
 
int i, visited[MAX];
char vertex[MAX];
 
//adjacency matrix
int  graph[MAX][MAX] = {{0,1,0,1,0},
                        {1,0,1,0,0},
                        {0,1,0,0,0},
                        {1,0,0,0,1},
                        {0,0,0,1,0}};
 
void dfs(int currentVertex){
    printf("%c ",vertex[currentVertex]);
    visited[currentVertex] = 1;
 
    for(i=0; i<MAX; i++ ){
        if(visited[i] == 0){
            //Recursive calling dfs() i.e implementing stack
            dfs(i);
        }
    }
}
 
int main()
{
    //Adding vertex to the graph
    vertex[0] = 'A';
    vertex[1] = 'B';
    vertex[2] = 'C';
    vertex[3] = 'D';
    vertex[4] = 'E';
 
    //Assuming Vertex A as root
    dfs(0);
 
    return 0;
}

C++

#include <iostream>
#include <list>
#include <stack>
#include <iterator>
#define Max 10 ;
using namespace std;
 
//Vertex class
class Vertex{
 
public:
    list<Vertex*> neighbors;
    char name;
    bool visited;
 
    Vertex(): name{'\0'},visited{false}{}
    Vertex(char ch): name{ch},visited{false}{}
 
    void addNeighbor(Vertex *v){
        neighbors.push_back(v);
    }
};
 
class DFS{
public:
void dfs(Vertex *currentVertex){
 
    cout << currentVertex->name <<" ";
    list<Vertex*> nbr = currentVertex->neighbors;
 
    //Iterating through each neighbor
    list<Vertex*> :: iterator it;
 
    for(it=nbr.begin(); it != nbr.end();it++ ){
            if(!(*it)->visited){
                (*it)->visited = true;
                //Recursive calling dfs() i.e implementing stack
                dfs(*it);
            }
        }
    }
};
 
int main()
{
    //Adding vertex to the graph
    Vertex v1('A'), v2('B'),v3('C'),v4('D'),v5('E');
 
    //Connecting vertex OR assigning neighbor
    v1.addNeighbor(&v2);
    v1.addNeighbor(&v4);
    v4.addNeighbor(&v5);
    v2.addNeighbor(&v3);
 
    DFS b;
    //Assuming Vertex v1 as root
    b.dfs(&v1);
 
    return 0;
}

Java

import java.util.ArrayList;
import java.util.List;
 
class Vertex{
  char value;
  List<Vertex> adVertex;
  boolean visited;
 
  Vertex(char value){
    this.value =value;
    adVertex = new ArrayList<>();
    visited = false;
  }
 
  public void addAdVertex(Vertex v){
    //Bidirectional edge (this <---> v)
    this.adVertex.add(v);
    v.adVertex.add(this);
  }
 
  public void display(){
    System.out.print(this.value+" ");
  }
}
 
class DFS{
  public void solve(Vertex root){
    
    root.visited = true;
    root.display();
 
    for(Vertex v: root.adVertex){
      //If unvisited go depth recursively
      //otherwise move to next adjacent vertex
      if(!v.visited){
        solve(v);
      }   
    }
  }
}
 
class Main {
  public static void main(String[] args) {
    DFS dfs = new DFS();
 
    //Create Vertices
    Vertex vertexA = new Vertex('A');
    Vertex vertexB = new Vertex('B');
    Vertex vertexC = new Vertex('C');
    Vertex vertexD = new Vertex('D');
    Vertex vertexE = new Vertex('E');
 
    //Join vertices
    vertexA.addAdVertex(vertexB);
    vertexA.addAdVertex(vertexD);
    vertexB.addAdVertex(vertexC);
    vertexD.addAdVertex(vertexE);
 
    //call solve() method
    dfs.solve(vertexA);
  }
}

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

3 × 3 =