Topological sort or Kahn's algorithm

Intuition:

The topological sorting of a directed acyclic graph is nothing but the linear ordering of vertices such that if there is an edge between node u and v(u -> v), node u appears before v in that ordering.

Why does topological sort only exist in DAG?

If the edges are undirected: An undirected edge between node u and v signifies an edge from u to v (u->v) as well as from v to u (v->u) making it practically impossible to write such orderings where u appears before v and v appears before u simultaneously.
If the directed graph contains a cycle: There is no linear ordering possible for nodes in cycles, making it impossible for topological sorting to exist.

Understanding:

Depth-first search (DFS) is a natural fit for this problem because it allows us to explore each path of the graph deeply before backtracking, ensuring that all dependencies of a node are processed before the node itself.

During the DFS traversal, when a node is fully processed (i.e., all nodes it points to are visited), we push it onto a stack.
This stack helps us reverse the order of processing, as nodes deeper in the graph (dependent nodes) are pushed onto the stack first. When we later pop from the stack, we get the nodes in the correct topological order.

Approach:

Prepare a list to store the topological order. Initialize a stack to keep track of the nodes in reverse order of their processing. Create a visited array to track which nodes have been visited.
Define a recursive DFS function that marks the current node as visited. For each neighbor of the current node, if it is not visited, recursively perform DFS on it. After all neighbors are processed, push the current node onto the stack.
Traverse all nodes in the graph. For each unvisited node, initiate a DFS traversal.
Once DFS is complete for all nodes, pop elements from the stack one by one and add them to the topological order list.

Dry Run:

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:

    // Function to perform DFS traversal
    void dfs(int node, vector<int> adj[], 
            vector<int> &vis, 
            stack <int> &st) {
                
        // Mark the node as visited
        vis[node] = 1;
        
        // Traverse all the neighbors
        for(auto it : adj[node]) {
            
            // If not visited, recursively perform DFS.
            if(vis[it] == 0) dfs(it, adj, vis, st);
        }
        
        /* Add the current node to stack 
        once all the nodes connected to it 
        have been processed */
        st.push(node);
    }
    
public:

	/* Function to return list containing 
	vertices in Topological order */
	vector<int> topoSort(int V, vector<int> adj[]) 
	{
	    // To store the result
	    vector <int> ans;
	    
	    /* Stack to store processed 
	    nodes in reverse order */
	    stack <int> st;
	    
	    // Visited array
	    vector<int> vis(V, 0);
	    
	    // Traverse the graph
	    for(int i=0; i<V; i++) {
	        
	        // Start DFS traversal for unvisited node
	        if(!vis[i]) {
	            dfs(i, adj, vis, st);
	        }
	    }
	    
	    // Until the stack is empty
	    while(!st.empty()) {
	        
	        // Add the top of stack to result
	        ans.push_back(st.top());
	        
	        // Pop the top node
	        st.pop();
	    }
	    
	    // Return the result
        return ans;
	}
};

int main() {
    
    int V = 6;
    vector<int> adj[V] = {
         {}, 
         {}, 
         {3}, 
         {1}, 
         {0,1}, 
         {0,2}
    };
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to return the 
    topological sorting of given graph */
    vector<int> ans = sol.topoSort(V, adj);
    
    // Output
    cout << "The topological sorting of the given graph is: \n";
    for(int i=0; i < V; i++) {
        cout << ans[i] << " ";
    }
    
    return 0;
}
import java.util.*;

class Solution {
    
    // Function to perform DFS traversal
    private void dfs(int node, List<Integer> adj[], 
                     int[] vis, Stack<Integer> st) {
        // Mark the node as visited
        vis[node] = 1;
        
        // Traverse all the neighbors
        for (int it : adj[node]) {
            // If not visited, recursively perform DFS.
            if (vis[it] == 0) {
                dfs(it, adj, vis, st);
            }
        }
        
        /* Add the current node to stack 
        once all the nodes connected to it 
        have been processed */
        st.push(node);
    }

