What is topological sort?

Topological sort gives a linear ordering of vertices in a directed acyclic graph such that, for every directed edge a -> b, vertex ‘a’ comes before vertex ‘b’. Remember, a directed acyclic graph has at least one vertex with an in-degree of 0 and one vertex with an out-degree of 0.

There can be more than one topological ordering for a directed acyclic graph.

Kahn’s Algorithm

Kahn’s algorithm is used to perform a topological sort on a directed acyclic graph with time complexity of $O(V + E)$ – where $V$ is the number of vertices and $E$ is the number of edges in the graph.

The steps below are involved in Kahn’s algorithm:

Auxiliary variables:

1. An array (“temp”) to hold the result of the preprocessing stage.

2. A variable (“visited”) to store the number of vertices that have been visited.

3. A string (“result”) to hold the topological sort order.

4. A queue.

Pre-processing:

Calculate the in-degree of each vertex of the graph and store them in the array “temp”.

Actual steps:

1. Enqueue the vertices with the in-degree of 0.

2. While the queue is not empty:

   2.1. Dequeue a vertex.

   2.2. Add this vertex to the result.

   2.3. Increment the “visited” variable by 1.

   2.4. Decrement the in-degree of all its neighboring vertices by 1 in the array “temp”.

   2.5 Enqueue the neighboring vertices with the in-degree of 0.

3. If the value of the “visited” variable is equal to the number of vertices in the graph, then the graph is indeed directed and acyclic ​and the result will contain the topological sort for the graph.

The following illustration shows the algorithm in action: