This Java program,to perform the topological Sort on a given graph by the DFS method.The topological sort is performed on a directed acyclic graph.
Here is the source code of the Java program to check for cycle in topological sort. 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 TopoCycle { private Stack<Integer> stack; public TopoCycle() { stack = new Stack<Integer>(); } public boolean checkCycle(int adjacency_matrix[][], int source) { int number_of_nodes = adjacency_matrix.length - 1; int[] topological_sort = new int [number_of_nodes + 1]; int pos = 1; int j; boolean cycle = false; int visited[] = new int[number_of_nodes + 1]; int element = source; int i = source; visited = 1; stack.push(source); while (!stack.isEmpty()) { element = stack.peek(); while (i <= number_of_nodes) { if (adjacency_matrix[element][i] == 1 && visited[i] == 1) { if (stack.contains(i)) { System.out.println("The Graph Contains a cycle"); cycle = true; return cycle; } } if (adjacency_matrix[element][i] == 1 && visited[i] == 0) { stack.push(i); visited[i] = 1; element = i; i = 1; continue; } i++; } j = stack.pop(); topological_sort[pos++] = j; i = ++j; } System.out.println("The Graph does not Contain cycle"); return cycle; } public static void main(String...arg) { int number_no_nodes, source; Scanner scanner = null; try { System.out.println("Enter the number of nodes in the graph"); scanner = new Scanner(System.in); number_no_nodes = scanner.nextInt(); int adjacency_matrix[][] = new int[number_no_nodes + 1][number_no_nodes + 1]; System.out.println("Enter the adjacency matrix"); for (int i = 1; i <= number_no_nodes; i++) for (int j = 1; j <= number_no_nodes; j++) adjacency_matrix[i][j] = scanner.nextInt(); System.out.println("Enter the source for the graph"); source = scanner.nextInt(); TopoCycle topoCycle = new TopoCycle(); topoCycle.checkCycle(adjacency_matrix, source); }catch(InputMismatchException inputMismatch) { System.out.println("Wrong Input format"); } scanner.close(); } }
$javac TopoCycle.java $java TopoCycle Enter the number of nodes in the graph 5 Enter the adjacency matrix 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 Enter the source for the graph 1 The Graph contains a cycle
Related posts:
Java Program to Find the Minimum Element of a Rotated Sorted Array using Binary Search approach
Java Program to Find the Shortest Path Between Two Vertices Using Dijkstra’s Algorithm
Java Program to Find a Good Feedback Edge Set in a Graph
Java Program to Implement Hash Tables Chaining with Doubly Linked Lists
Guide to System.gc()
Java Program to Implement Shunting Yard Algorithm
Java Program to Perform the Shaker Sort
Java Program to Implement a Binary Search Tree using Linked Lists
Spring Boot - Introduction
Java – String to Reader
Hướng dẫn Java Design Pattern – Abstract Factory
A Guide to ConcurrentMap
Jackson vs Gson
Java Web Services – JAX-WS – SOAP
Java Program to Check whether Undirected Graph is Connected using DFS
Spring WebClient Filters
Java Program to Find the Peak Element of an Array O(n) time (Naive Method)
Các nguyên lý thiết kế hướng đối tượng – SOLID
Guide to DelayQueue
HashSet trong java
How to Define a Spring Boot Filter?
Java Program to Implement Self organizing List
Java Program to Check Whether Graph is DAG
How to Iterate Over a Stream With Indices
Java Program to Implement Heap Sort Using Library Functions
Guide to Apache Commons CircularFifoQueue
Java program to Implement Tree Set
Static Content in Spring WebFlux
Ways to Iterate Over a List in Java
Anonymous Classes in Java
Using Spring ResponseEntity to Manipulate the HTTP Response
Java Program to Perform Encoding of a Message Using Matrix Multiplication