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.

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.

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

int i, visited[MAX];
char vertex[MAX];

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()
{
vertex = 'A';
vertex = 'B';
vertex = 'C';
vertex = 'D';
vertex = '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}{}

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()
{
Vertex v1('A'), v2('B'),v3('C'),v4('D'),v5('E');

//Connecting vertex OR assigning neighbor

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;
boolean visited;

Vertex(char value){
this.value =value;
visited = false;
}

//Bidirectional edge (this <---> v)
}

public void display(){
System.out.print(this.value+" ");
}
}

class DFS{
public void solve(Vertex root){

root.visited = true;
root.display();

//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