    /* Function to return array containing 
    vertices in Topological order */
    public int[] topoSort(int V, List<Integer> adj[]) {
        // To store the result
        int[] ans = new int[V];
        
        /* Stack to store processed 
        nodes in reverse order */
        Stack<Integer> st = new Stack<>();
        
        // Visited array
        int[] vis = new int[V];
        
        // Traverse the graph
        for (int i = 0; i < V; i++) {
            // Start DFS traversal for unvisited node
            if (vis[i] == 0) {
                dfs(i, adj, vis, st);
            }
        }
        
        // Until the stack is empty
        for (int i = 0; i < V; i++) {
            // Add the top of stack to result
            ans[i] = st.pop();
        }
        
        // Return the result
        return ans;
    }
}

class Main {
    public static void main(String[] args) {
        int V = 6;
        List<Integer> adj[] = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
        adj[2].add(3);
        adj[3].add(1);
        adj[4].add(0);
        adj[4].add(1);
        adj[5].add(0);
        adj[5].add(2);
        
        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution(); 
        
        /* Function call to return the 
        topological sorting of given graph */
        int[] ans = sol.topoSort(V, adj);
        
        // Output
        System.out.println("The topological sorting of the given graph is:");
        for (int i = 0; i < V; i++) {
            System.out.print(ans[i] + " ");
        }
    }
}
class Solution:
    # Function to perform DFS traversal
    def dfs(self, node, adj, vis, st):
        # Mark the node as visited
        vis[node] = 1
        
        # Traverse all the neighbors
        for it in adj[node]:
            
            # If not visited, recursively perform DFS.
            if vis[it] == 0:
                self.dfs(it, adj, vis, st)
        
        # Add the current node to stack 
        # once all the nodes connected to it 
        # have been processed
        st.append(node)
    
    # Function to return list containing 
    # vertices in Topological order
    def topoSort(self, V, adj):
        # To store the result
        ans = []
        
        # Stack to store processed 
        # nodes in reverse order
        st = []
        
        # Visited array
        vis = [0] * V
        
        # Traverse the graph
        for i in range(V):
            
            # Start DFS traversal for unvisited node
            if vis[i] == 0:
                self.dfs(i, adj, vis, st)
        
        # Until the stack is empty
        while st:
            
            # Add the top of stack to result
            ans.append(st.pop())
        
        # Return the result
        return ans

if __name__ == "__main__":
    
    V = 6
    adj = [
        [], 
        [], 
        [3], 
        [1], 
        [0, 1], 
        [0, 2]
    ]
    
    # Creating an instance of 
    # Solution class
    sol = Solution()
    
    # Function call to return the 
    # topological sorting of given graph
    ans = sol.topoSort(V, adj)
    
    # Output
    print("The topological sorting of the given graph is:")
    for i in range(V):
        print(ans[i], end=" ")
class Solution {
    // Function to perform DFS traversal
    dfs(node, adj, vis, st) {
        // Mark the node as visited
        vis[node] = 1;
        
        // Traverse all the neighbors
        for (let it of adj[node]) {
            
            // If not visited, recursively perform DFS.
            if (vis[it] === 0) this.dfs(it, adj, vis, st);
        }
        
        // Add the current node to stack 
        // once all the nodes connected to it 
        // have been processed
        st.push(node);
    }

    // Function to return list containing 
    // vertices in Topological order
    topoSort(V, adj) {
        // To store the result
        let ans = [];
        
        // Stack to store processed 
        // nodes in reverse order
        let st = [];
        
        // Visited array
        let vis = new Array(V).fill(0);
        
        // Traverse the graph
        for (let i = 0; i < V; i++) {
            
            // Start DFS traversal for unvisited node
            if (vis[i] === 0) {
                this.dfs(i, adj, vis, st);
            }
        }
        
        // Until the stack is empty
        while (st.length > 0) {
            
            // Add the top of stack to result
            ans.push(st.pop());
        }
        
        // Return the result
        return ans;
    }
}

// Main function to test the code
const main = () => {
    
    const V = 6;
    const adj = [
        [], 
        [], 
        [3], 
        [1], 
        [0, 1], 
        [0, 2]
    ];
    
    // Creating an instance of 
    // Solution class
    const sol = new Solution();
    
    // Function call to return the 
    // topological sorting of given graph
    const ans = sol.topoSort(V, adj);
    
    // Output
    console.log("The topological sorting of the given graph is:");
    for (let i = 0; i < V; i++) {
        console.log(ans[i] + " ");
    }
};

// Call the main function
main();

Complexity Analysis:

Time Complexity: O(V+E) (where V and E represent the number of nodes and edges in the graph)
A simple DFS traversal takes O(V+E) time.

