A Java Program for Topological Sorting

In this tutorial, you will be learning how to perform Topological Sorting using Java. In many situations, either directly or indirectly we might have to come up with these types of problems. So here the algorithm is a version of DFS, but in this scenario we will be maintaining an extra/temporary stack. So that we won’t be printing the nodes immediately, rather we will be calling the topological sort recursively for all its neighboring nodes and finally pushing them into the stack. Once we are completely done with this recursive topological sorting technique, we are going to print the stack.

Topological sorting is nothing else but, ordering of the vertices only if there exist an edge between two nodes/vertices u, v then u should appear before v in topological sorting. It is only possible for Directed Acyclic Graph (DAG) because of the, linear ordering of its vertices/nodes. As the name DAG indicates which consists of zero cycles in it. In other words the topological sort algorithm takes a directed graph as its input and returns an array of the nodes as the output, where each node appears before all the nodes it points to.

For a given Directed Acyclic Graph there might be multiple different topological orderings, where the ordering of the nodes in the array is termed as Topological Ordering.

Topological Sorting in Java

The source code of the Java Program for the above Implementation is as follows,

// Java program for topological sorting of a DAG 
import java.io.*; 
import java.util.*; 
  
class TopoSort 
{ 
  private int V; // No. of vertices 
  // Adjacency List as ArrayList of ArrayList's 
  private ArrayList<ArrayList<Integer>> adj; 
  
  TopoSort(int v) 
  { 
    V = v; 
    adj = new ArrayList<ArrayList<Integer>>(v); 
    for (int i=0; i<v; ++i) 
      adj.add(new ArrayList<Integer>()); 
  } 
  
  // Function to add an edge into the graph 
  void addEdge(int v,int w) 
  {
    adj.get(v).add(w); 
  } 
  
  // A recursive function used by the topologicalSort function 
  void topologicalSortUtil(int v, boolean visited[], Stack<Integer> st) 
  { 
    // It Marks the current node as visited. 
    visited[v] = true; 
    Integer i; 

    Iterator<Integer> it = adj.get(v).iterator(); 
    while (it.hasNext()) 
    { 
      i = it.next(); 
      if (!visited[i]) 
        topologicalSortUtil(i, visited, st); 
    } 
  
    // Push current vertex into the stack which stores the result 
    st.push(new Integer(v)); 
  } 
  
  // The function to perform Topological Sort. It uses 
  // recursive topologicalSortUtil() 
  void topologicalSort() 
  { 
    Stack<Integer> st = new Stack<Integer>(); 
  
    // Mark all the vertices as not visited 
    boolean visited[] = new boolean[V]; 
    for (int i = 0; i < V; i++) 
      visited[i] = false; 
  

    for (int i = 0; i < V; i++) 
      if (visited[i] == false) 
        topologicalSortUtil(i, visited, st); 
  
    // Print the contents of stack 
    while (st.empty()==false) 
      System.out.print(st.pop() + " "); 
  } 
  
  public static void main(String args[]) 
  { 
    // Create a graph given in the above diagram 
    TopoSort dg = new TopoSort(6); 
    dg.addEdge(5, 2); 
    dg.addEdge(5, 0); 
    dg.addEdge(4, 0); 
    dg.addEdge(4, 1); 
    dg.addEdge(2, 3); 
    dg.addEdge(3, 1); 
    System.out.println("After performing the Topological Sort, the given graph is:"); 
    dg.topologicalSort(); 
  } 
}

Output when you run the above program:

After performing the Topological Sort, the given graph is:
5 4 2 3 1 0

 Time Complexity: Since the above algorithm is simply a DFS with an extra stack. So here the time complexity will be same as DFS which is O (V+E).

Applications of Topological Sort:

Few important applications of topological sort are as follows,

  • Scheduling jobs
  • Instruction Scheduling
  • Data Serialization

Leave a Reply

Your email address will not be published. Required fields are marked *