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:
JUnit 5 @Test Annotation
Java – Convert File to InputStream
Checked and Unchecked Exceptions in Java
A Guide to the ResourceBundle
Introduction to Eclipse Collections
Jackson Ignore Properties on Marshalling
Spring’s RequestBody and ResponseBody Annotations
Object cloning trong java
Spring WebClient Requests with Parameters
Introduction to Netflix Archaius with Spring Cloud
Chương trình Java đầu tiên
Guide to @ConfigurationProperties in Spring Boot
Mệnh đề Switch-case trong java
Show Hibernate/JPA SQL Statements from Spring Boot
Java Program to Find Number of Articulation points in a Graph
Giới thiệu SOAP UI và thực hiện test Web Service
Spring Boot - Eureka Server
Java Program to Implement Borwein Algorithm
Guide to Escaping Characters in Java RegExps
Static Content in Spring WebFlux
Creating a Generic Array in Java
Hướng dẫn kết nối cơ sở dữ liệu với Java JDBC
Hướng dẫn Java Design Pattern – Observer
Logging in Spring Boot
OAuth2 Remember Me with Refresh Token
Java – Try with Resources
Template Engines for Spring
Guide to ThreadLocalRandom in Java
Java Program to Implement Hash Tables Chaining with List Heads
Spring @Primary Annotation
Java NIO2 Path API
Life Cycle of a Thread in Java