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 Implement Tree Set
Kiểu dữ liệu Ngày Giờ (Date Time) trong java
Kết hợp Java Reflection và Java Annotations
Guide to Escaping Characters in Java RegExps
Split a String in Java
Java Program to Implement ConcurrentLinkedQueue API
Spring MVC Async vs Spring WebFlux
Generating Random Numbers in a Range in Java
Java Program to Implement LinkedBlockingQueue API
Batch Processing with Spring Cloud Data Flow
Send an email using the SMTP protocol
Weak References in Java
Java Program to Construct K-D Tree for 2 Dimensional Data
Java Program to Find Strongly Connected Components in Graphs
OAuth 2.0 Resource Server With Spring Security 5
Java Program to Perform Partition of an Integer in All Possible Ways
Java Program to Implement Johnson’s Algorithm
Java Program to Implement LinkedHashSet API
Java Program to Check Whether a Directed Graph Contains a Eulerian Cycle
Java Program to Implement HashSet API
Converting Iterator to List
Spring WebClient Filters
Java Program to Implement SimpeBindings API
Java Program to Implement Variable length array
Các nguyên lý thiết kế hướng đối tượng – SOLID
Guide to the Volatile Keyword in Java
Difference Between Wait and Sleep in Java
Spring Boot - Batch Service
Use Liquibase to Safely Evolve Your Database Schema
Java Program to Implement Sieve Of Sundaram
Java Program to Check Whether a Given Point is in a Given Polygon
Abstract class và Interface trong Java