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:
Java Program to Implement Interpolation Search Algorithm
Convert Character Array to String in Java
HttpClient Connection Management
Deque và ArrayDeque trong Java
Java Program to Implement Bubble Sort
Java Program to Implement Hash Tables with Quadratic Probing
What is a POJO Class?
Iterating over Enum Values in Java
HttpClient with SSL
Java 8 and Infinite Streams
Java Program to Perform Arithmetic Operations on Numbers of Size
How to Store Duplicate Keys in a Map in Java?
Xử lý ngoại lệ trong Java (Exception Handling)
Java Program to Implement Naor-Reingold Pseudo Random Function
Performance Difference Between save() and saveAll() in Spring Data
Java Program to Implement Max-Flow Min-Cut Theorem
Spring Data JPA @Modifying Annotation
Using Spring ResponseEntity to Manipulate the HTTP Response
Guide to CountDownLatch in Java
Java Program to Implement Find all Cross Edges in a Graph
Guide to java.util.Formatter
Java Program to Implement the Vigenere Cypher
Flattening Nested Collections in Java
Java Program to Implement Fenwick Tree
A Guide to the Java LinkedList
Converting between an Array and a List in Java
Java Program to Implement HashMap API
Custom Cascading in Spring Data MongoDB
Java Program to Implement Binary Heap
Spring Autowiring of Generic Types
Java Program to Optimize Wire Length in Electrical Circuit
REST Pagination in Spring