Java Program to Check the Connectivity of Directed Graph using BFS

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


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

If you find any mistake above, kindly email to [email protected]

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.