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:
Compact Strings in Java 9
Immutable Map Implementations in Java
List Interface trong Java
Sorting Query Results with Spring Data
A Quick Guide to Using Keycloak with Spring Boot
Create Java Applet to Simulate Any Sorting Technique
Java Program to Check Whether a Given Point is in a Given Polygon
Retrieve User Information in Spring Security
How to Count Duplicate Elements in Arraylist
Java Program to Implement Park-Miller Random Number Generation Algorithm
Configuring a DataSource Programmatically in Spring Boot
How to Read a Large File Efficiently with Java
Java Program to Print the Kind of Rotation the AVL Tree is Undergoing
Set Interface trong Java
Function trong Java 8
Java Program to Implement Hash Tables chaining with Singly Linked Lists
Apache Commons Collections SetUtils
Notify User of Login From New Device or Location
Serve Static Resources with Spring
Java Program to Implement the Bin Packing Algorithm
Java Program to Perform Insertion in a 2 Dimension K-D Tree
Write/Read cookies using HTTP and Read a file from the internet
Converting Iterator to List
SOAP Web service: Upload và Download file sử dụng MTOM trong JAX-WS
New Features in Java 15
Spring Boot Integration Testing with Embedded MongoDB
Java Program to Implement Caesar Cypher
A Guide to JUnit 5
Java Program to Find kth Smallest Element by the Method of Partitioning the Array
A Guide to BitSet in Java
Upload and Display Excel Files with Spring MVC
Java Program to Find MST (Minimum Spanning Tree) using Kruskal’s Algorithm