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:
Concrete Class in Java
Jackson vs Gson
Xây dựng ứng dụng Client-Server với Socket trong Java
Tìm hiểu về Web Service
Java Program to Solve the Fractional Knapsack Problem
Java Program to Perform Finite State Automaton based Search
Guide to Apache Commons CircularFifoQueue
ETags for REST with Spring
Java Program to find the peak element of an array using Binary Search approach
Java Program to Implement LinkedBlockingDeque API
Giới thiệu Aspect Oriented Programming (AOP)
Java Program to Solve Travelling Salesman Problem for Unweighted Graph
The Dining Philosophers Problem in Java
Guava – Join and Split Collections
Java Program to Check if it is a Sparse Matrix
Java Program to Construct an Expression Tree for an Postfix Expression
Hướng dẫn Java Design Pattern – Abstract Factory
Overview of Spring Boot Dev Tools
Debugging Reactive Streams in Java
Java Program to Find the GCD and LCM of two Numbers
Java Program to Perform Encoding of a Message Using Matrix Multiplication
Check if a String is a Palindrome in Java
Sử dụng CountDownLatch trong Java
Java Program to Implement Bucket Sort
Join and Split Arrays and Collections in Java
Java Program to Compute Discrete Fourier Transform Using the Fast Fourier Transform Approach
A Guide to the Java ExecutorService
Java Program to Implement SynchronosQueue API
Java Program to Implement RoleUnresolvedList API
Understanding Memory Leaks in Java
Tạo ứng dụng Java RESTful Client không sử dụng 3rd party libraries
LinkedList trong java