Java Program to Check the Connectivity of Undirected Graph using DFS

«
»
This Java program,performs the DFS traversal on the given undirected 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 undirected 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 UndirectedConnectivityDfs
  6. {
  7.     private Stack<Integer> stack;
  8.  
  9.     public UndirectedConnectivityDfs() 
  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.             } else
  49.             {
  50.                 connected = false;
  51.                 break;
  52.             }
  53.         }
  54.  
  55.         if (connected)
  56.         {
  57.             System.out.println("The graph is connected");
  58. 	}else
  59.         {
  60.             System.out.println("The graph is disconnected");
  61.         }
  62.     }
  63.  
  64.     public static void main(String...arg)
  65.     {
  66.         int number_of_nodes, source;
  67.         Scanner scanner = null;
  68.  	try
  69.         {
  70. 	    System.out.println("Enter the number of nodes in the graph");
  71.             scanner = new Scanner(System.in);
  72.             number_of_nodes = scanner.nextInt();
  73.  
  74. 	    int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];
  75. 	    System.out.println("Enter the adjacency matrix");
  76. 	    for (int i = 1; i <= number_of_nodes; i++)
  77. 	       for (int j = 1; j <= number_of_nodes; j++)
  78.                    adjacency_matrix[i][j] = scanner.nextInt();
  79.  
  80.    	    for (int i = 1; i <= number_of_nodes; i++)
  81.             {
  82.                 for (int j = 1; j <= number_of_nodes; j++)
  83.                 {	
  84.                      if (adjacency_matrix[i][j] == 1 && adjacency_matrix[j][i] == 0)
  85.                      {
  86.                          adjacency_matrix[j][i] = 1;
  87.                      }
  88.                 }
  89.             }			
  90.  
  91. 	    System.out.println("Enter the source for the graph");
  92.             source = scanner.nextInt(); 
  93.  
  94.             UndirectedConnectivityDfs undirectedConnectivity= new UndirectedConnectivityDfs();
  95.             undirectedConnectivity.dfs(adjacency_matrix, source);	
  96.  
  97.         }catch(InputMismatchException inputMismatch)
  98.         {
  99.             System.out.println("Wrong Input format");
  100.         }	
  101.         scanner.close();	
  102.     }	
  103. }

$javac UndirectedConnectivityDfs.java
$java UndirectedConnectivityDfs
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
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
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.