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:
Spring Boot - Google Cloud Platform
Java Program to Describe the Representation of Graph using Adjacency Matrix
Java Program to Implement Fermat Factorization Algorithm
Java Program to Find Basis and Dimension of a Matrix
Java – Reader to InputStream
Tránh lỗi NullPointerException trong Java như thế nào?
Java Program to Check Cycle in a Graph using Topological Sort
Working with Network Interfaces in Java
Hướng dẫn Java Design Pattern – MVC
Spring Boot Tutorial – Bootstrap a Simple Application
Hướng dẫn Java Design Pattern – Observer
Simple Single Sign-On with Spring Security OAuth2
Java Program to Find a Good Feedback Vertex Set
@Lookup Annotation in Spring
Lớp HashMap trong Java
Java Program to Implement Wagner and Fisher Algorithm for online String Matching
How to Find an Element in a List with Java
Giới thiệu Java Service Provider Interface (SPI) – Tạo các ứng dụng Java dễ mở rộng
Introduction to PCollections
Error Handling for REST with Spring
Consuming RESTful Web Services
Java Program to Use the Bellman-Ford Algorithm to Find the Shortest Path
Java Program to Implement Threaded Binary Tree
How to Get a Name of a Method Being Executed?
Java Program to Implement Johnson’s Algorithm
The DAO with Spring and Hibernate
Java Program to Find Transitive Closure of a Graph
Spring Boot - Unit Test Cases
JUnit5 @RunWith
ClassNotFoundException vs NoClassDefFoundError
Receive email by java client
Java Program to Convert a Decimal Number to Binary Number using Stacks