# Kahn’s Topological Sort Algorithm

Given a directed acyclic graph (DAG), print it in Topological order using Kahn’s Topological Sort algorithm. If the DAG has more than one topological ordering, print any of them.

A Topological Sort or Topological Ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. A topological ordering is possible if and only if the graph has no directed cycles, i.e. if the graph is DAG.

For example, consider below graph: Above graph has many valid topological ordering of vertices like,

7, 5, 3, 1, 4, 2, 0, 6
7, 5, 1, 2, 3, 4, 0, 6
5, 7, 3, 1, 0, 2, 6, 4
3, 5, 7, 0, 1, 2, 6, 4
5, 7, 3, 0, 1, 4, 6, 2
7, 5, 1, 3, 4, 0, 6, 2
5, 7, 1, 2, 3, 0, 6, 4
3, 7, 0, 5, 1, 4, 2, 6

.. and many more

Note that for every directed edge u -> v, u comes before v in the ordering. For example, the pictorial representation of the topological order [7, 5, 3, 1, 4, 2, 0, 6] is: In the previous post, we have seen how to print topological order of a graph using Depth First Search (DFS) algorithm. In this post, Kahn’s Topological Sort algorithm is introduced which provides a efficient way to print topological order of a graph.

Kahn’s Topological Sort Algorithm works by finding vertices which have no incoming edges and removing all outgoing edges from these vertices. Below is psedocode for Kahn’s Topological Sort Algorithm taken from Wikipedia –

Kahn’s-Algorithm (graph)

L -> Empty list that will contain the sorted elements
S -> Set of all vertices with no incoming edges (i.e. having indegree 0)

while S is non-empty do
remove a vertex n from S
add n to tail of L
for each vertex m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S

if graph has edges then
return report “graph has at least one cycle”
else
return L “a topologically sorted order”

Note that a DAG has at least one such vertex which has no incoming edges.

##### How can we remove an edge from the graph or check if a vertex has no other incoming edge in constant time?

The idea is to maintain in-degree information of all graph vertices in a map or an array (say indegree[]) for constant time operations. Here, indegree[m] will store number of incoming edges to vertex m.

• If vertex m has no incoming edge and is ready to get processed, its indegree will be 0 i.e. indegree[m] = 0.

• To remove an edge from n to m from the graph, we decrement indegree[m] by 1.

Below is C++/Java implementation of Kahn’s Topological Sort Algorithm:

Output:

7 5 1 2 3 4 0 6

## Java

Output:

7 5 1 2 3 4 0 6

Time complexity of Kahn’s Topological Sort Algorithm is O(n + m) where n is number of vertices and m is number of edges in the graph.     (1 votes, average: 5.00 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂 Subscribe
Notify of Guest

Good article! Haven’t seen a lot of CS people gravitate towards C++ for algorithms, and IMO, I think it forces one to really think about both Complexity, and ADT interfacing. Both that are crucial for good API design and implementation.

The Most Interesting Software Engineer in the World:
He parallel parked a train… He used a PS2 monitor… He let Donald Knuth copy his homework…
“I don’t always implement my pseudocode, but when I do, I use C++.” Guest
arandomguy

In line 85, why use two loops? Simply
`for(int i=0;i<N;i++) if(indegree[i]) return false;`
is enough.
After all indegree is an attribute of node and not edge.