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:
Shuffling Collections In Java
Spring AMQP in Reactive Applications
Java Program to Implement Vector API
New in Spring Security OAuth2 – Verify Claims
Java Program to Implement Horner Algorithm
Java Program to Implement Singly Linked List
Spring Boot Integration Testing with Embedded MongoDB
A Guide to BitSet in Java
Hướng dẫn sử dụng String Format trong Java
Java program to Implement Tree Set
Java Program to Implement Rope
HashSet trong Java hoạt động như thế nào?
Java Program to Implement Skip List
Create Java Applet to Simulate Any Sorting Technique
Java Program to Implement the Hungarian Algorithm for Bipartite Matching
Spring REST API + OAuth2 + Angular
Finding the Differences Between Two Lists in Java
Spring Boot - Creating Docker Image
Java Program to Perform Searching Based on Locality of Reference
Remove the First Element from a List
Spring Boot - Batch Service
Java Program to Find the Number of Ways to Write a Number as the Sum of Numbers Smaller than Itself
Lập trình đa luồng trong Java (Java Multi-threading)
Testing an OAuth Secured API with Spring MVC
Java Program to Implement Uniform-Cost Search
Custom Cascading in Spring Data MongoDB
Java Program to Construct an Expression Tree for an Infix Expression
Hướng dẫn sử dụng Java Annotation
Uploading MultipartFile with Spring RestTemplate
Marker Interface trong Java
Overview of the java.util.concurrent
Java Program to Perform Sorting Using B-Tree