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:
The Order of Tests in JUnit
Java Program to Solve Tower of Hanoi Problem using Stacks
Java Program to Perform Postorder Recursive Traversal of a Given Binary Tree
Java Program to Solve Knapsack Problem Using Dynamic Programming
Quick Guide to java.lang.System
Introduction to Java Serialization
Jackson – Marshall String to JsonNode
Java Program to Implement VList
Depth First Search (DFS)
Java Program to Compute the Volume of a Tetrahedron Using Determinants
Command-Line Arguments in Java
Java Program to Find Minimum Element in an Array using Linear Search
Java Program to Implement Cubic convergence 1/pi Algorithm
Guide to BufferedReader
Java Program to Solve any Linear Equation in One Variable
Query Entities by Dates and Times with Spring Data JPA
Format ZonedDateTime to String
Spring Cloud – Tracing Services with Zipkin
Java Program to Implement HashTable API
Mockito and JUnit 5 – Using ExtendWith
Java Program to Implement Stein GCD Algorithm
Creating a Generic Array in Java
Custom Exception trong Java
Java InputStream to String
Spring 5 WebClient
Functional Interfaces in Java 8
A Custom Media Type for a Spring REST API
Spring Boot - Tomcat Deployment
Examine the internal DNS cache
Tips for dealing with HTTP-related problems
Apache Commons Collections SetUtils
Java Program to Check if a Given Set of Three Points Lie on a Single Line or Not