Kahn’s algorithm for Topological Sorting

Topological sorting is basically a linear ordering of the vertices in a Directed Acyclic Graph (DAG), where each vertex is ordered in such a way that the next vertex is dependent on the previous vertices/vertex.

A practical usage of Topological sorting is in the Package Managers such as npm. Most of the libraries, we use in the web/app development projects are dependent of any other external library/libraries which further is dependent on any other library/libraries.

This makes a chain of their dependency, and the library which is the dependency for other libraries needs to be installed first in order for the later to work.

That might have been a complex example, so let’s look it in terms of a Directed Acyclic Graph.

Let us built an array with the explanation:

Initially, vertex-5 and vertex-4 will be added to the array as they have no other dependency, i.e., their indegree is 0.

[5, 4]

Vertex-2 can now be added to the array as is was dependent on vertex-5 which had already been completed (i.e., already added to the array).

[5, 4, 2]

Vertex-3 can now be added to the array as is was dependent on vertex-2 which had already been completed (i.e., already added to the array).

[5, 4, 2, 3]

Vertex-1 can now be added to the array as is was dependent on vertex-3 and vertex-4 which had already been completed (i.e., already added to the array).

[5, 4, 2, 3, 1]

Vertex-0 can now be added to the array as is was dependent on vertex-4 and vertex-5 which had already been completed (i.e., already added to the array).

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

We might notice that 5 and 4 were already completed, so why haven't we added 0 after 5 and 4, as vertex-0 was dependent on 5 and 4 only.

This concludes that, we can have multiple correct answers for the topological sorting order as long as they follow the conditions discussed above.

Thus, another answer to the above graph could be [4, 5, 2, 0, 3, 1].

One approach to tackle this problem is to use the DFS (Depth First Traversal) while maintaining a Stack during the recursions.

The Kahn’s Algorithm is based on the BFS (Breadth First Traversal) of the Graph.

The Kahn’s Algorithm works in the following way:

a. Store indegree of every vertex

b. Create a Queue, q.

c. Add all 0 indegree vertices to the Queue q.

d. while q is not empty

{

1. u = q.pop()

2. Print u

3. For every adjacent v of u

• Reduce indegree of v by 1
• If indegree of v becomes 0, add v to the q.

}

How to find the in-degree of each node? 

There are 2 ways to calculate in-degree of every vertex: 
 

1. Take an in-degree array which will keep track of indegrees.
   Traverse the adjacency list and simply increase the counter of the destination node by 1. 
    

for each node in Adjacency List
    indegree[node] = 0;
for each edge(src, dest) in Edges
    indegree[dest]++

1. Time Complexity: O(V+E)
2. Traverse the list for every node and then increment the in-degree of all the nodes connected to it by 1. 
    

    for each node in Nodes
        If (list[node].size()!=0) then
        for each dest in list
            indegree[dest]++;

1. Time Complexity: The outer for loop will be executed V number of times and the inner for loop will be executed E number of times, Thus overall time complexity is O(V+E).
   The overall time complexity of the algorithm is O(V+E)

Below is the implementation of the above algorithm. The implementation uses method 2 discussed above for finding in degrees. 

Implementation:

---

In Java:

// A Java program to print topological
// sorting of a graph using indegrees
import java.util.*;

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

	// An Array of List which contains
	// references to the Adjacency List of
	// each vertex
	List<Integer> adj[];
	// Constructor
	public Graph(int V)
	{
		this.V = V;
		adj = new ArrayList[V];
		for (int i = 0; i < V; i++)
			adj[i] = new ArrayList<Integer>();
	}

	// Function to add an edge to graph
	public void addEdge(int u, int v)
	{
		adj[u].add(v);
	}
	// prints a Topological Sort of the
	// complete graph
	public void topologicalSort()
	{
		// Create a array to store
		// indegrees of all
		// vertices. Initialize all
		// indegrees as 0.
		int indegree[] = new int[V];

		// Traverse adjacency lists
		// to fill indegrees of
		// vertices. This step takes
		// O(V+E) time
		for (int i = 0; i < V; i++) {
			ArrayList<Integer> temp
				= (ArrayList<Integer>)adj[i];
			for (int node : temp) {
				indegree[node]++;
			}
		}

		// Create a queue and enqueue
		// all vertices with indegree 0
		Queue<Integer> q
			= new LinkedList<Integer>();
		for (int i = 0; i < V; i++) {
			if (indegree[i] == 0)
				q.add(i);
		}

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

		// Create a vector to store result
		// (A topological ordering of the vertices)
		Vector<Integer> topOrder = new Vector<Integer>();
		while (!q.isEmpty()) {
			// Extract front of queue
			// (or perform dequeue)
			// and add it to topological order
			int u = q.poll();
			topOrder.add(u);

			// Iterate through all its
			// neighbouring nodes
			// of dequeued node u and
			// decrease their in-degree
			// by 1
			for (int node : adj[u]) {
				// If in-degree becomes zero,
				// add it to queue
				if (--indegree[node] == 0)
					q.add(node);
			}
			cnt++;
		}

		// Check if there was a cycle
		if (cnt != V) {
			System.out.println(
				"There exists a cycle in the graph");
			return;
		}

		// Print topological order
		for (int i : topOrder) {
			System.out.print(i + " ");
		}
	}
}
// Driver program to test above functions
class Main {
	public static void main(String args[])
	{
		// Create a graph given in the above diagram
		Graph g = new Graph(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);
		System.out.println(
			"Following is a Topological Sort");
		g.topologicalSort();
	}
}

Output

Following is a Topological Sort of
4 5 2 0 3 1 

---

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;

public:
	// 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)
{
	adj[u].push_back(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++)
			in_degree[*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)
			q.push(i);

	// 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();
		q.pop();
		top_order.push_back(u);

		// 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)
				q.push(*itr);

		cnt++;
	}

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

	// 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";
	g.topologicalSort();

	return 0;
}

Output

Following is a Topological Sort of
4 5 2 0 3 1 

---

Complexity Analysis: 

• Time Complexity: O(V+E). 
  The outer for loop will be executed V number of times and the inner for loop will be executed E number of times.
• Auxiliary Space: O(V+E). 
  The queue needs to store all the vertices of the graph and an array is needed for storing indegrees. So the space required is O(V+E)

Reference: Kahn’s algorithm for Topological Sorting

Read Next: Bellman Ford Algorithm