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:
Spring Boot - Actuator
Getting the Size of an Iterable in Java
Integer Constant Pool trong Java
Java InputStream to String
Interface trong Java 8 – Default method và Static method
Tìm hiểu về Web Service
Spring 5 WebClient
Ways to Iterate Over a List in Java
Java Program to Implement Bit Array
Java Program to Implement LinkedTransferQueue API
How to Return 404 with Spring WebFlux
Jackson – JsonMappingException (No serializer found for class)
ClassNotFoundException vs NoClassDefFoundError
Creating a Web Application with Spring 5
Java Program to Find MST (Minimum Spanning Tree) using Prim’s Algorithm
Java 8 Stream API Analogies in Kotlin
Java Program to find the maximum subarray sum O(n^2) time(naive method)
Spring Boot - Interceptor
Thao tác với tập tin và thư mục trong Java
Lớp Properties trong java
Server-Sent Events in Spring
Control Structures in Java
Spring Boot - Creating Docker Image
Prevent Cross-Site Scripting (XSS) in a Spring Application
Java Program to Construct an Expression Tree for an Prefix Expression
How to Use if/else Logic in Java 8 Streams
OAuth2 for a Spring REST API – Handle the Refresh Token in AngularJS
Spring Boot: Customize Whitelabel Error Page
Constructor Injection in Spring with Lombok
Quick Guide on Loading Initial Data with Spring Boot
Write/Read cookies using HTTP and Read a file from the internet
Exploring the New Spring Cloud Gateway