Topological sort - Kahn's Algorithm GFG

#leetcode #dsa/graphs

Question

Given a Directed Acyclic Graph (DAG) of V (0 to V-1) vertices and E edges represented as a 2D list of edges[][], where each entry edges[i] = [u, v] denotes a directed edge u -> v. Return the topological sort for the given graph.

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.

Note: As there are multiple Topological orders possible, you may return any of them. If your returned Topological sort is correct then the output will be true else false.

Examples:

Input: V = 4, E = 3, edges[][] = 3, 0], [1, 0], [2, 0

Output: true
Explanation: The output true denotes that the order is valid. Few valid Topological orders for the given graph are:
[3, 2, 1, 0]
[1, 2, 3, 0]
[2, 3, 1, 0]

Input: V = 6, E = 6, edges[][] = 1, 3], [2, 3], [4, 1], [4, 0], [5, 0], [5,2

Output: true
Explanation: The output true denotes that the order is valid. Few valid Topological orders for the graph are:
[4, 5, 0, 1, 2, 3]
[5, 2, 4, 0, 1, 3]

Constraints:
2  ≤  V  ≤  103
1  ≤  E = edges.size()  ≤  (V * (V - 1)) / 2

Try more examples

Approach 1: Kahn's Algorithm Optimal

Intuition

Algorithm

  1. Get adjacency list from edge list
  2. Declare & initialize vector<int> indegree with length of the nodes & zero
  3. Update the indegree by looping through the adjacency list
  4. Declare a queue<int> q
  5. Loop through the indegree array
    1. If the indegree of a node == 0 then push it into the queue
  6. Declare an vector<int> ans array
  7. While q is not empty
    1. Get the node at the front of the queue & pop it
    2. Push the node into the q
    3. Loop over the neighbors of the node
      1. Decrement the indegree by 1
      2. If the indegree == 0 then push it into the queue
  8. return ans.

Code

class Solution {
public:
    vector<vector<int>> getAdj(int V, vector<vector<int>>& edges) {
        vector<vector<int>> adj(V);
        for (auto edge : edges) {
            adj[edge[0]].push_back(edge[1]);
        }
        return adj;
    }

    vector<int> topoSort(int V, vector<vector<int>>& edges) {
        vector<vector<int>> adj = getAdj(V, edges);

        vector<int> indegree (V, 0);

        for (int i = 0 ; i < V ; i++) {
            for (int neighbor: adj[i]) {
                indegree[neighbor]++;   
            }
        }

        queue<int> q;

        for (int i = 0 ; i < V ; i++) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }

        vector<int> ans;

        while (!q.empty()) {
            int node = q.front();
            q.pop();
            ans.push_back(node);

            for (int neighbor: adj[node]) {
                indegree[neighbor]--;

                if (indegree[neighbor] == 0) {
                    q.push(neighbor);   
                }
            }

        }

        return ans;
    }
};

Complexity Analysis