Topological sort | Practice Medium 0 attempts
GeeksforGeeks ↗

Topological sort | Practice

Medium GraphBFSDFS GeeksforGeeks

Given a DAG with V vertices, return a topological ordering.

Example: V=4, edges=[[3,0],[1,0],[2,0]] → [3,2,1,0] or equivalent

Sample Input
—
Sample Output
—
Constraints
  • 2 <= V <= 10^4
  • 1 <= E <= V*(V-1)/2
Topics
GraphBFSDFS

Kahn's Algorithm (BFS)

function topologicalSort(V, adj) {
  const inDeg = Array(V).fill(0);
  for (let u=0;u<V;u++) for (const v of adj[u]) inDeg[v]++;
  const q = [], result = [];
  for (let i=0;i<V;i++) if (inDeg[i]===0) q.push(i);
  while (q.length) {
    const u = q.shift(); result.push(u);
    for (const v of adj[u]) if (--inDeg[v]===0) q.push(v);
  }
  return result;
}

Time: O(V + E) | Space: O(V)

Saved in this browser only. Private to you.

JavaScript