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:
A Guide to Queries in Spring Data MongoDB
Guide to Selenium with JUnit / TestNG
Marker Interface trong Java
How to Remove the Last Character of a String?
@DynamicUpdate with Spring Data JPA
Java Program to Create a Balanced Binary Tree of the Incoming Data
Java Program to Generate Randomized Sequence of Given Range of Numbers
Assertions in JUnit 4 and JUnit 5
Java Program to Implement Control Table
Consuming RESTful Web Services
Spring Data JPA @Modifying Annotation
Write/Read cookies using HTTP and Read a file from the internet
Receive email by java client
Comparing Arrays in Java
Java Program to Check Whether an Undirected Graph Contains a Eulerian Cycle
Jackson Ignore Properties on Marshalling
Encode/Decode to/from Base64
Java Program to implement Associate Array
Entity To DTO Conversion for a Spring REST API
The Thread.join() Method in Java
Getting a File’s Mime Type in Java
Java Program to Implement Gift Wrapping Algorithm in Two Dimensions
Java Program to Implement the Vigenere Cypher
Spring Boot - Cloud Configuration Client
Java Program to Implement Attribute API
Java Program to Implement Karatsuba Multiplication Algorithm
Documenting a Spring REST API Using OpenAPI 3.0
Lớp lồng nhau trong java (Java inner class)
Java Program to Perform Postorder Non-Recursive Traversal of a Given Binary Tree
Summing Numbers with Java Streams
Java Program to Solve the 0-1 Knapsack Problem
Hướng dẫn Java Design Pattern – Proxy