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:
Câu lệnh điều khiển vòng lặp trong Java (break, continue)
Giới thiệu Google Guice – Dependency injection (DI) framework
Jackson JSON Views
Java Program to Perform String Matching Using String Library
Depth First Search (DFS)
Chuyển đổi từ HashMap sang ArrayList
Spring REST API + OAuth2 + Angular (using the Spring Security OAuth legacy stack)
Guide to the Java ArrayList
Java Program to implement Bit Matrix
Spring @Primary Annotation
Create a Custom Exception in Java
Guava CharMatcher
ClassNotFoundException vs NoClassDefFoundError
Filtering a Stream of Optionals in Java
Java Program to Represent Graph Using Incidence List
Java Program to Implement an Algorithm to Find the Global min Cut in a Graph
Giới thiệu SOAP UI và thực hiện test Web Service
Java Program to Implement Suffix Array
HashSet trong Java hoạt động như thế nào?
Spring REST API + OAuth2 + Angular
Java Program to Implement Gabow Algorithm
Instance Profile Credentials using Spring Cloud
How to Round a Number to N Decimal Places in Java
Guide to the Volatile Keyword in Java
Using Spring @ResponseStatus to Set HTTP Status Code
Java Program to Implement Sparse Matrix
Jackson Date
Spring Boot - Google OAuth2 Sign-In
Java Program to implement Sparse Vector
Java Program to Implement Maximum Length Chain of Pairs
Request Method Not Supported (405) in Spring
A Guide to Java 9 Modularity