Java Program to Traverse a Graph using DFS

«
»

This is the Java Program to do a Depth First Search/Traversal on a graph non-recursively.

Problem Description

Given a graph in the form of an adjacency matrix and a source vertex, write a program to perform a depth-first search of the graph. In depth-first search traversal, neighbours of a node are traversed first.

Problem Solution

The idea is to store the source vertex in the stack. Now, iterate through the stack until it is empty. For every vertex retrieved from the stack, check which of its neighbours are still not processed. Traverse the first encountered neighbour after adding the current vertex to the stack.

Program/Source Code

Here is the source code of the Java Program to do a Depth First Search/Traversal on a graph non-recursively. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.

  1.  
  2. //Java Program to do a Depth First Search/Traversal on a graph non-recursively
  3.  
  4. import java.io.BufferedReader;
  5. import java.io.IOException;
  6. import java.io.InputStreamReader;
  7. import java.util.Stack;
  8.  
  9. public class DepthFirstSearch {
  10.     // Function to perform depth first search
  11.     static void depthFirstSearch(int[][] matrix, int source){
  12.         boolean[] visited = new boolean[matrix.length];
  13.         visited[source-1] = true;
  14.         Stack<Integer> stack = new Stack<>();
  15.         stack.push(source);
  16.         int i,x;
  17.         System.out.println("The depth first order is");
  18.         System.out.println(source);
  19.         while(!stack.isEmpty()){
  20.             x = stack.pop();
  21.             for(i=0; i<matrix.length; i++){
  22.                 if(matrix[x-1][i] == 1 && visited[i] == false){
  23.                     stack.push(x);
  24.                     visited[i] = true;
  25.                     System.out.println(i+1);
  26.                     x = i+1;
  27.                     i = -1;
  28.                 }
  29.             }
  30.         }
  31.     }
  32.     // Function to read user input
  33.     public static void main(String[] args) {
  34.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  35.         int vertices;
  36.         System.out.println("Enter the number of vertices in the graph");
  37.         try{
  38.             vertices = Integer.parseInt(br.readLine());
  39.         }catch(IOException e){
  40.             System.out.println("An error occurred");
  41.             return;
  42.         }
  43.         int[][] matrix = new int[vertices][vertices];
  44.         System.out.println("Enter the adjacency matrix");
  45.         int i,j;
  46.         for(i=0; i<vertices; i++){
  47.             for(j=0; j<vertices; j++){
  48.                 try{
  49.                     matrix[i][j] = Integer.parseInt(br.readLine());
  50.                 }catch (IOException e){
  51.                     System.out.println("An error occurred");
  52.                 }
  53.             }
  54.         }
  55.         int source;
  56.         System.out.println("Enter the source vertex");
  57.         try{
  58.             source = Integer.parseInt(br.readLine());
  59.         }catch(IOException e){
  60.             System.out.println("An error occurred");
  61.             return;
  62.         }
  63.         depthFirstSearch(matrix,source);
  64.     }
  65. }
Program Explanation

1. In function depthFirstSearch(), a boolean array is created and visited value of the source is set to true.
2. Then a stack is created and source vertex is added to it.
3. The loop while(!stack.isEmpty()) traverses until the stack is empty.
4. The nested loop for(i=0; i&ltmatrix.length; i++) traverses through all the neighbours of the currently popped vertex from the stack.
5. The condition if(matrix[x-1][i] == 1 && visited[i] == false) looks for all the neighbours of the currently polled vertex and traverses the first non-visited neighbour after pushing the current vertex to the stack.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

Time Complexity: O(n2) where n is the number of elements in the array.

Runtime Test Cases
 
Case 1 (Simple Test Case):
 
Enter the number of vertices in the graph
4
Enter the adjacency matrix
1
1
1
1
1
0
0
0
1
1
1
0
0
0
0
1
Enter the source vertex
2
The depth first order is
2
1
3
4
 
Case 2 (Simple Test Case - another example):
 
Enter the number of vertices in the graph
3
Enter the adjacency matrix
0
0
0
1
0
1
1
1
1
Enter the source vertex
3
The depth first order is
3
1
2

Sanfoundry Global Education & Learning Series – Java Programs.

Take Java Programming Practice Tests - Chapterwise!
Start the Test Now: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.