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:
Tạo số và chuỗi ngẫu nhiên trong Java
Ways to Iterate Over a List in Java
Java Program to Find Minimum Element in an Array using Linear Search
Registration – Password Strength and Rules
Giới thiệu SOAP UI và thực hiện test Web Service
Xử lý ngoại lệ đối với trường hợp ghi đè phương thức trong java
Java Program to Perform Deletion in a BST
Converting a Stack Trace to a String in Java
How to Manually Authenticate User with Spring Security
Spring Boot Application as a Service
Sử dụng CyclicBarrier trong Java
Sort a HashMap in Java
Spring NoSuchBeanDefinitionException
Spring Cloud – Tracing Services with Zipkin
Java Program to Evaluate an Expression using Stacks
Java Program to Implement Sparse Matrix
Registration with Spring Security – Password Encoding
Java Program to Implement Fermat Primality Test Algorithm
Java Program to Check whether Undirected Graph is Connected using DFS
Đồng bộ hóa các luồng trong Java
File Upload with Spring MVC
Java Program to Check Whether Graph is DAG
Java 8 Stream findFirst() vs. findAny()
Hướng dẫn Java Design Pattern – Builder
ArrayList trong java
Java Copy Constructor
Java Program to Implement an Algorithm to Find the Global min Cut in a Graph
Quick Guide to java.lang.System
Spring Boot - Interceptor
Creating a Generic Array in Java
Java – InputStream to Reader
Java Program to find the maximum subarray sum using Binary Search approach