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

Prerequisites

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)

Illustration

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 ) {
            Q.enqueue(i);
            visited[i] = true
        }
    }
    
    while( Q.size() != 0 )
    {
        curr = Q.front()
        Q.dequeue();
        T.append(curr);
        for( j = 0 to N-1 )
        {
            if ( adj[curr][j] == true and visited[j] == false)
            {
                in_degree[j] -= 1
                if (in_degree[j] == 0)
                {
                    Q.enqueue(j)
                    visited[j] = true
                }
            }
        }
    }
    
    return T
}

Applications

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?