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:
Convert a Map to an Array, List or Set in Java
Java Program to Check the Connectivity of Graph Using BFS
Java Program to Perform LU Decomposition of any Matrix
Supplier trong Java 8
Implementing a Runnable vs Extending a Thread
Spring Boot with Multiple SQL Import Files
Java Program to Find Basis and Dimension of a Matrix
Java 8 Predicate Chain
Java Program to Generate All Subsets of a Given Set in the Lexico Graphic Order
Java Program to Perform Preorder Recursive Traversal of a Given Binary Tree
ETL with Spring Cloud Data Flow
Notify User of Login From New Device or Location
Send an email with an attachment
Comparing Two HashMaps in Java
Java Program to Implement an Algorithm to Find the Global min Cut in a Graph
Send an email using the SMTP protocol
Guide to BufferedReader
Java Program to Implement ConcurrentLinkedQueue API
Simple Single Sign-On with Spring Security OAuth2
Spring REST API with Protocol Buffers
Java – String to Reader
New Features in Java 8
Remove the First Element from a List
Java Program to Generate All Possible Combinations of a Given List of Numbers
Properties with Spring and Spring Boot
Spring RestTemplate Error Handling
Java Program to Implement Aho-Corasick Algorithm for String Matching
Guide to Guava Multimap
Java Program to Implement Euclid GCD Algorithm
Java Program to Implement Network Flow Problem
Java Program to Print only Odd Numbered Levels of a Tree
Java Program to Check if any Graph is Possible to be Constructed for a Given Degree Sequence