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.
import java.util.InputMismatchException; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class DirectedConnectivityBFS { private Queue<Integer> queue; public DirectedConnectivityBFS() { queue = new LinkedList<Integer>(); } public void bfs(int adjacency_matrix[][], int source) { int number_of_nodes = adjacency_matrix.length - 1; int[] visited = new int[number_of_nodes + 1]; int i, element; visited = 1; queue.add(source); while (!queue.isEmpty()) { element = queue.remove(); i = element; while (i <= number_of_nodes) { if (adjacency_matrix[element][i] == 1 && visited[i] == 0) { queue.add(i); visited[i] = 1; } i++; } } boolean connected = false; for (int vertex = 1; vertex <= number_of_nodes; vertex++) { if (visited[vertex] == 1) { connected = true; } else { connected = false; break; } } if (connected) { System.out.println("The graph is connected"); } else { System.out.println("The graph is disconnected"); } } public static void main(String... arg) { int number_no_nodes, source; Scanner scanner = null; try { System.out.println("Enter the number of nodes in the graph"); scanner = new Scanner(System.in); number_no_nodes = scanner.nextInt(); int adjacency_matrix[][] = new int[number_no_nodes + 1][number_no_nodes + 1]; System.out.println("Enter the adjacency matrix"); for (int i = 1; i <= number_no_nodes; i++) for (int j = 1; j <= number_no_nodes; j++) adjacency_matrix[i][j] = scanner.nextInt(); System.out.println("Enter the source for the graph"); source = scanner.nextInt(); DirectedConnectivityBFS directedConnectivity= new DirectedConnectivityBFS(); directedConnectivity.bfs(adjacency_matrix, source); } catch (InputMismatchException inputMismatch) { System.out.println("Wrong Input Format"); } scanner.close(); } }
$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
Related posts:
Using a Custom Spring MVC’s Handler Interceptor to Manage Sessions
Jackson Exceptions – Problems and Solutions
Java Program to Solve Set Cover Problem assuming at max 2 Elements in a Subset
Encode/Decode to/from Base64
Guide to the Synchronized Keyword in Java
Spring @RequestParam Annotation
Java Program to Implement Horner Algorithm
New Features in Java 15
Java Program to Compute DFT Coefficients Directly
Biến trong java
A Guide to System.exit()
The Thread.join() Method in Java
Java Program to Implement AttributeList API
Java String Conversions
Java Program to Find SSSP (Single Source Shortest Path) in DAG (Directed Acyclic Graphs)
Registration – Activate a New Account by Email
Java Program to Implement Vector API
Java Web Services – JAX-WS – SOAP
Inheritance and Composition (Is-a vs Has-a relationship) in Java
Java Program to Implement the Checksum Method for Small String Messages and Detect
JUnit5 @RunWith
Guide to java.util.concurrent.Future
Giới thiệu Java 8
Java Program to Represent Linear Equations in Matrix Form
Fixing 401s with CORS Preflights and Spring Security
How to Read a File in Java
Immutable ArrayList in Java
Từ khóa this và super trong Java
Converting Between a List and a Set in Java
Format ZonedDateTime to String
Java Program to implement Circular Buffer
Từ khóa static và final trong java