Space Complexity: O(V)
The stack will store at most V nodes taking O(V) space and the array to store the topological sort takes O(V) space.

Intuition:

Why does topological sort only exist in DAG?

If the edges are undirected: An undirected edge between node u and v signifies an edge from u to v (u->v) as well as from v to u (v->u) making it practically impossible to write such orderings where u appears before v and v appears before u simultaneously.
If the directed graph contains a cycle: There is no linear ordering possible for nodes in cycles, making it impossible for topological sorting to exist.

To solve the problem using BFS traversal, Kahn's algorithm can be used.

Kahn's Algorithm:

The algorithm suggests that there will always be at least one node having in-degree as zero, which means all such nodes can be put before any other node in the ordering as there is no node pointing to any of these nodes.

After such nodes are added to the ordering, the edges from these nodes can be removed, updating the in-degree of other nodes and exposing more nodes having an in-degree of zero. This process can be repeated till there are nodes left in the graph to get the required linear ordering.

Approach:

Prepare a list to store the topological order. Create an array to track the in-degree (number of incoming edges) of each node. Traverse each node and update the in-degree of its neighbors based on the adjacency list representation of the graph.
Initialize a queue and add all nodes with zero in-degree to it. These nodes have no dependencies and can be processed first.
Use a loop to process nodes from the queue until it is empty:
- Remove a node from the front of the queue and add it to the topological order list.
- For each neighbor of the removed node, reduce its in-degree by one.
- If a neighbor's in-degree becomes zero, all its parent nodes are processed so add it to the queue.
After processing all nodes, the topological order list will contain a valid topological sorting of the graph.

Dry Run:

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to return the topological
     sorting of given graph */
    vector<int> topoSort(int V, vector<int> adj[]) {
        
        // To store the result
        vector<int> ans;
        
        // To store the In-degrees of nodes
	    vector<int> inDegree(V, 0);
	    
	    // Calculating the In-degree of the given graph
	    for(int i=0; i<V; i++) {
	        for(auto it : adj[i]) inDegree[it]++;
	    }
	    
	    // Queue to facilitate BFS
	    queue<int> q;
	    
	    // Add the nodes with no in-degree to queue
	    for(int i=0; i<V; i++) {
	        if(inDegree[i] == 0) q.push(i);
	    }
	    
	    // Until the queue is empty
	    while(!q.empty()) {
	        
	        // Get the node
	        int node = q.front();
	        
	        // Add it to the answer
	        ans.push_back(node);
	        q.pop();
	        
	        // Traverse the neighbours
	        for(auto it : adj[node]) {
	            
	            // Decrement the in-degree
	            inDegree[it]--;
	            
	            /* Add the node to queue if 
	            its in-degree becomes zero */
	            if(inDegree[it] == 0) q.push(it);
	        }
	    }
	    
	    // Return the result
	    return ans;
    }
};

int main() {
    
    int V = 6;
    vector<int> adj[V] = {
         {}, 
         {}, 
         {3}, 
         {1}, 
         {0,1}, 
         {0,2}
    };
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to return the 
    topological sorting of given graph */
    vector<int> ans = sol.topoSort(V, adj);
    
    // Output
    cout << "The topological sorting of the given graph is: \n";
    for(int i=0; i < V; i++) {
        cout << ans[i] << " ";
    }
    
    return 0;
}
import java.util.*;

class Solution {
    /* Function to return the topological
     sorting of given graph */
    public int[] topoSort(int V, List<Integer> adj[]) {
        // To store the result
        int[] ans = new int[V];

        // To store the In-degrees of nodes
        int[] inDegree = new int[V];

        // Calculating the In-degree of the given graph
        for (int i = 0; i < V; i++) {
            for (int it : adj[i]) inDegree[it]++;
        }

        // Queue to facilitate BFS
        Queue<Integer> q = new LinkedList<>();

        // Add the nodes with no in-degree to queue
        for (int i = 0; i < V; i++) {
            if (inDegree[i] == 0) q.add(i);
        }

        int index = 0; // Index to store elements in ans array

        // Until the queue is empty
        while (!q.isEmpty()) {
            // Get the node
            int node = q.poll();

            // Add it to the answer
            ans[index++] = node;

            // Traverse the neighbours
            for (int it : adj[node]) {
                // Decrement the in-degree
                inDegree[it]--;

                /* Add the node to queue if 
                its in-degree becomes zero */
                if (inDegree[it] == 0) q.add(it);
            }
        }

        // Return the result
        return ans;
    }
}

