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:
How to Iterate Over a Stream With Indices
Using JWT with Spring Security OAuth (legacy stack)
Most commonly used String methods in Java
Hướng dẫn sử dụng String Format trong Java
Spring MVC Setup with Kotlin
Java Program to Check if a Point d lies Inside or Outside a Circle Defined by Points a, b, c in a Pl...
Java Program to Implement Sorted List
Spring Cloud – Tracing Services with Zipkin
Difference Between Wait and Sleep in Java
Java Program to find the maximum subarray sum using Binary Search approach
Java Program to Implement Kosaraju Algorithm
Registration – Password Strength and Rules
Tính kế thừa (Inheritance) trong java
Java Program to Implement Min Heap
Java Program to Compute DFT Coefficients Directly
Java Program to Solve Knapsack Problem Using Dynamic Programming
Removing all Nulls from a List in Java
Command-Line Arguments in Java
A Guide to Concurrent Queues in Java
Java Program to Implement Quick sort
Java Program to Perform Partial Key Search in a K-D Tree
Java Program to Implement Suffix Tree
A Guide to BitSet in Java
Jackson – Marshall String to JsonNode
Java Program to Implement Sorted Doubly Linked List
Create a Custom Exception in Java
Java Program to Implement a Binary Search Tree using Linked Lists
SOAP Web service: Authentication trong JAX-WS
Class Loaders in Java
Quick Guide to java.lang.System
Introduction to the Java NIO2 File API
How To Serialize and Deserialize Enums with Jackson