Summary: In this tutorial, we will learn what Kahn’s Topological Sort algorithm is and how to obtain the topological ordering of the given graph using it.

Introduction to Topological Sort

Topological ordering of a directed graph is the ordering of its vertices such that for each directed edge from vertex A to vertex B, vertex A appears before vertex B in the ordering.

Topological Sort
One of the Topological orders of the given graph.

Topological sorting sorts vertices in such a way that every directed edge of the graph has the same direction.

It is important to note that the same graph may have different topological orders.

Topological ordering is only possible for the Directed Acyclic Graphs (i.e., DAG). Graph with cycles cannot be topologically sorted.

Kahn’s Algorithm for Topological Sort

Kahn’s algorithm in order to form topological order constantly looks for the vertices that have no incoming edge and removes all outgoing edges from them.

Basically, the algorithm:

  1. Finds the vertex that has no incoming edges.
  2. Remove all outgoing edges from that vertex.
  3. Add vertex to the topological order.
  4. Repeat the process until all the vertices are processed.
Khan's Topological Sort Algorithm
Illustration of Kahn’s Algorithm.
Note: The order may differ depending on which vertices are processed first.

Implementation of the Algorithm

In programming, to perform edge related operations, we use another graph property known as a degree.

A degree to a vertex is the number of incoming edges.

A degree represents how many incoming edges does a vertex has. A vertex with 0 degrees means no incoming edges.

We use Queue to process those vertices because it follows the First In First Out (FIFO) pattern.

To implement Kahn’s Topological Algorithm:

  1. We look for 0-degree vertices in the given graph and add them to the queue.
  2. We process the vertices one by one until the queue is emptied.
    1. We pop a vertex from the queue and add it in topological order.
    2. After that, we decrement the degree of all its adjacent vertices (apparently to remove the outgoing edges).
    3. We add it to the queue if the degree of any adjacent vertex is reduced to zero.
  3. Once all the vertices are processed, we print the order.

Here is the implementation of the algorithm in Python, C++ and Java:

Python

C++

Java

Output:

Python: [A, C, B, D, E, F]
C++: [A, B, C, E, D, F]
Java: [A, B, C, E, D, F]


The order of different languages is not the same, yet all are correct.

The orders are such that for each directed edge from vertex A to vertex B, vertex A appears before vertex B in the ordering.

In the above programs, the init_degree() method calculates the degree of each vertex of a given graph. We have called this method before the sorting process.

If there is a cycle in the graph, some vertices will be processed several times. In that case, the count of processed vertices exceeds the number of vertices in the graph, and topological order is not possible.

In this tutorial, we learned to get the topological ordering of the vertices of the given graph using the Kahn’s Topological Sort Algorithm

Leave a Reply

3 × 3 =