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 perform the Topological Sort on the 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 TopologicalSort { private Stack<Integer> stack; public TopologicalSort() { stack = new Stack<Integer>(); } public int [] topological(int adjacency_matrix[][], int source) throws NullPointerException { int number_of_nodes = adjacency_matrix.length - 1; int[] topological_sort = new int [number_of_nodes + 1]; int pos = 1; int j ; 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("TOPOLOGICAL SORT NOT POSSIBLE"); return null; } } 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; } return topological_sort; } public static void main(String...arg) { int number_no_nodes, source; Scanner scanner = null; int topological_sort[] = 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(); System.out.println("The Topological sort for the graph is given by "); TopologicalSort toposort = new TopologicalSort(); topological_sort = toposort.topological(adjacency_matrix, source); System.out.println(); for (int i = topological_sort.length - 1; i > 0; i-- ) { if (topological_sort[i] != 0) System.out.print(topological_sort[i]+"\t"); } }catch(InputMismatchException inputMismatch) { System.out.println("Wrong Input format"); }catch(NullPointerException nullPointer) { } scanner.close(); } }
$javac TopologicalSort.java $java TopologicalSort Enter the number of nodes in the graph 4 Enter the adjacency matrix 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 Enter the source for the graph 1 The Topological sort for the graph is given by 1 2 4 3
Related posts:
Setting Up Swagger 2 with a Spring REST API
Java Program to Check Cycle in a Graph using Topological Sort
Using Java Assertions
Generate Spring Boot REST Client with Swagger
Java Program to Implement Warshall Algorithm
Using a List of Values in a JdbcTemplate IN Clause
Java Program to Implement Adjacency List
Queue và PriorityQueue trong Java
Java – Reader to Byte Array
Shuffling Collections In Java
Getting Started with Stream Processing with Spring Cloud Data Flow
Spring MVC Tutorial
Encode a String to UTF-8 in Java
Circular Dependencies in Spring
Java Program to Implement Self Balancing Binary Search Tree
Programmatic Transaction Management in Spring
Java NIO2 Path API
Java Program to Check Whether an Input Binary Tree is the Sub Tree of the Binary Tree
Spring Boot Annotations
Jackson Exceptions – Problems and Solutions
Java Program to Find Nearest Neighbor for Static Data Set
Tạo ứng dụng Java RESTful Client không sử dụng 3rd party libraries
Java Program to Generate Date Between Given Range
A Guide to @RepeatedTest in Junit 5
Format ZonedDateTime to String
Tính kế thừa (Inheritance) trong java
Recommended Package Structure of a Spring Boot Project
Check if a String is a Palindrome in Java
Hướng dẫn Java Design Pattern – Object Pool
Jackson – Decide What Fields Get Serialized/Deserialized
Function trong Java 8
Hướng dẫn sử dụng biểu thức chính quy (Regular Expression) trong Java