Topological Sorting

In this blog, we will discuss Topological sort in a Directed Acyclic Graph i.e. DAG. We will discuss the following things:

  • What is the Topological Sort?
  • How can we find Topological Ordering?
  • Illustration using a Directed Acyclic Graph
  • Pseudo Code
  • Applications of Topological Sorting


What is Topological Sort

In the Directed Acyclic Graph, Topological sort is a way of the linear ordering of vertices v1, v2, …. vN in such a way that for every directed edge x → y, x will come before y in the ordering.

For example-The topological sort for the below graph is 1, 2, 4, 3, 5

Important Points to remember

  • There can be multiple topological ordering for a Directed Acyclic Graph.
  • In order to have a topological sorting, the graph must not contain any cycles and it must be directed i.e. the graph must be a DAG. (Think!)

How to find Topological Sort

Topological order can be one of the subsets of all the permutations of all the vertices following the condition that for every directed edge x → y, x will come before y in the ordering.

For that, we will maintain an array T[ ], which will store the ordering of the vertices in topological order. We will store the number of edges that are coming into a vertex in an array in_degree[N], where the i-th element will store the number of edges coming into the vertex i. We will also store whether a certain vertex has been visited or not in visited[N]. We will follow the belo steps:

  • First, take out the vertex whose in_degree is 0. That means there is no edge that is coming into that vertex.
  • We will append the vertices in the Queue and mark these vertices as visited.
  • Now we will traverse through the queue and in each step we will dequeue() the front element in the Queue and push it into the T.
  • Now, we will put out all the edges that are originated from the front vertex which means we will decrease the in_degree of the vertices which has an edge with the front vertex.
  • Similarly, for those vertices whose in_degree is 0, we will push it in Queue and also mark that vertex as visited. (Hope you must be thinking its BFS but with in_degree)


Pseudo Code

topological_ordering(int N, bool adj[N][N]) 
    int T[]
    bool visited[N]
    int in_degree[N]
    for ( i = 0 to N-1 )
        in_degree[i] = visited[i] = false
    for ( i = 0 to N-1 )
        for ( j = 0 to N-1 )
            if (adj[i][j] == true)
                in_degree[j] += 1
    Q = Queue()
    for ( i = 0 to N-1 )
        if ( in_degree[i] == 0 ) {
            visited[i] = true
    while( Q.size() != 0 )
        curr = Q.front()
        for( j = 0 to N-1 )
            if ( adj[curr][j] == true and visited[j] == false)
                in_degree[j] -= 1
                if (in_degree[j] == 0)
                    visited[j] = true
    return T


  • Scheduling jobs from given dependencies among Jobs. For example, if some job requires the dependency of some other job, then we can use topological sorting.
  • Instruction Scheduling
  • Determining the order of compilation tasks to perform in makefiles, data serializations and resolving symbol dependencies in linkers.
  • Use in maven dependency resolutions.

Critical Ideas to Think

  • The above approach uses the BFS traversal technique. Can it be solved using the DFS traversal technique?
  • What can be the modifications that can be done if we have been given the Adjacency matrix?

Graph questions

Happy Learning, Enjoy Algorithms!

Team AfterAcademy!