How to perform Depth First Search in Java?

By Tanisha Saxena

In this tutorial, we will learn how to perform Depth First Search or DFS on a graph in java. There are two ways to traverse a graph:

  • Breadth first search
  • Depth first search

DFS – Depth First Search in Java

DFS can be implemented in two ways:

  1. Recursive
  2. Iterative

Iterative Approach to perform DFS

Depth-first search can be implemented using iteration.

public  void dfs(Node node)
  {
    Stack<Node> stack=new  Stack<Node>();
    stack.add(node);
    node.visited=true;
    while (!stack.isEmpty())
    {
      Node ele=stack.pop();
      System.out.print(ele.data + " ");
 
      List<Node> neighbour_nodes=ele.getNeighbours();
      for (int i = 0; i < neighbour_nodes.size(); i++) {
        Node n=neighbour_nodes.get(i);
        if(n!=null && !n.visited)
        {
          stack.add(n);
          n.visited=true;
 
        }
      }
    }
  }

Recursive Approach to perform DFS

Depth first search can be implemented using recursion as well. We do not need to maintain external stack, it will be taken care of by recursion.

public  void dfs(Node node)
  {
    System.out.print(node.data + " ");
    List neighbour_nodes=node.getNeighbours();
        node.visited=true;
    for (int i = 0; i < neighbour_nodes.size(); i++) {
      Node n=neighbour_nodes.get(i);
      if(n!=null && !n.visited)
      {
        dfs(n);
      }
    }
  }

Now, that we have seen both the approaches to solve our problem. We will implement the entire program in java. There are two ways to represent a graph:

  • Using Neighbours List
  • Using Adjacency Matrix
 We will write our program using adjacency matrix approach.
import java.util.*;
public class Main
{ 
  static ArrayList<Node> nodesList=new ArrayList<>();
  static class Node
  {
    int data;
    boolean visited;
 
    Node(int data)
    {
      this.data=data;
 
    }
  }
  public ArrayList<Node> findNeighbours(int adjacency_matrix[][],Node x)
  {
    int nodeIndex=-1;
 
    ArrayList<Node> neighbour_nodes=new ArrayList<>();
    for (int i = 0; i < nodesList.size(); i++) {
      if(nodesList.get(i).equals(x))
      {
        nodeIndex=i;
        break;
      }
    }
 
    if(nodeIndex!=-1)
    {
      for (int j = 0; j < adjacency_matrix[nodeIndex].length; j++) {
        if(adjacency_matrix[nodeIndex][j]==1)
        {
          neighbour_nodes.add(nodesList.get(j));
        }
      }
    }
    return neighbour_nodes;
  }
 
 
  // Recursive 
  public  void dfs(int adjacency_matrix[][], Node node)
  {
 
    System.out.print(node.data + " ");
    ArrayList<Node> neighbour_nodes=findNeighbours(adjacency_matrix,node);
        node.visited=true;
    for (int i = 0; i < neighbour_nodes.size(); i++) {
      Node n=neighbour_nodes.get(i);
      if(n!=null && !n.visited)
      {
        dfs(adjacency_matrix,n);
      }
    }
  }
 
  // Iterative 
  public  void dfsIterative(int adjacency_matrix[][], Node node)
  {
    Stack<Node> stack=new  Stack<>();
    stack.add(node);
    node.visited=true;
    while (!stack.isEmpty())
    {
      Node element=stack.pop();
      System.out.print(element.data + " ");
 
      ArrayList<Node> neighbour_nodes=findNeighbours(adjacency_matrix,element);
      for (int i = 0; i < neighbour_nodes.size(); i++) {
        Node n=neighbour_nodes.get(i);
        if(n!=null &&!n.visited)
        {
          stack.add(n);
          n.visited=true;
 
        }
      }
    }
  }
 
  public static void main(String arg[])
  {
 
    Node node40 =new Node(40);
    Node node10 =new Node(10);
    Node node20 =new Node(20);
    Node node30 =new Node(30);
    Node node60 =new Node(60);
    Node node50 =new Node(50);
    Node node70 =new Node(70);
 
    nodesList.add(node40);
    nodesList.add(node10);
    nodesList.add(node20);
    nodesList.add(node30);
    nodesList.add(node60);
    nodesList.add(node50);
    nodesList.add(node70);
    int adjacency_matrix[][] = {
        {0,1,1,0,0,0,0},
        {0,0,0,1,0,0,0}, 
        {0,1,0,1,1,1,0},  
        {0,0,0,0,1,0,0}, 
        {0,0,0,0,0,0,1}, 
        {0,0,0,0,0,0,1},  
        {0,0,0,0,0,0,0},  
    };
 
    Main obj = new Main();
 
    System.out.println("The DFS traversal(Iterative) ");
    obj.dfsIterative(adjacency_matrix, node40);
 
    System.out.println();
    clearVisitedFlags();
 
    System.out.println("The DFS traversal(Recursion) ");
    obj.dfs(adjacency_matrix, node40);
 
  }
 
  public static void clearVisitedFlags()
  {
    for (int i = 0; i < nodesList.size(); i++) {
      nodesList.get(i).visited=false;
    }
  }
}

Output:

The DFS traversal of the graph using stack 
40 20 50 70 60 30 10 
The DFS traversal of the graph using recursion 
40 10 30 60 70 20 50

We hope you have learned how to perform DFS or Depth First Search Algorithm in Java.

Also Read,

Java Program to find the difference between two dates

Leave a Reply