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


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


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




And more...



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.



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

If the vertex has 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


Time Complexity: O(V+E)

As we are processing each vertex only once.


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

Leave a Reply