Java Program to Check the Connectivity of Directed Graph using DFS

This Java program,performs the DFS traversal on the given directed graph represented by a adjacency matrix to check connectivity.the DFS traversal makes use of an stack.

Here is the source code of the Java program to check the connectivity of a directed graph. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. import java.util.InputMismatchException;
  2. import java.util.Scanner;
  3. import java.util.Stack;
  4.  
  5. public class DirectedConnectivityDfs
  6. {
  7.     private Stack<Integer> stack;
  8.  
  9.     public DirectedConnectivityDfs() 
  10.     {
  11.         stack = new Stack<Integer>();
  12.     }
  13.  
  14.     public void dfs(int adjacency_matrix[][], int source)
  15.     {
  16.         int number_of_nodes = adjacency_matrix[source].length - 1;
  17.         int visited[] = new int[number_of_nodes + 1];		
  18.         int element = source;		
  19.         int i = source;	
  20.         visited[source] = 1;		
  21.         stack.push(source);
  22.  
  23.         while (!stack.isEmpty())
  24.         {
  25.             element = stack.peek();
  26.             i = element;	
  27. 	    while (i <= number_of_nodes)
  28. 	    {
  29.      	        if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
  30. 	        {
  31.                     stack.push(i);
  32.                     visited[i] = 1;
  33.                     element = i;
  34.                     i = 1;
  35. 	            continue;
  36.                 }
  37.                 i++;
  38. 	    }
  39.             stack.pop();	
  40.         }
  41.         boolean connected = false;
  42.  
  43.         for (int vertex = 1; vertex <= number_of_nodes; vertex++)
  44.         {
  45.             if (visited[vertex] == 1) 
  46.             {
  47.                 connected = true;
  48.             }
  49.             else
  50.             {
  51.                 connected = false;
  52.                 break;
  53.             }
  54.         }
  55.  
  56.         if (connected)
  57.         {
  58.             System.out.println("The graph is connected");
  59.         }else
  60.         {
  61.             System.out.println("The graph is disconnected");
  62.         }
  63.     }
  64.  
  65.     public static void main(String...arg)
  66.     {
  67.         int number_of_nodes, source;
  68.         Scanner scanner = null;
  69.  	try
  70.         {
  71. 	    System.out.println("Enter the number of nodes in the graph");
  72.             scanner = new Scanner(System.in);
  73.             number_of_nodes = scanner.nextInt();
  74.  
  75. 	    int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];
  76. 	    System.out.println("Enter the adjacency matrix");
  77. 	    for (int i = 1; i <= number_of_nodes; i++)
  78. 	       for (int j = 1; j <= number_of_nodes; j++)
  79.                    adjacency_matrix[i][j] = scanner.nextInt();			
  80.  
  81. 	    System.out.println("Enter the source for the graph");
  82.             source = scanner.nextInt(); 
  83.  
  84.             DirectedConnectivityDfs directedConnectivity= new DirectedConnectivityDfs();
  85.             directedConnectivity.dfs(adjacency_matrix, source);	
  86.  
  87.         }catch(InputMismatchException inputMismatch)
  88.         {
  89.             System.out.println("Wrong Input format");
  90.         }	
  91.         scanner.close();	
  92.     }	
  93. }

$javac DirectedConnectivityDfs.java
$java DirectedConnectivityDfs
Enter the number of nodes in the graph
5
Enter the adjacency matrix
0 1 0 1 0
0 0 1 0 0
0 0 0 0 0
0 1 0 0 0
0 0 0 0 0
Enter the source for the graph
1
The graph is disconnected

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

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
I’m Manish - Founder and CTO at Sanfoundry. I’ve been working in tech for over 25 years, with deep focus on Linux kernel, SAN technologies, Advanced C, Full Stack and Scalable website designs.

You can connect with me on LinkedIn, watch my Youtube Masterclasses, or join my Telegram tech discussions.

If you’re in your 40s–60s and exploring new directions in your career, I also offer mentoring. Learn more here.