In this article, we will learn how to find the Topological sort of a directed acyclic graph using Kahn's Algo.

But wait...

Before diving into topological sorting, we need to understand some important terms.

• Indegree - Indegree of a vertex is defined as the number of edges pointing towards it.
• Outdegree - Outdegree of a vertex is defined as number of edges going out from the vertex.
• Source Vertex - A vertex with no edges pointing towards it. It has edges that only point outwards.
• Sink Vertex - A vertex with no outgoing edges. It has edges that only points towards it.

Let's consider the vertex A in the following graph.

The indegree of vertex A is zero as there are no incoming edges.
Vertex A has two outgoing edges, thus the outdegree of vertex A is two.

A is source vertex as it has zero indegree.
C and D are sink vertices as they have zero outdegree.

Topological Sorting

The DAG's are complicated. Topological sorting simplifies our DAG's so that we can easily understand the relationship between vertices.

Topological sorting sorts the vertices of the DAG's in such order that edges flow in one direction. (Left to right/Right to left). The above DAG will look like this after applying top sort. The source vertex is on the extreme left while the sink vertices are at the extreme right.

Basically, it rearranges the vertices of our DAG's in a linear fashion. Now we can easily observe the flow edges, it also helps us to understand, which vertices can reach which vertices.

It can also be seen as a hierarchical way of executing a task in which the left task should be done before the next task.

Kahn's Algo to find Top Sort

Consider the following graph.

According to Kahn's Algo, First, we need to find the indegree of all the vertices.

The next step is to find the vertex having zero indegree (source vertex). In our case, vertex 1 is having zero indegree. It will be the first node in topological order. Let's write it down.

Topological order -> 1

Let's find out the remaining vertices also. Delete this vertex from the graph and all the outgoing edges. Update the indegree of the remaining vertices. The graph will look like this after removing vertex 1 and its outgoing edges.

Now again find the vertex having zero indegree. In our case, it is the vertex 2. Write it down after vertex 1 in the topological order.

Topological order -> 1 2

Delete the vertex 2 from the graph and all of its outgoing edges. After finding the indegree of the remaining vertices, the graph will look like this.

Now Vertex 4 has zero indegree. Write down the vertex 4 in topological order, remove it from the graph, and all its outgoing edges.

Topological order - 1 2 4

After updating the indegree of the remaining vertices. we have vertex 3 and vertex 5 with zero indegree. We will consider both one by one.

If we consider vertex 3 first, the topological order will become - 1 2 4 3 5 if we consider vertex 5 first, the topological order will become - 1 2 4 5 3

Thus, we found two topological orders for the above graph.

Top Sort is different from other sorting algorithms in such a way that the order of vertices can differ but the flow of edges remains consistent. In the above diagrams A and B, the vertices 3 and 5 have different positions but the flow of edges towards them remains consistent.

Coding

Now it's time for the most exciting part. We will write a program to find the topological ordering of the Directed Acyclic Graphs.

In simple words, we will keep finding vertices with no incoming edges and removing all outgoing edges from these vertices. We will do this until all the vertices have been visited. The first vertex in topological order will always be a vertex having zero incoming edges (zero indegree).

Kahn's Algorithm

Step 1 - Find the indegree of all the vertices and store it in an array or vector.

Step 2 - Pick all the vertices having zero indegrees and push them into the queue.

Step 3 - Pop a vertex from the front of the queue and push it into the result array.

• Increase the count of visited vertices by 1.
• Reduce the in-degree of neighboring vertices by 1.
• If the in-degree of any vertex becomes zero then push it into the queue.

Step 4 - Repeat Step 3 until the queue is empty.

Step 5 - If the count of visited nodes is not equal to the count of vertices in the graph, then there must be a cycle in the graph and topological ordering is not possible.

Time Complexity

The Time Complexity of this program is O(V+E) and Space Complexity is O(V). Where V is the number of vertices and E is the number of edges in the graph.

I hope you learned something new today.