class Main {
    public static void main(String[] args) {
        int V = 6;
        List<Integer> adj[] = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
        adj[2].add(3);
        adj[3].add(1);
        adj[4].add(0);
        adj[4].add(1);
        adj[5].add(0);
        adj[5].add(2);

        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution(); 

        /* Function call to return the 
        topological sorting of given graph */
        int[] ans = sol.topoSort(V, adj);

        // Output
        System.out.println("The topological sorting of the given graph is:");
        for (int i = 0; i < V; i++) {
            System.out.print(ans[i] + " ");
        }
    }
}
from collections import deque

class Solution:
    # Function to return the topological
    # sorting of given graph
    def topoSort(self, V, adj):
        
        # To store the result
        ans = []
        
        # To store the In-degrees of nodes
        inDegree = [0] * V
        
        # Calculating the In-degree of the given graph
        for i in range(V):
            for it in adj[i]:
                inDegree[it] += 1
        
        # Queue to facilitate BFS
        q = deque()
        
        # Add the nodes with no in-degree to queue
        for i in range(V):
            if inDegree[i] == 0:
                q.append(i)
        
        # Until the queue is empty
        while q:
            
            # Get the node
            node = q.popleft()
            
            # Add it to the answer
            ans.append(node)
            
            # Traverse the neighbours
            for it in adj[node]:
                
                # Decrement the in-degree
                inDegree[it] -= 1
                
                # Add the node to queue if 
                # its in-degree becomes zero
                if inDegree[it] == 0:
                    q.append(it)
        
        # Return the result
        return ans

if __name__ == "__main__":
    
    V = 6
    adj = [
        [], 
        [], 
        [3], 
        [1], 
        [0,1], 
        [0,2]
    ]
    
    # Creating an instance of 
    # Solution class
    sol = Solution()
    
    # Function call to return the 
    # topological sorting of given graph
    ans = sol.topoSort(V, adj)
    
    # Output
    print("The topological sorting of the given graph is:")
    for i in range(V):
        print(ans[i], end=" ")
class Solution {
    /* Function to return the topological
     sorting of given graph */
    topoSort(V, adj) {
        
        // To store the result
        let ans = [];
        
        // To store the In-degrees of nodes
        let inDegree = new Array(V).fill(0);
        
        // Calculating the In-degree of the given graph
        for (let i = 0; i < V; i++) {
            for (let it of adj[i]) inDegree[it]++;
        }
        
        // Queue to facilitate BFS
        let q = [];
        
        // Add the nodes with no in-degree to queue
        for (let i = 0; i < V; i++) {
            if (inDegree[i] === 0) q.push(i);
        }
        
        // Until the queue is empty
        while (q.length > 0) {
            
            // Get the node
            let node = q.shift();
            
            // Add it to the answer
            ans.push(node);
            
            // Traverse the neighbours
            for (let it of adj[node]) {
                
                // Decrement the in-degree
                inDegree[it]--;
                
                /* Add the node to queue if 
                its in-degree becomes zero */
                if (inDegree[it] === 0) q.push(it);
            }
        }
        
        // Return the result
        return ans;
    }
}

// Main function to test the code
const main = () => {
    
    const V = 6;
    const adj = [
        [], 
        [], 
        [3], 
        [1], 
        [0, 1], 
        [0, 2]
    ];
    
    /* Creating an instance of 
    Solution class */
    const sol = new Solution();
    
    /* Function call to return the 
    topological sorting of given graph */
    const ans = sol.topoSort(V, adj);
    
    // Output
    console.log("The topological sorting of the given graph is:");
    for (let i = 0; i < V; i++) {
        console.log(ans[i] + " ");
    }
};

// Call the main function
main();

Complexity Analysis:

Time Complexity: O(V+E) (where V and E represent the number of nodes and edges in the graph)
A simple BFS traversal takes O(V+E) time.

Space Complexity: O(V)
Array to store in-degrees require O(V) space and queue space will store O(V) nodes at maximum.

Problem List

Topological sort or Kahn's algorithm

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Why does topological sort only exist in DAG?

Understanding:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Intuition:

Why does topological sort only exist in DAG?

Kahn's Algorithm:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code

Facts