Coders Packet

Implementation of Depth-First-Search (DFS) algorithm using Java

By Abhishek Birendra Verma

In this tutorial, we will learn about the Depth-First-Search algorithm and we will also see the program to implement the Depth-First-Search algorithm using Java.

 
 
 
 

Depth-first search (DFS) is an algorithm for which is used for traversing a tree or graph. The algorithm starts at the root node (which can be any node in a graph) and it keeps exploring the same route/path until it reaches the leaf node and after reaching the leaf node it backtracks along the same path until it finds an unvisited node and then it starts traversing that node until it reaches the leaf node/dead-end/visited node. This process keeps repeating until all the nodes are visited.

Backtracking means that when you are moving forward and there are no more nodes to traverse along the current path then you move back on the same path to find new unvisited nodes to traverse. DFS uses a stack for this purpose to keep track of the nodes that are yet to be visited.

The Worst-Case Time Complexity of DFS is O(V+E) where V is the total number of vertices and E is the total number of edges. Please note that to avoid visiting the already visited nodes more than once, the algorithm uses a Boolean “visited “array.

Output:

import java.util.Scanner;
import java.util.Stack;
  public class DFS {

    public static void main(String[] args) {
      // TODO Auto-generated method stub
      Scanner sc=new Scanner(System.in);
      Stack stack1=new Stack();
      System.out.print("Enter the total number of vertices in the graph: ");
      int vertices=sc.nextInt();
      boolean visited[]=new boolean[vertices];
      int adj[][]=new int[vertices][vertices],i,j,count=1,starting_vertex;
      System.out.println("Enter the elements of adjacency matrix: ");
      System.out.println("Enter 0 if Edge does not Exists\nEnter 1 if Edge exists");
      for(i=0;i<vertices;i++) {
        
        for(j=0;j<vertices;j++) {
          System.out.print("Enter Adj["+(i+1)+"]["+(j+1)+"]:");
          adj[i][j]=sc.nextInt();
        }
      }
      System.out.print("Enter the Starting vertex:");
      starting_vertex=sc.nextInt()-1;
      if(starting_vertex<0||starting_vertex>=vertices) {
        System.out.println("Incorect value!! Try again");
        System.exit(1);
      }
      //Putting the starting vertex into the stack	
      stack1.push(starting_vertex);
      visited[starting_vertex]=true;
      System.out.println("Depth First Search is:");
      System.out.print(starting_vertex+1);
      System.out.print("-->");
      while(!stack1.isEmpty()) {
        //Selecting the top node in the stack to visit it and explore as far as possible along the same path/branch
        i=stack1.peek();
          for(j=0;j<adj.length;j++) {
            if(adj[i][j]!=0&&!visited[j]) {
              stack1.push(j);
              visited[j]=true;
              //Printing the node after visiting it
              System.out.print(j+1);
              if(count<vertices-1) {
                System.out.print("-->");
                count++;
              }
              i=j;
              j=0;
            }
              
          }
          //As the node has been visited so removing it from the stack
          stack1.pop();		
      }
      
    }

  }

 

Download project

Reviews Report

Submitted by Abhishek Birendra Verma (AbhishekVerma)

Download packets of source code on Coders Packet