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 Implement Find all Back Edges in a Graph
Java Program to Perform Sorting Using B-Tree
Inheritance and Composition (Is-a vs Has-a relationship) in Java
Hướng dẫn Java Design Pattern – Flyweight
Java Program to Implement AA Tree
A Quick Guide to Using Keycloak with Spring Boot
Một số từ khóa trong Java
Check If a File or Directory Exists in Java
Hướng dẫn Java Design Pattern – Template Method
The Registration API becomes RESTful
Java Program to Implement Sorting of Less than 100 Numbers in O(n) Complexity
Custom JUnit 4 Test Runners
Java Program to Use the Bellman-Ford Algorithm to Find the Shortest Path
Creating a Generic Array in Java
Java Program to Generate Random Partition out of a Given Set of Numbers or Characters
Java Program to Implement Hash Tables chaining with Singly Linked Lists
Jackson – Change Name of Field
Binary Numbers in Java
Creating Docker Images with Spring Boot
Java Program to Check Cycle in a Graph using Graph traversal
Spring Security Logout
Lớp Properties trong java
Java Program to Implement Floyd-Warshall Algorithm
Hướng dẫn Java Design Pattern – Dependency Injection
Java – Write to File
Marker Interface trong Java
Java Program to Implement Binary Tree
Spring AMQP in Reactive Applications
Java Program to Check whether Undirected Graph is Connected using DFS
Spring Security Login Page with React
Một số ký tự đặc biệt trong Java
Java Program to Implement Circular Singly Linked List