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:
Get and Post Lists of Objects with RestTemplate
Java Program to implement Bit Matrix
OAuth2 Remember Me with Refresh Token
Xây dựng ứng dụng Client-Server với Socket trong Java
Hướng dẫn Java Design Pattern – Proxy
Java Program to Implement PrinterStateReasons API
Java Program to Implement Attribute API
Tính đa hình (Polymorphism) trong Java
HashSet trong java
Java Program to Implement Meldable Heap
Convert XML to JSON Using Jackson
Java Program to Describe the Representation of Graph using Incidence List
Removing all duplicates from a List in Java
Map Serialization and Deserialization with Jackson
Hướng dẫn sử dụng String Format trong Java
Collection trong java
How to Get All Dates Between Two Dates?
Spring Boot - Apache Kafka
Send an email using the SMTP protocol
Using the Not Operator in If Conditions in Java
ExecutorService – Waiting for Threads to Finish
Java Program to Implement Heap Sort Using Library Functions
Java Program to Implement Binary Search Tree
Guide to Java 8 groupingBy Collector
LIKE Queries in Spring JPA Repositories
Java Program to Implement the Hill Cypher
Java Program to Implement Dijkstra’s Algorithm using Priority Queue
Java Program to Check Cycle in a Graph using Topological Sort
Spring Security Form Login
Apache Commons Collections BidiMap
Debugging Reactive Streams in Java
Java Program to Implement Bloom Filter