Java Program to Check the Connectivity of Undirected Graph using BFS

This Java program, to perform the bfs traversal of a given undirected graph in the form of the adjacency matrix and check for the connectivity of the graph.the bfs traversal makes use of a queue.

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


$javac UndirectedConnectivityBFS.java
$java UndirectedConnectivityBFS
Enter the number of nodes in the graph
5
Enter the adjacency matrix
0 1 1 1 0
0 0 1 0 0
0 0 0 0 0
0 0 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 & discussions at Telegram SanfoundryClasses.