Close Menu

    Subscribe to Updates

    Get the latest creative news from FooBar about art, design and business.

    What's Hot

    How to use hooks inside React Class Components

    November 29, 2023

    Experience at CNCF – Jaeger under the LFX Mentorship Program

    November 29, 2023

    Wrapping up the first month at CNCF – Jaeger under LFX Mentorship

    November 29, 2023
    Facebook X (Twitter) Instagram
    • Our Authors
    Facebook X (Twitter) Instagram Pinterest Vimeo
    HackTechHub
    • Homepage
      • Advisory Team
      • Charter for Advisory Team
    • Events
    • Coding
      • C++
      • Competitive Programming
        • Mathematics
      • Algorithms
        • Arrays
        • Linked List
        • Mathematical Algorithms
      • DSA
        • Array
        • Graphs
        • Hashing
        • Linked List
        • Recursion
        • Sorting Algorithms
        • String
        • Tree
    • Development
      • Web Development
        • Backend Development
        • Frontend Development
    • DevOps
      • Docker
      • Kubernetes
    • Security
      • Ethical Hacking
      • Authentication & Security
      • Networking
      • Linux
    • Finance
      • Cryptocurrency
      • Fiat
    Subscribe
    HackTechHub
    Home » Kahn’s algorithm for Topological Sorting
    Algorithms

    Kahn’s algorithm for Topological Sorting

    Ansh GoyalBy Ansh GoyalAugust 1, 2022Updated:November 29, 20232 Comments8 Mins Read
    Share Facebook Twitter Pinterest LinkedIn Tumblr Reddit Telegram Email
    Kahn's Algorithm for Topological Sorting
    Share
    Facebook Twitter LinkedIn Pinterest Email

    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

    Kahn's Algorithm Topological Sorting
    Share. Facebook Twitter Pinterest LinkedIn Tumblr Email
    Previous ArticleDeploying Node App with MongoDB to Heroku
    Next Article Circular Linked List
    Ansh Goyal
    • Website

    Related Posts

    Development

    How to use hooks inside React Class Components

    November 29, 2023
    C++

    Linked List Data Structure

    October 6, 2022
    C++

    Tower of Hanoi – Recursion Based Problem

    August 23, 2022
    View 2 Comments

    2 Comments

    1. Sadhana Sharma on August 1, 2022 2:59 pm

      Explicitly explained…

      Reply
      • Ansh Goyal on August 1, 2022 3:16 pm

        Thanks for the feedback 😊

        Reply

    Leave A Reply Cancel Reply

    Demo
    Top Posts

    Experience at CNCF – Jaeger under the LFX Mentorship Program

    November 29, 202312 Views

    Wrapping up the first month at CNCF – Jaeger under LFX Mentorship

    November 29, 202312 Views

    How to Implement SSO in a NodeJS App

    April 24, 20237 Views
    Stay In Touch
    • Facebook
    • YouTube
    • TikTok
    • WhatsApp
    • Twitter
    • Instagram
    Latest Reviews

    Subscribe to Updates

    Get the latest tech news from FooBar about tech, design and biz.

    Demo
    Most Popular

    Experience at CNCF – Jaeger under the LFX Mentorship Program

    November 29, 202312 Views

    Wrapping up the first month at CNCF – Jaeger under LFX Mentorship

    November 29, 202312 Views

    How to Implement SSO in a NodeJS App

    April 24, 20237 Views
    Our Picks

    How to use hooks inside React Class Components

    November 29, 2023

    Experience at CNCF – Jaeger under the LFX Mentorship Program

    November 29, 2023

    Wrapping up the first month at CNCF – Jaeger under LFX Mentorship

    November 29, 2023

    Subscribe to Updates

    Get the latest creative news from FooBar about art, design and business.

    Facebook X (Twitter) Instagram Pinterest
    • Our Authors
    © 2023 CodifyPlus. Designed by CodifyPlus | Ansh.

    Type above and press Enter to search. Press Esc to cancel.