Code360 powered by Coding Ninjas X Code360 powered by Coding Ninjas X
Table of contents
Complexity Analysis
Key Takeaways
Last Updated: Mar 27, 2024

Topological sort without Kahn’s algorithm

Author Malay Gain
0 upvote
Master Python: Predicting weather forecasts
Ashwin Goyal
Product Manager @


Topological sorting is a linear ordering of vertices of a directed acyclic graph. If there is an edge from vertex u to vertex v, u will appear before v in that ordering.


Let’s visualize this ordering through an example.




Topological sorting of the above graph is 15,14,12,13,11,10. But this is not the only one. There can be multiple such topological sorts of the same graph.



In this algorithm, we use DFS(depth-first search) for topological sort. But we implement it using a modified version of the standard DFS Algorithm. Instead of printing the node just after visiting, we store it in a temporary stack after visiting all of its adjacent nodes recursively.


  • Call the DFS for all of the nodes of the graph.


  • DFS will mark a node as visited and recursively call itself for its adjacent nodes and push them into a temporary stack. So, a node is pushed into the stack only after its adjacent nodes are pushed.


  • When there is no node left unvisited(i.e., all are visited), we will print the content of the stack in order after popping.


This ordering will be the required topological sort of the graph. As we push one node after its adjacent nodes are pushed, the node will appear before its adjacent nodes in that ordering.


Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job



// C++ program  for Topological Sort

using namespace std;

// Class to represent a graph
class Graph {
// no. of nodes
int n;

// pointer to an array containing adjacency list representation of the graph
vector<int>* adj;

//DFS used for Topological Sort
void topoDFS(int v, bool visited[],stack<int>& Stack);

// Constructor
Graph(int n);

// function to add an edge to the graph
void addEdge(int u, int v);

// function to Topological Sort
void topologicalSort();

Graph::Graph(int n)
this->n = n;
adj = new vector<int>[n]; //allocating memory for adjacency list

void Graph::addEdge(int u, int v)
// adding an edge from u to v

// DFS used by topologicalSort
void Graph::topoDFS(int v, bool visited[],stack<int>& Stack)
// mark the current node as visited.
visited[v] = true;

// recursively calls  itself for its adjacent nodes 
//and push them into a temporary stack

    for( auto child:adj[v])

// push current node into the stack


//actual function to print Topological Sort
void Graph::topologicalSort()
stack<int> Stack;

// mark all the vertices as not visited
bool* visited = new bool[n];
for (int i = 0; i < n; i++)
visited[i] = false;

//Call the DFS for all of the nodes of the graph if it is not visited
for (int i = 0; i < n; i++)
if (visited[i] == false)
topoDFS(i, visited, Stack);

// printing  contents of stack after popping
while (Stack.empty() == false) {
cout << << " ";

// Driver Code
int main()
// creating a graph with 6 nodes
Graph g(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);

cout << "Topological Sort of the given graph :\n";

// Function Call

return 0;


Topological Sort of the given graph :
5 4 2 3 1 0

Complexity Analysis

  • Time Complexity: In this algorithm, we have only used DFS. So,  its complexity is the same as DFS, O (n+e), where n is the number of vertices and e is the number of edges in the graph.


  • Space Complexity: Here, an extra stack of size n is used to maintain the topological ordering of the vertices, and in the worst-case Recursion, stack size can become n.So, space complexity is O(n)+O(n) i.e, O(n).


This video gives a detailed tutorial on the “Topological Sort Algorithm”, so you can watch this video to understand it better.

Refer to know about :  Topological sort


  1. What is Topological Sort?
    It is a linear ordering of vertices of a directed acyclic graph, such that if there is an edge from vertex u to vertex v, u will appear before v in that ordering.
  2. What is the application of Topological Sort?
    (i)Scheduling jobs according to given dependencies among the jobs.
    (ii)Resolving symbol and data serialization in linkers.
    (iii)Detecting cycle in a graph.
    (iv)Topological Sort detects deadlock in the operating system.
  3. What is the main difference between the above algorithm and Khan’s Algorithm?
    The main difference between the above algorithm and Khan’s Algorithm is for the above algorithm, we have used DFS(depth-first search), but  Khan’s Algorithm is implemented using the BFS(breadth-first search) algorithm.
  4. What is an acyclic graph?
    If there is no cycle present in a graph, the graph is classified as an acyclic graph.
  5. What is a directed graph?
    If directed edges connect vertices of a graph, the graph is said to be directed graph or digraph.


Key Takeaways

This article discussed the concept of Topological sort, implementation of  Topological sort on an acyclic directed graph. The blog also tried to provide a better understanding of the time complexity for such sorting on a graph.

Recommended Problems - 

To learn more, head over right now to Coding Ninjas Studio to practice important graph-related problems and crack your interviews like a Ninja!

Happy learning!

Previous article
01 Matrix
Next article
Stepping Numbers
Live masterclass