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.

Algorithm

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 Bootcamp

Code

// C++ program for Topological Sort
#include<bits/stdc++.h>
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);
public:
// 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
adj[u].push_back(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])
{
if(!visited[child])
{
topoDFS(child,visited,Stack);
}
}
// push current node into the stack
Stack.push(v);
}
//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 << Stack.top() << " ";
Stack.pop();
}
}
// 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
g.topologicalSort();
return 0;
}

Output

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.

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.

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.

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.

What is an acyclic graph? If there is no cycle present in a graph, the graph is classified as an acyclic graph.

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.