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:

Kahn's Topological Sort Algorithm

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:

 
Kahn's Topological Sort Algorithm

 
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++ implementation of Kahn’s Topological Sort Algorithm:
 

Download   Run Code

Output:

7 5 1 2 3 4 0 6

 
Time complexity of Kahn’s Toplogical Sort Algorithm is O(n + m) where n is number of vertices and e is number of edges in the graph.

 
References: https://en.wikipedia.org/wiki/Topological_sorting#Kahn.27s_algorithm

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Steve
Guest
Steve

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++.”

wpDiscuz