Kahn’s Algorithm for Topological Sort

Implementation:

BFS + Queue

We will have a Adjacency List, on array which consists of degree of each vertex and a Queue

Let’s see and traverse this algorithm for the graph given below.

Step 1: Find incoming degree for each vertex and store it in the array

Step 2: Push all the nodes with incoming degree zero in the Queue. As the nodes with incoming degree zero becomes the starting point of the topological Sort (in the previous blog)

Step 3: Process the queue and we will take a count variable which will keep track of how many vertices have been processed

Now we will process vertex 4 processing here means we will remove the vertex 4 along with its edges and update the incoming degree array

Since we have processed on vertex i.e. 4 count is incremented to 1.And the pop element is stored in the answer vector that form topological sort order

Result=[4]

Now we will process 5 as it’s in the front of the queue

When we will process vertex 5. Vertex 5 and its corresponding edges will be removed.

Now we will update the incoming degree array as from the adjacency list we could clearly see that

The degree of vertex 0 and 3 will be decreased

Now as soon the vertex degree becomes zero we will move the vertex to the queue so 3 is moved to the queue since 5 is now been processed it is removed from the queue and stored in the answer vector and count is incremented to 2.

Result=[4,5]

Now we will process node 3.We we remove vertex 3 with it’s edges as we can clearly see from the adjacency list that the incoming degree of vertex 0 and 2 will be decrease. So now we will update the incoming degree array

And vertex 3 is now been processed so it’s removed from the queue count value is incremented to 3 and 0 and 2 with incoming degree 0 are pushed into the queue

Result=[4,5,3]

Now we will process vertex 0 when vertex zero is removed along with its edges there will not be any updation in the incoming degree array. As we can clearly see in the adjacency list no vertex depends on node 0.So we will simply remove it from the queue add it in the result vector and update the value of count to 4

Result=[4,5,3,0]

Now we will process vertex 2.Vertex 1 has a incoming edge from vertex 2 .So the incoming degree of vertex 1 will be decreased when we remove vertex 2 along with it’s edges

Now vertex 1 is moved to the queue as it’s incoming degree becomes 0 and vertex 2 is removed ,count is incremented to 5 and 2 is added to result vector.

Result=[4,5,3,0,2]

Now we will process vertex 1 when vertex zero is removed along with it’s edges there will not be any updation in the incoming degree array. As no vertex has an incoming edge from vertex 1.So we will simply remove it from the queue add it in the result vector and update the value of count to 6.

Result=[4,5,3,0,2,1]

Now our queue is empty we come out of the DFS call.This is the required topological sort order

Result=[4,5,3,0,2,1]

Now let’s see why we have used the variable count?

If count!=no of vertices in the graph then the graph is not a DAG and it’s topological sort cannot be found

Let’s understand it with a small example.

Applying the above algorithm 0 is pushed into the queue and will be processed

Vertex 0 along with it’s corresponding edges are removed and pushed onto the resultant vector and adjacency list will be updated and count is incremented to 1

Result=[0]

Count=1

Now we can clearly see that there is no vertex in the incoming degree array whose incoming degree is zero.

Since queue is empty it will come out of the BFS call and we could clearly see that the

Count< no of vertices

So the graph contains a cycle so it is not a DAG and we cannot find topological sort for this graph

Time Complexity: O (V+E)

1. Filling the incoming degree array: O (V+E)

2. Filling the Queue: O (V)

3. Processing vertex in the Queue: O (V+E)

Comparison between Kahn’s Algorithm and DFS+Stack approach

1. Both are using extra space in DFS+Stack approach we are using Stack and in Kahn’s algorithm we are using an incoming degree array

2. We can find the cycle in the graph using Kahn’s algorithm

Code link

For DFS+Stack approach for topological sort

Refer to this blog link