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:
Jackson – Unmarshall to Collection/Array
Intro to Spring Boot Starters
Spring Boot Actuator
Java Program to Find the Number of Ways to Write a Number as the Sum of Numbers Smaller than Itself
Reactive WebSockets with Spring 5
Debug a JavaMail Program
Implementing a Binary Tree in Java
Sao chép các phần tử của một mảng sang mảng khác như thế nào?
Java Program to Generate All Subsets of a Given Set in the Lexico Graphic Order
Marker Interface trong Java
Jackson – JsonMappingException (No serializer found for class)
Tạo chương trình Java đầu tiên sử dụng Eclipse
Java Program to Implement an Algorithm to Find the Global min Cut in a Graph
Circular Dependencies in Spring
Inject Parameters into JUnit Jupiter Unit Tests
Spring Boot - Creating Docker Image
Custom HTTP Header with the HttpClient
Java Program to Implement RenderingHints API
HttpClient 4 – Follow Redirects for POST
Daemon Threads in Java
Java Program to Encode a Message Using Playfair Cipher
Getting Started with Forms in Spring MVC
Java Program to Check if a Given Set of Three Points Lie on a Single Line or Not
Period and Duration in Java
How to Read HTTP Headers in Spring REST Controllers
A Guide to Iterator in Java
New Stream Collectors in Java 9
Java Program to Find the Median of two Sorted Arrays using Binary Search Approach
Java Program to Implement VList
Chuyển đổi Array sang ArrayList và ngược lại
Spring Boot - OAuth2 with JWT
Java Program to Solve Knapsack Problem Using Dynamic Programming