This Java program,performs the DFS traversal on the given graph represented by a adjacency matrix to check for cycles in the graph.the DFS traversal makes use of an stack.
Here is the source code of the Java program to check for cycle in 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 CheckCycle { private Stack<Integer> stack; private int adjacencyMatrix[][]; public CheckCycle() { stack = new Stack<Integer>(); } public void dfs(int adjacency_matrix[][], int source) { int number_of_nodes = adjacency_matrix.length - 1; adjacencyMatrix = new int[number_of_nodes + 1][number_of_nodes + 1]; for (int sourcevertex = 1; sourcevertex <= number_of_nodes; sourcevertex++) { for (int destinationvertex = 1; destinationvertex <= number_of_nodes; destinationvertex++) { adjacencyMatrix[sourcevertex][destinationvertex] = adjacency_matrix[sourcevertex][destinationvertex]; } } int visited[] = new int[number_of_nodes + 1]; int element = source; int destination = source; visited = 1; stack.push(source); while (!stack.isEmpty()) { element = stack.peek(); destination = element; while (destination <= number_of_nodes) { if (adjacencyMatrix[element][destination] == 1 && visited[destination] == 1) { if (stack.contains(destination)) { System.out.println("The Graph contains cycle"); return; } } if (adjacencyMatrix[element][destination] == 1 && visited[destination] == 0) { stack.push(destination); visited[destination] = 1; adjacencyMatrix[element][destination] = 0; element = destination; destination = 1; continue; } destination++; } stack.pop(); } } 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(); System.out.println("Enter the source for the graph"); source = scanner.nextInt(); CheckCycle checkCycle = new CheckCycle(); checkCycle.dfs(adjacency_matrix, source); }catch(InputMismatchException inputMismatch) { System.out.println("Wrong Input format"); } scanner.close(); } }
$javac CheckCycle.java $java CheckCycle Enter the number of nodes in the graph 5 Enter the adjacency matrix 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 Enter the source for the graph 1 The Graph contains a cycle
Related posts:
Simple Single Sign-On with Spring Security OAuth2
Tìm hiểu về Web Service
Apache Tiles Integration with Spring MVC
Notify User of Login From New Device or Location
Rest Web service: Filter và Interceptor với Jersey 2.x (P2)
Java Program to Implement Randomized Binary Search Tree
ETL with Spring Cloud Data Flow
Guide to Spring 5 WebFlux
Overview of Spring Boot Dev Tools
Java Program to Describe the Representation of Graph using Adjacency Matrix
Java Program to Implement String Matching Using Vectors
Java Program to Implement Depth-limited Search
Java Program to Implement Knapsack Algorithm
Running Spring Boot Applications With Minikube
Guide to Dynamic Tests in Junit 5
Java Program to Implement Binomial Tree
Java Program to Implement Shoelace Algorithm
Java Program to Implement Double Order Traversal of a Binary Tree
Guide to java.util.concurrent.Locks
Spring Boot - Servlet Filter
Hashing a Password in Java
Java Program to Implement Levenshtein Distance Computing Algorithm
Number Formatting in Java
Sắp xếp trong Java 8
A Guide to the Java ExecutorService
Java List UnsupportedOperationException
Spring Security – Reset Your Password
New in Spring Security OAuth2 – Verify Claims
Loại bỏ các phần tử trùng trong một ArrayList như thế nào?
Lớp lồng nhau trong java (Java inner class)
Display Auto-Configuration Report in Spring Boot
Java – Reader to String