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:
Intersection of Two Lists in Java
Java Program to Find Minimum Number of Edges to Cut to make the Graph Disconnected
Java Program to Perform Stooge Sort
Receive email by java client
Java 8 and Infinite Streams
Java Program to Implement Min Heap
Spring Cloud Bus
Send email with JavaMail
How to Replace Many if Statements in Java
Spring Security Custom AuthenticationFailureHandler
Hướng dẫn Java Design Pattern – Visitor
Spring Security Registration – Resend Verification Email
Java Program to Compute Determinant of a Matrix
Java Program to Implement Sorted List
Spring MVC Custom Validation
Guide to java.util.concurrent.BlockingQueue
Java Program to Implement Skew Heap
Working with Tree Model Nodes in Jackson
Các kiểu dữ liệu trong java
Guide to the Fork/Join Framework in Java
Java Program to Implement Weight Balanced Tree
Registration with Spring Security – Password Encoding
Get and Post Lists of Objects with RestTemplate
Most commonly used String methods in Java
Introduction to Project Reactor Bus
JUnit5 @RunWith
Spring Boot - Rest Template
Java Program to Implement Counting Sort
Loại bỏ các phần tử trùng trong một ArrayList như thế nào trong Java 8?
Tính đóng gói (Encapsulation) trong java
Comparing getPath(), getAbsolutePath(), and getCanonicalPath() in Java
Java Program for Topological Sorting in Graphs