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:
Hướng dẫn sử dụng Java Reflection
Java List UnsupportedOperationException
Java Program to Find Location of a Point Placed in Three Dimensions Using K-D Trees
Wrapper Classes in Java
Binary Numbers in Java
Tạo ứng dụng Java RESTful Client không sử dụng 3rd party libraries
Spring Cloud – Adding Angular
How to Find an Element in a List with Java
JUnit5 @RunWith
Java Timer
StringBuilder vs StringBuffer in Java
Java Program to Check Whether a Weak Link i.e. Articulation Vertex Exists in a Graph
Getting the Size of an Iterable in Java
Java Program to Implement Naor-Reingold Pseudo Random Function
Comparing Arrays in Java
Java Program to Implement Bucket Sort
Java 8 Stream findFirst() vs. findAny()
Java Program to Implement Gaussian Elimination Algorithm
The StackOverflowError in Java
An Intro to Spring Cloud Task
Error Handling for REST with Spring
Tránh lỗi NullPointerException trong Java như thế nào?
Hướng dẫn sử dụng Lớp FilePermission trong java
Overflow and Underflow in Java
SOAP Web service: Upload và Download file sử dụng MTOM trong JAX-WS
Spring Boot: Customize Whitelabel Error Page
Java Program to Implement Max Heap
The Thread.join() Method in Java
Java Map With Case-Insensitive Keys
Java Program to Generate Random Numbers Using Multiply with Carry Method
Copy a List to Another List in Java
OAuth2 for a Spring REST API – Handle the Refresh Token in AngularJS