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
 Introduction to Graph in Programming
 Graph Traversal: Depth First Search
 Graph Traversal: BreadthFirst Search
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 ith 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 N1 )
in_degree[i] = visited[i] = false
for ( i = 0 to N1 )
for ( j = 0 to N1 )
if (adj[i][j] == true)
in_degree[j] += 1
Q = Queue()
for ( i = 0 to N1 )
{
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 N1 )
{
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?
Graph questions
 Is Graph Bipartite?
 Number of Islands
 Word Ladder Problem
 Smallest Multiple with 0 and 1
 Course Schedule
 Knight on Chessboard
Happy Learning, Enjoy Algorithms!
Team AfterAcademy!