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:
Introduction to Spring MVC HandlerInterceptor
Java Program to Implement K Way Merge Algorithm
Java Scanner hasNext() vs. hasNextLine()
Date Time trong Java 8
Guide to the Java Queue Interface
Convert Time to Milliseconds in Java
Control Structures in Java
Java Program to Check Whether a Directed Graph Contains a Eulerian Path
Guide to Spring 5 WebFlux
Mapping Nested Values with Jackson
Jackson vs Gson
Spring MVC Async vs Spring WebFlux
Guide to java.util.concurrent.Future
Java Program to Implement Sparse Matrix
HttpClient 4 – Follow Redirects for POST
Converting a Stack Trace to a String in Java
So sánh ArrayList và LinkedList trong Java
Introduction to Spring Data MongoDB
Java Program to Generate N Number of Passwords of Length M Each
Spring Security Basic Authentication
Java Program to Represent Graph Using 2D Arrays
Hướng dẫn sử dụng biểu thức chính quy (Regular Expression) trong Java
Java Program to implement Circular Buffer
Hướng dẫn Java Design Pattern – Singleton
Java Program to Solve a Matching Problem for a Given Specific Case
Call Methods at Runtime Using Java Reflection
Validations for Enum Types
@Lookup Annotation in Spring
Zipping Collections in Java
Spring Cloud AWS – RDS
Java Program to Perform Postorder Non-Recursive Traversal of a Given Binary Tree
Java Program to Find Transpose of a Graph Matrix