This Java program,performs the DFS traversal on the given directed graph represented by a adjacency matrix to check connectivity.the DFS traversal makes use of an stack.
Here is the source code of the Java program to check the connectivity of a directed graph. 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.Scanner; import java.util.Stack; public class DirectedConnectivityDfs { private Stack<Integer> stack; public DirectedConnectivityDfs() { stack = new Stack<Integer>(); } public void dfs(int adjacency_matrix[][], int source) { int number_of_nodes = adjacency_matrix.length - 1; int visited[] = new int[number_of_nodes + 1]; int element = source; int i = source; visited = 1; stack.push(source); while (!stack.isEmpty()) { element = stack.peek(); i = element; while (i <= number_of_nodes) { if (adjacency_matrix[element][i] == 1 && visited[i] == 0) { stack.push(i); visited[i] = 1; element = i; i = 1; continue; } i++; } stack.pop(); } 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_of_nodes, source; Scanner scanner = null; try { System.out.println("Enter the number of nodes in the graph"); scanner = new Scanner(System.in); number_of_nodes = scanner.nextInt(); int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1]; System.out.println("Enter the adjacency matrix"); for (int i = 1; i <= number_of_nodes; i++) for (int j = 1; j <= number_of_nodes; j++) adjacency_matrix[i][j] = scanner.nextInt(); System.out.println("Enter the source for the graph"); source = scanner.nextInt(); DirectedConnectivityDfs directedConnectivity= new DirectedConnectivityDfs(); directedConnectivity.dfs(adjacency_matrix, source); }catch(InputMismatchException inputMismatch) { System.out.println("Wrong Input format"); } scanner.close(); } }
$javac DirectedConnectivityDfs.java $java DirectedConnectivityDfs Enter the number of nodes in the graph 5 Enter the adjacency matrix 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 Enter the source for the graph 1 The graph is disconnected
Related posts:
A Guide to JUnit 5
LinkedList trong java
Java Program to Apply DFS to Perform the Topological Sorting of a Directed Acyclic Graph
Java Program to Find the GCD and LCM of two Numbers
Tìm hiểu về xác thực và phân quyền trong ứng dụng
An Intro to Spring Cloud Zookeeper
Guide to BufferedReader
Sort a HashMap in Java
Guide to the Java ArrayList
Spring Boot - OAuth2 with JWT
Spring Boot - Code Structure
Java Program to Check Multiplicability of Two Matrices
Spring Boot: Customize Whitelabel Error Page
Generate Spring Boot REST Client with Swagger
Using Spring @ResponseStatus to Set HTTP Status Code
String Processing with Apache Commons Lang 3
Spring MVC Content Negotiation
Cài đặt và sử dụng Swagger UI
Java Program to Implement Hopcroft Algorithm
How to Read a File in Java
Java Program to Implement Ford–Fulkerson Algorithm
Java Program to Find Minimum Element in an Array using Linear Search
Map to String Conversion in Java
Java 9 Stream API Improvements
Apache Tiles Integration with Spring MVC
Java Program to Implement the Hungarian Algorithm for Bipartite Matching
Difference Between Wait and Sleep in Java
Setting Up Swagger 2 with a Spring REST API
The DAO with JPA and Spring
Spring WebClient and OAuth2 Support
Consumer trong Java 8
Deploy a Spring Boot App to Azure