Java Program to Apply DFS to Perform the Topological Sorting of a Directed Acyclic Graph

This is a java program to find topological sort of DAG. In computer science, a topological sort (sometimes abbreviated topsort or toposort) or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time.

Here is the source code of the Java Program to Apply DFS to Perform the Topological Sorting of a Directed Acyclic Graph. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

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

Output:

 
 
Enter the number of nodes in the graph
6
Enter the adjacency matrix
0 1 0 0 0 0
0 0 1 1 0 0 
0 0 0 0 0 0 
0 0 0 0 1 0
0 0 0 0 0 1
0 0 1 1 0 0 
Enter the source for the graph
1
The Topological sort for the graph is given by 
TOPOLOGICAL SORT NOT POSSIBLE
 
Enter the number of nodes in the graph
6
Enter the adjacency matrix
0 1 0 0 0 1
0 0 1 1 0 0
0 0 0 0 0 0 
0 0 0 0 1 0
0 0 0 0 0 1
0 0 1 0 0 0
Enter the source for the graph
1
The Topological sort for the graph is given by 
1	2	4	5	6	3

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

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 & discussions at Telegram SanfoundryClasses.