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:
Java Program to Implement Trie
A Guide to Spring Cloud Netflix – Hystrix
Java Program to Check whether Graph is a Bipartite using 2 Color Algorithm
Hướng dẫn sử dụng Lớp FilePermission trong java
Jackson – Decide What Fields Get Serialized/Deserialized
Java InputStream to String
Calling Stored Procedures from Spring Data JPA Repositories
Java Program to Describe the Representation of Graph using Adjacency Matrix
Spring Data JPA and Null Parameters
Java Program to implement Bit Matrix
Spring Boot Gradle Plugin
A Guide to the ResourceBundle
How to Convert List to Map in Java
Tính đa hình (Polymorphism) trong Java
Converting a Stack Trace to a String in Java
Java Program to find the number of occurrences of a given number using Binary Search approach
Hướng dẫn Java Design Pattern – Builder
Guide to Spring Cloud Kubernetes
Java Program to Implement RoleList API
List Interface trong Java
Java Program to Implement Park-Miller Random Number Generation Algorithm
Versioning a REST API
Handling URL Encoded Form Data in Spring REST
Java Program to Implement the Hungarian Algorithm for Bipartite Matching
New Features in Java 9
Use Liquibase to Safely Evolve Your Database Schema
Java Program to Implement the Program Used in grep/egrep/fgrep
JUnit5 @RunWith
Giới thiệu Google Guice – Injection, Scope
Java Program to Implement Depth-limited Search
Disable Spring Data Auto Configuration
Configure a Spring Boot Web Application