Java Program for Topological Sorting in Graphs

«
»
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.

  1. import java.util.InputMismatchException;
  2. import java.util.Scanner;
  3. import java.util.Stack;
  4.  
  5. public class TopologicalSort
  6. {
  7.     private Stack<Integer> stack;
  8.  
  9.     public TopologicalSort() 
  10.     {
  11.         stack = new Stack<Integer>();
  12.     }
  13.  
  14.     public int [] topological(int adjacency_matrix[][], int source) throws NullPointerException
  15.     {
  16.         int number_of_nodes = adjacency_matrix[source].length - 1;
  17.         int[] topological_sort = new int [number_of_nodes + 1];
  18.         int pos = 1;
  19.         int j ;
  20.         int visited[] = new int[number_of_nodes + 1];
  21.         int element = source;
  22.         int i = source;
  23.         visited[source] = 1;
  24.         stack.push(source);
  25.  
  26.         while (!stack.isEmpty())
  27.         {
  28.             element = stack.peek();
  29.             while (i <= number_of_nodes)
  30.             {
  31.                 if (adjacency_matrix[element][i] == 1 && visited[i] == 1)
  32.                 {
  33.                     if (stack.contains(i))
  34.                     {
  35.                         System.out.println("TOPOLOGICAL SORT NOT POSSIBLE");
  36.                         return null;
  37.                     }
  38.                 }  
  39.                 if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
  40.                 {
  41.                     stack.push(i);
  42.                     visited[i] = 1;
  43.                     element = i;
  44.                     i = 1;
  45.                     continue;
  46.                 }
  47.                 i++;
  48.             }
  49.             j = stack.pop();	
  50.             topological_sort[pos++] = j;
  51.             i = ++j;
  52.         }
  53.         return topological_sort;
  54.     }	
  55.  
  56.     public static void main(String...arg)
  57.     {
  58.         int number_no_nodes, source;
  59.         Scanner scanner = null;
  60.         int topological_sort[]  = null;
  61.         try 
  62.         {
  63.             System.out.println("Enter the number of nodes in the graph");
  64.             scanner = new Scanner(System.in);
  65.             number_no_nodes = scanner.nextInt();
  66.  
  67.             int adjacency_matrix[][] = new int[number_no_nodes + 1][number_no_nodes + 1];
  68.             System.out.println("Enter the adjacency matrix");
  69. 	    for (int i = 1; i <= number_no_nodes; i++)
  70.                 for (int j = 1; j <= number_no_nodes; j++)
  71.                     adjacency_matrix[i][j] = scanner.nextInt();
  72.  
  73.             System.out.println("Enter the source for the graph");
  74.             source = scanner.nextInt();
  75.  
  76.             System.out.println("The Topological sort for the graph is given by ");
  77.             TopologicalSort toposort = new TopologicalSort();
  78.             topological_sort = toposort.topological(adjacency_matrix, source);
  79.             System.out.println();
  80.             for (int i = topological_sort.length - 1; i > 0; i-- )
  81.             {
  82.                 if (topological_sort[i] != 0)
  83.                     System.out.print(topological_sort[i]+"\t");
  84.             } 	
  85.         }catch(InputMismatchException inputMismatch)
  86.          {
  87.              System.out.println("Wrong Input format");
  88.          }catch(NullPointerException nullPointer)
  89.          {
  90.          }
  91.         scanner.close();
  92.     }
  93. }


$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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.