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 Permute All Letters of an Input String
Sorting Query Results with Spring Data
Java Program to Implement K Way Merge Algorithm
Java Web Services – JAX-WS – SOAP
Setting a Request Timeout for a Spring REST API
The Order of Tests in JUnit
Java Program to Find Shortest Path Between All Vertices Using Floyd-Warshall’s Algorithm
Guide to Dynamic Tests in Junit 5
DistinctBy in the Java Stream API
Java Program to Implement SynchronosQueue API
Java Program to Implement Network Flow Problem
Tạo ứng dụng Java RESTful Client với thư viện Retrofit
Spring Cloud Series – The Gateway Pattern
Java Program to add two large numbers using Linked List
Java Program to Implement Self organizing List
Java Program to Generate All Possible Combinations Out of a, b, c, d, e
Java String Conversions
Java Program to Implement Randomized Binary Search Tree
Getting Started with GraphQL and Spring Boot
Spring Security 5 – OAuth2 Login
Custom HTTP Header with the HttpClient
Java Program to Implement RoleList API
Inheritance with Jackson
So sánh HashMap và HashSet trong Java
Java Program to Perform Right Rotation on a Binary Search Tree
Guide to the Java ArrayList
Java Program to Implement Hamiltonian Cycle Algorithm
Java Program to Implement Nth Root Algorithm
Comparing Strings in Java
Guide to Mustache with Spring Boot
Java Program to implement Sparse Vector
Spring RestTemplate Error Handling