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 Bloom Filter
Get and Post Lists of Objects with RestTemplate
Java Program to Implement Warshall Algorithm
Spring MVC and the @ModelAttribute Annotation
Các chương trình minh họa sử dụng Cấu trúc điều khiển trong Java
Java Program to Implement EnumMap API
Removing all duplicates from a List in Java
Converting between an Array and a List in Java
Java Program to Find MST (Minimum Spanning Tree) using Prim’s Algorithm
Using Spring ResponseEntity to Manipulate the HTTP Response
Java Program to Implement Max-Flow Min-Cut Theorem
A Guide to JUnit 5 Extensions
Java Program to Find Maximum Element in an Array using Binary Search
Lập trình đa luồng trong Java (Java Multi-threading)
Java Program to Perform Insertion in a BST
Java Program to Generate N Number of Passwords of Length M Each
Java Program to Implement LinkedBlockingQueue API
Java Program to Implement ArrayList API
Hướng dẫn Java Design Pattern – Factory Method
Java Program to Find the Median of two Sorted Arrays using Binary Search Approach
Constructor Dependency Injection in Spring
Java Program to Repeatedly Search the Same Text (such as Bible by building a Data Structure)
How to Use if/else Logic in Java 8 Streams
An Intro to Spring Cloud Task
Tạo chương trình Java đầu tiên sử dụng Eclipse
Java Program to Generate a Sequence of N Characters for a Given Specific Case
Logout in an OAuth Secured Application
Chuyển đổi giữa các kiểu dữ liệu trong Java
Java Program to Find All Pairs Shortest Path
Java Program to Check if any Graph is Possible to be Constructed for a Given Degree Sequence
Java Program to Find Inverse of a Matrix
Spring Cloud Bus