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 Sorted Array
Spring Web Annotations
Quick Intro to Spring Cloud Configuration
Spring Boot - Service Components
Java Program to Implement the One Time Pad Algorithm
Jackson Unmarshalling JSON with Unknown Properties
Convert String to Byte Array and Reverse in Java
Java Program to Find the Nearest Neighbor Using K-D Tree Search
Convert Hex to ASCII in Java
How To Serialize and Deserialize Enums with Jackson
Spring Boot: Customize Whitelabel Error Page
Java Program to Create a Random Graph Using Random Edge Generation
Spring Boot With H2 Database
Comparing Dates in Java
@Order in Spring
Java Program to Perform Searching Based on Locality of Reference
Lấy ngày giờ hiện tại trong Java
A Guide to TreeSet in Java
Collect a Java Stream to an Immutable Collection
Java Program to Find Second Smallest of n Elements with Given Complexity Constraint
Java Program to Generate Random Hexadecimal Byte
Java Program to Implement CopyOnWriteArrayList API
Semaphore trong Java
Java Program to Implement Radix Sort
Java Program to Implement Iterative Deepening
Biểu thức Lambda trong Java 8 – Lambda Expressions
Từ khóa throw và throws trong Java
Java Program to Implement Gift Wrapping Algorithm in Two Dimensions
Spring REST API + OAuth2 + Angular
Spring Boot with Multiple SQL Import Files
Java Program to Represent Graph Using Linked List
Java Program to Implement TreeMap API