This is a Java Program to implement graph and check the connectivity between nodes using a standard Depth First Search algorithm. Algorithm visits the node that was traversed last or last come first serve basis. We create a visited array to avoid revisiting a node. If destination node appears in visited array, source and destination nodes are connected, not otherwise.
Here is the source code of the Java Program to Check the Connectivity of Graph Using DFS. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
//This is a java program to check the connectivity of a graph using DFS import java.util.Scanner; import java.util.Stack; public class Connectivity_DFS { private final int vertices; private int[][] adjacency_matrix; private Stack<Integer> stack; public Connectivity_DFS(int v) { vertices = v; adjacency_matrix = new int[vertices + 1][vertices + 1]; stack = new Stack<Integer>(); } public void makeEdge(int to, int from, int edge) { try { adjacency_matrix[to][from] = edge; adjacency_matrix[from][to] = edge; } catch (ArrayIndexOutOfBoundsException index) { System.out.println("The vertices does not exists"); } } public int getEdge(int to, int from) { try { return adjacency_matrix[to][from]; } catch (ArrayIndexOutOfBoundsException index) { System.out.println("The vertices does not exists"); } return -1; } public void dfs(int source) { int number_of_nodes = adjacency_matrix.length - 1; int[] visited = new int[number_of_nodes + 1]; int i, element; visited = 1; stack.push(source); while (!stack.isEmpty()) { element = stack.pop(); i = 1;// element; while (i <= number_of_nodes) { if (adjacency_matrix[element][i] == 1 && visited[i] == 0) { stack.push(i); visited[i] = 1; } i++; } } System.out.print("The source node " + source + " is connected to: "); int count = 0; for (int v = 1; v <= number_of_nodes; v++) if (visited[v] == 1) { System.out.print(v + " "); count++; } if (count == number_of_nodes) System.out.print("\nThe Graph is Connected "); else System.out.print("\nThe Graph is Disconnected "); } public static void main(String args[]) { int v, e, count = 1, to = 0, from = 0; Scanner sc = new Scanner(System.in); Connectivity_DFS graph; System.out.println("The Undirected Graph Connectivity Test"); try { System.out.println("Enter the number of vertices: "); v = sc.nextInt(); System.out.println("Enter the number of edges: "); e = sc.nextInt(); graph = new Connectivity_DFS(v); System.out.println("Enter the edges: <to> <from>"); while (count <= e) { to = sc.nextInt(); from = sc.nextInt(); graph.makeEdge(to, from, 1); count++; } System.out.println("The adjacency matrix for the given graph is: "); System.out.print(" "); for (int i = 1; i <= v; i++) System.out.print(i + " "); System.out.println(); for (int i = 1; i <= v; i++) { System.out.print(i + " "); for (int j = 1; j <= v; j++) System.out.print(graph.getEdge(i, j) + " "); System.out.println(); } System.out.println("Enter the Source Node: "); int sourceNode = sc.nextInt(); graph.dfs(sourceNode); } catch (Exception E) { System.out.println("Somthing went wrong"); } sc.close(); } }
Output:
$ javac Connectivity_DFS.java $ java Connectivity_DFS The Undirected Graph Connectivity Test(DFS) Enter the number of vertices: 4 Enter the number of edges: 2 Enter the edges: <to> <from> 1 2 1 3 The adjacency matrix for the given graph is: 1 2 3 4 1 0 1 1 0 2 1 0 0 0 3 1 0 0 0 4 0 0 0 0 Enter the Source Node: 2 The source node 2 is connected to: 1 2 3 The Graph is Disconnected The Undirected Graph Connectivity Test(DFS) Enter the number of vertices: 4 Enter the number of edges: 4 Enter the edges: <to> <from> 1 2 1 3 1 4 2 4 The adjacency matrix for the given graph is: 1 2 3 4 1 0 1 1 1 2 1 0 0 1 3 1 0 0 0 4 1 1 0 0 Enter the Source Node: 4 The source node 4 is connected to: 1 2 3 4 The Graph is Connected
Related posts:
Java Program to Implement LinkedHashMap API
Tính trừu tượng (Abstraction) trong Java
Java Program to Find Nearest Neighbor Using Linear Search
Spring Boot - Cloud Configuration Server
Upload and Display Excel Files with Spring MVC
Spring Data JPA and Null Parameters
JUnit5 Programmatic Extension Registration with @RegisterExtension
Java – Get Random Item/Element From a List
JWT – Token-based Authentication trong Jersey 2.x
Java Multi-line String
Guide to Guava Multimap
Java Program to Implement Sorting of Less than 100 Numbers in O(n) Complexity
Guide to java.util.Formatter
Hướng dẫn Java Design Pattern – Proxy
Autoboxing và Unboxing trong Java
Java Program to Use Dynamic Programming to Solve Approximate String Matching
Java Program to Check Whether Topological Sorting can be Performed in a Graph
Java Program to Implement the String Search Algorithm for Short Text Sizes
Spring Security OAuth2 – Simple Token Revocation
Using a List of Values in a JdbcTemplate IN Clause
Java Program to Implement Booth Algorithm
HttpClient 4 Cookbook
Java String Conversions
Marker Interface trong Java
Beans and Dependency Injection
Java Byte Array to InputStream
Adding a Newline Character to a String in Java
HttpClient Timeout
Java Program to Implement Ternary Search Algorithm
Java 8 – Powerful Comparison with Lambdas
Java Program to Solve TSP Using Minimum Spanning Trees
Java Program to Compute Determinant of a Matrix