More
    AlgorithmsKahn’s algorithm for Topological Sorting

    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.

    Topological Sorting Example
    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

    Sponsored

    Previous articlePointer in C++
    Next articleCircular Linked List

    2 COMMENTS

    LEAVE A REPLY

    Please enter your comment!
    Please enter your name here

    Subscribe Today

    GET EXCLUSIVE FULL ACCESS TO PREMIUM CONTENT

    Get unlimited access to our EXCLUSIVE Content and our archive of subscriber stories.

    Exclusive content

    Latest article

    More article