## 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)

#### 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 )
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?

#### Graph questions

Happy Learning, Enjoy Algorithms!