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:
Hướng dẫn sử dụng luồng vào ra nhị phân trong Java
Java Program to find the peak element of an array using Binary Search approach
Guide to ThreadLocalRandom in Java
HttpClient 4 – Follow Redirects for POST
Introduction to Using FreeMarker in Spring MVC
Show Hibernate/JPA SQL Statements from Spring Boot
Giới thiệu thư viện Apache Commons Chain
Partition a List in Java
Java Program to Implement ScapeGoat Tree
Các kiểu dữ liệu trong java
Java Program to Perform Quick Sort on Large Number of Elements
Zipping Collections in Java
Java Program to Implement First Fit Decreasing for 1-D Objects and M Bins
Guide to the Java Clock Class
Java Program to find the maximum subarray sum using Binary Search approach
Java Program to Implement CountMinSketch
Lập trình hướng đối tượng (OOPs) trong java
Java Program to Implement Bloom Filter
String Joiner trong Java 8
Spring Boot - Creating Docker Image
Java Program to Solve a Matching Problem for a Given Specific Case
Hướng dẫn tạo và sử dụng ThreadPool trong Java
Java Program to Implement Stack using Linked List
Convert Time to Milliseconds in Java
Java Program to implement Bit Matrix
HashMap trong Java hoạt động như thế nào?
Map Interface trong java
Spring Security 5 for Reactive Applications
Sử dụng CountDownLatch trong Java
Introduction to Using Thymeleaf in Spring
Java Program to Generate All Possible Subsets with Exactly k Elements in Each Subset
Check If Two Lists are Equal in Java