Back to home
Logicmojo - Updated Sept 18, 2021

One of the difficulties in dealing with directed acyclic graphs (DAGs) is that they can look complicated and messy. This makes it difficult to see the relationships that vertices have with each other.

In this article, we’re going to discuss and learn how to rearrange the vertices of DAGs in such a way that will allow us to simplify these graphs and see possible patterns much easier.

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge u v, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.

First remember that this algorithm only makes sense for directed graphs since it assumes a scheduling/ordering of the nodes (eg: direction of the edges).

You could technically use that same piece of code to traverse an undirected graph but it wouldn’t mean anything particular it's just a post order traversal


1. The algorithm of the topological sort goes like this:

2. Identify the node that has no in-degree(no incoming edges) and select that node as the source node of the graph

3. Delete the source node with zero in-degree and also delete all its outgoing edges from the graph. Insert the deleted vertex in the result array.

4. Update the in-degree of the adjacent nodes after deleting the outgoing edges

5. Repeat step 1 to step 3 until the graph is empty

Implementation in Python

def topological_sort(digraph):
    # digraph is a dictionary:
    #   key: a node
    # value: a set of adjacent neighboring nodes

    # construct a dictionary mapping nodes to their
    # indegrees
    indegrees = {node : 0 for node in digraph}
    for node in digraph:
        for neighbor in digraph[node]:
            indegrees[neighbor] += 1

    # track nodes with no incoming edges
    nodes_with_no_incoming_edges = []
    for node in digraph:
        if indegrees[node] == 0:

    # initially, no nodes in our ordering
    topological_ordering = [] 
    # as long as there are nodes with no incoming edges
    # that can be added to the ordering 
    while len(nodes_with_no_incoming_edges) > 0:

        # add one of those nodes to the ordering
        node = nodes_with_no_incoming_edges.pop()
        # decrement the indegree of that node's neighbors
        for neighbor in digraph[node]:
            indegrees[neighbor] -= 1
            if indegrees[neighbor] == 0:

    # we've run out of nodes with no incoming edges
    # did we add all the nodes or find a cycle?
    if len(topological_ordering) == len(digraph):
        return topological_ordering  # got them all
        raise Exception("Graph has a cycle! No topological ordering exists.")

Implementation in C++

// A C++ program to print topological
// sorting of a graph using indegrees.
#include <bits/stdc++.h>
using namespace std;

// Class to represent a graph
class Graph {
	// No. of vertices'
	int V;

	// Pointer to an array containing
	// adjacency listsList
	list<int>* adj;

	// Constructor
	Graph(int V);

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

	// prints a Topological Sort of
	// the complete graph
	void topologicalSort();

Graph::Graph(int V)
	this->V = V;
	adj = new list<int>[V];

void Graph::addEdge(int u, int v)

// The function to do
// Topological Sort.
void Graph::topologicalSort()
	// Create a vector to store
	// indegrees of all
	// vertices. Initialize all
	// indegrees as 0.
	vector<int> in_degree(V, 0);

	// Traverse adjacency lists
	// to fill indegrees of
	// vertices. This step
	// takes O(V+E) time
	for (int u = 0; u < V; u++) {
		list<int>::iterator itr;
		for (itr = adj[u].begin();
			itr != adj[u].end(); itr++)

	// Create an queue and enqueue
	// all vertices with indegree 0
	queue<int> q;
	for (int i = 0; i < V; i++)
		if (in_degree[i] == 0)

	// Initialize count of visited vertices
	int cnt = 0;

	// Create a vector to store
	// result (A topological
	// ordering of the vertices)
	vector<int> top_order;

	// One by one dequeue vertices
	// from queue and enqueue
	// adjacents if indegree of
	// adjacent becomes 0
	while (!q.empty()) {
		// Extract front of queue
		// (or perform dequeue)
		// and add it to topological order
		int u = q.front();

		// Iterate through all its
		// neighbouring nodes
		// of dequeued node u and
		// decrease their in-degree
		// by 1
		list<int>::iterator itr;
		for (itr = adj[u].begin();
			itr != adj[u].end(); itr++)

			// If in-degree becomes zero,
			// add it to queue
			if (--in_degree[*itr] == 0)


	// Check if there was a cycle
	if (cnt != V) {
		cout << "There exists a cycle in the graph\n";

	// Print topological order
	for (int i = 0; i < top_order.size(); i++)
		cout << top_order[i] << " ";
	cout << endl;

// Driver program to test above functions
int main()
	// Create a graph given in the
	// above diagram
	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 << "Following is a Topological Sort of\n";

	return 0;

Time & Space Complexity Analysis

Breaking the algorithm into chunks, we:

Determine the indegree for each node. This is O(M) time (where M is the number of edges), since this involves looking at each directed edge in the graph once.

Find nodes with no incoming edges. This is a simple loop through all the nodes with some number of constant-time appends. O(N) time (where N is the number of nodes). Add nodes until we run out of nodes with no incoming edges. This loop could run once for every nodeβ€”O(N) times. In the body, we:
Do two constant-time operations on a vector to add a node to the topological ordering.
Decrement the indegree for each neighbor of the node we added. Over the entire algorithm, we'll end up doing exactly one decrement for each edge, making this step O(M) time overall.

All together, the time complexity is O(M+N).

All in all, we have three structures and they're all O(N) space. Overall space complexity: O(N).

πŸ’‘ Follow up: Try to do it using DFS

With this article at Logicmojo, you must have the complete idea of analyzing Topolgical Sort algorithm.

Good Luck & Happy Learning!!