This Java program,performs the DFS traversal on the given undirected 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 undirected 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 UndirectedConnectivityDfs { private Stack<Integer> stack; public UndirectedConnectivityDfs() { 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(); for (int i = 1; i <= number_of_nodes; i++) { for (int j = 1; j <= number_of_nodes; j++) { if (adjacency_matrix[i][j] == 1 && adjacency_matrix[j][i] == 0) { adjacency_matrix[j][i] = 1; } } } System.out.println("Enter the source for the graph"); source = scanner.nextInt(); UndirectedConnectivityDfs undirectedConnectivity= new UndirectedConnectivityDfs(); undirectedConnectivity.dfs(adjacency_matrix, source); }catch(InputMismatchException inputMismatch) { System.out.println("Wrong Input format"); } scanner.close(); } }
$javac UndirectedConnectivityDfs.java $java UndirectedConnectivityDfs 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 Solve the Fractional Knapsack Problem
Consuming RESTful Web Services
Java Program to Describe the Representation of Graph using Incidence Matrix
A Guide to Apache Commons Collections CollectionUtils
Exploring the New Spring Cloud Gateway
Convert char to String in Java
Java Program for Douglas-Peucker Algorithm Implementation
Spring Boot - Rest Controller Unit Test
Spring Security Custom AuthenticationFailureHandler
Mapping Nested Values with Jackson
Spring Boot Actuator
Java Program to Implement Queue using Two Stacks
A Guide to Java 9 Modularity
Chương trình Java đầu tiên
The StackOverflowError in Java
Java Program to Implement Shunting Yard Algorithm
Mockito and JUnit 5 – Using ExtendWith
Java Program to Implement PrinterStateReasons API
JUnit 5 for Kotlin Developers
Guide to CopyOnWriteArrayList
Convert Hex to ASCII in Java
Check if a String is a Palindrome in Java
Java Program to Find the Longest Subsequence Common to All Sequences in a Set of Sequences
Java Program to Solve any Linear Equations
The Difference Between Collection.stream().forEach() and Collection.forEach()
Set Interface trong Java
Spring Boot - Rest Template
Java Program to Implement Regular Falsi Algorithm
Java Program to Implement ConcurrentLinkedQueue API
Spring Boot - Google Cloud Platform
Java Program to Print only Odd Numbered Levels of a Tree
Object Type Casting in Java