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 Bit Array
Java Program to Implement Queue
Spring Cloud – Adding Angular
Java Program to Implement Coppersmith Freivald’s Algorithm
Java Program to Implement EnumMap API
Prevent Cross-Site Scripting (XSS) in a Spring Application
Hướng dẫn sử dụng Java String, StringBuffer và StringBuilder
Java Program to Implement Dijkstra’s Algorithm using Priority Queue
Java Program to Implement Heap’s Algorithm for Permutation of N Numbers
Spring MVC Setup with Kotlin
Java Program to implement Priority Queue
Java Program to Find Maximum Element in an Array using Binary Search
Jackson JSON Views
Remove the First Element from a List
Send email with JavaMail
Java Program to Implement Max Heap
Database Migrations with Flyway
Spring Security Custom AuthenticationFailureHandler
Java Program to Implement JobStateReasons API
Generating Random Dates in Java
Java Program to Implement VList
Converting String to Stream of chars
Spring MVC Tutorial
Introduction to Spring Cloud Rest Client with Netflix Ribbon
Adding Parameters to HttpClient Requests
Java Program to Find the Longest Path in a DAG
Java Program to Implement Iterative Deepening
Exception Handling in Java
Java Program to Find Strongly Connected Components in Graphs
Guide to Java 8’s Collectors
Spring Autowiring of Generic Types
Spring @Primary Annotation