This Java program, to perform the bfs traversal of a given undirected 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 undirected 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 UndirectedConnectivityBFS { private Queue<Integer> queue; public UndirectedConnectivityBFS() { 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(); for (int i = 1; i <= number_of_nodes; i++) { for (int j = 1; j <= number_of_nodes; j++) { if (adjacency_matrix[i][j] == 1 && adjacency_matrix[j][i] == 0) { adjacency_matrix[j][i] = 1; } } } System.out.println("Enter the source for the graph"); source = scanner.nextInt(); UndirectedConnectivityBFS undirectedConnectivity= new UndirectedConnectivityBFS(); undirectedConnectivity.bfs(adjacency_matrix, source); } catch (InputMismatchException inputMismatch) { System.out.println("Wrong Input Format"); } scanner.close(); } }
$javac UndirectedConnectivityBFS.java $java UndirectedConnectivityBFS 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 Gale Shapley Algorithm
Java Program to Implement CopyOnWriteArraySet API
HashSet trong java
Tạo ứng dụng Java RESTful Client không sử dụng 3rd party libraries
Java Program to Implement the Bin Packing Algorithm
Get the workstation name or IP
Hướng dẫn sử dụng luồng vào ra nhị phân trong Java
Java NIO2 Path API
Spring Boot - Sending Email
How to Round a Number to N Decimal Places in Java
Join and Split Arrays and Collections in Java
OAuth 2.0 Resource Server With Spring Security 5
Java Program to Construct an Expression Tree for an Postfix Expression
Java Program to Implement Queue using Linked List
Convert XML to JSON Using Jackson
Java Program to Implement HashSet API
Java Program to Implement Branch and Bound Method to Perform a Combinatorial Search
Sử dụng Fork/Join Framework với ForkJoinPool trong Java
Java Program to Implement Threaded Binary Tree
Java Program to Implement vector
Object Type Casting in Java
Spring’s RequestBody and ResponseBody Annotations
Java Program to Implement Flood Fill Algorithm
Spring Security Login Page with React
Java Program to Implement Min Heap
Jackson – Marshall String to JsonNode
Java Program to Create a Balanced Binary Tree of the Incoming Data
A Guide to TreeMap in Java
Deploy a Spring Boot App to Azure
String Processing with Apache Commons Lang 3
Java Program to Generate a Graph for a Given Fixed Degree Sequence
Java Program to Represent Linear Equations in Matrix Form