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:
Java Program to Solve TSP Using Minimum Spanning Trees
Spring Boot - Database Handling
Fixing 401s with CORS Preflights and Spring Security
Hướng dẫn Java Design Pattern – Bridge
Java Program to find the maximum subarray sum O(n^2) time(naive method)
Hướng dẫn Java Design Pattern – Visitor
Reading an HTTP Response Body as a String in Java
Java Program to Solve the 0-1 Knapsack Problem
Java Program to Find Minimum Element in an Array using Linear Search
HashSet trong java
The Spring @Controller and @RestController Annotations
Login For a Spring Web App – Error Handling and Localization
A Guide to Spring Boot Admin
LinkedHashSet trong java
Object Type Casting in Java
Spring AMQP in Reactive Applications
Hướng dẫn sử dụng String Format trong Java
Creating Docker Images with Spring Boot
An Intro to Spring Cloud Contract
Setting the Java Version in Maven
A Guide to Concurrent Queues in Java
Static Content in Spring WebFlux
Java – Combine Multiple Collections
Java Program to Find Number of Spanning Trees in a Complete Bipartite Graph
Java Program to Implement Sieve Of Atkin
Xử lý ngoại lệ trong Java (Exception Handling)
A Guide to the Java LinkedList
Tính đóng gói (Encapsulation) trong java
Java Program to Implement the Bin Packing Algorithm
Java Program to Implement Pollard Rho Algorithm
New Features in Java 14
Java Program to Implement PriorityQueue API