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 Map With Case-Insensitive Keys
Java Program to Implement Bellman-Ford Algorithm
Abstract class và Interface trong Java
Introduction to Using Thymeleaf in Spring
Java Program to implement Array Deque
Tạo ứng dụng Java RESTful Client không sử dụng 3rd party libraries
ExecutorService – Waiting for Threads to Finish
Java Program to Use Boruvka’s Algorithm to Find the Minimum Spanning Tree
Spring Boot - Rest Controller Unit Test
Guide to Escaping Characters in Java RegExps
Java Program to Generate a Random UnDirected Graph for a Given Number of Edges
Hướng dẫn sử dụng Java String, StringBuffer và StringBuilder
Java Program to Perform Naive String Matching
Guide to ThreadLocalRandom in Java
Thực thi nhiều tác vụ cùng lúc như thế nào trong Java?
Inheritance with Jackson
A Guide to @RepeatedTest in Junit 5
Java Program to Perform Finite State Automaton based Search
Spring Boot Tutorial – Bootstrap a Simple Application
HttpClient Basic Authentication
Returning Custom Status Codes from Spring Controllers
Service Registration with Eureka
Spring Boot - Logging
Hướng dẫn Java Design Pattern – Iterator
The “final” Keyword in Java
Java Program to Perform Polygon Containment Test
New Features in Java 12
Life Cycle of a Thread in Java
A Guide to System.exit()
Retrieve User Information in Spring Security
Spring Boot - Cloud Configuration Server
Hướng dẫn Java Design Pattern – DAO