## 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: Breadth-First 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 ** i-th** element will store the number of edges coming into the vertex

**We will also store whether a certain vertex has been visited or not in**

*i.***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?

**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!**