Topological Sort

Topological sorting for any graph is possible if it is a DAG

Directed Acyclic Graph (DAG)

A directed graph with no cycle is called DAG

Topological Sort is the linear ordering of the vertices such that for every directed edge UV(U->V) vertex U comes before V in the ordering.

Let’s look at this graph and find the topological sort for this:

Step 1: First find the vertex with 0 degree means no incoming edge

So we can start with vertex 4 or 5 .So let’s start with vertex 5

Result= [5]

Since we have one more vertex with degree 0 i.e. 4 we add it in the result list

Result=[5,4]

Step 2: Now eliminate 5 and 4 with their edges and again calculate the degree of each vertex.

Now we will select 0 vertex because it has a degree 0 and it in the resultant list

Result= [5, 4, 0]

Similarly we will delete the vertex 0 with its corresponding edges

Now we can select 3 and 2

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

We repeat the above steps and delete 2 and 3 and eliminate the edge corresponding to vertex 3 then we are only left with vertex 1 we add it into the array

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

There are many topological sort orders possible for the above example like

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

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

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

And more..

Implementation

DFS+Stack

We will take a stack and a visited array that is initially false for each vertex as none of the vertices have now been visited.

Algorithm:

We start from a vertex and go till the Nth vertex in the graph.

If the vertex have already been visited that means it is true in the visited array we proceed to the next vertex and if it is not been visited we explore it vertex using DFS

Let’s dry run this algorithm for the above example.

1. We start from the vertex 0 .Now we have 2 options we can go to vertex 2 or vertex 3.Let’s go to vertex 2.

2. Now vertex 2 doesn’t have any outgoing edge so now we have to backtrack to vertex 0.Vertex 0 and 2 are marked as visited in the array. Before backtracking 2 is pushed into the stack

We will backtrack and go to vertex 3.Since according to the algorithm the value of the visited array for vertex 3 is false we can traverse to node 3

Now from vertex 3 we make a call to vertex 1 since this vertex is also not visited

Now from vertex 1 there is no outgoing edge so we have to backtrack before backtracking we push 1 onto the stack

Now we backtrack from vertex 1 to vertex 3 since all the outgoing edges from vertex 3 have also been traversed we backtrack to vertex 1 .Before backtracking from vertex 3 we have to push vertex 3 onto the stack

So now when we reach to vertex 0 all its outgoing edges have now been traversed we have to backtrack from vertex 0 so before backtracking we have to push 0 onto over stack

Now we will traverse for i=1 in this algorithm

So now for i=4 visited[4]=false

Now we are on vertex 4 and mark it has true in the visited array

Vertex 4 has 2 outgoing edges to vertex 2 and vertex 1 but both are visited so we have to backtrack from the vertex 4.Before backtracking from the vertex we have to push it onto the stack

Now we will go to vertex 5 and mark it as visited in the array

Now for vertex 5 it’s all outgoing edges have already been traversed. So we have to backtrack from vertex 5 .So before backtracking from vertex 5 we have to move vertex 5 onto the stack

Once all the vertices have been traversed we will just pop it and give it as our answer

RESULT:[5,4,0,3,1,2]

Time Complexity: O(V+E)

As we are processing each vertex only once.

Applications:

1. Used in scheduling a sequence of Jobs

Code link

For BFS+Queue approach for topological sort i.e. Kahn’s Algorithm

Refer to this blog link