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:
Java Program to Generate All Possible Subsets with Exactly k Elements in Each Subset
Java Program to Implement wheel Sieve to Generate Prime Numbers Between Given Range
Filtering a Stream of Optionals in Java
Java Program to Check Whether Topological Sorting can be Performed in a Graph
Basic Authentication with the RestTemplate
Fixing 401s with CORS Preflights and Spring Security
Remove HTML tags from a file to extract only the TEXT
Overview of the java.util.concurrent
CyclicBarrier in Java
Java Program to Implement Skip List
Java Program to Implement Sorted Circularly Singly Linked List
Java Program to Find Inverse of a Matrix
Java Program to Check if a Matrix is Invertible
Spring REST API with Protocol Buffers
Dockerizing a Spring Boot Application
Service Registration with Eureka
Java – Reader to InputStream
Extra Login Fields with Spring Security
Java Program to Implement the Alexander Bogomolny’s UnOrdered Permutation Algorithm for Elements Fro...
Java Program to Implement Stack API
Java Program to Implement Hash Tables with Quadratic Probing
How to Set TLS Version in Apache HttpClient
Intersection of Two Lists in Java
Java Program to Emulate N Dice Roller
Spring Data – CrudRepository save() Method
Java Program to Perform Inorder Non-Recursive Traversal of a Given Binary Tree
Java Program to Implement Graph Coloring Algorithm
Guava CharMatcher
Bootstrapping Hibernate 5 with Spring
The DAO with Spring and Hibernate
Handle EML file with JavaMail
Check If a File or Directory Exists in Java