Topological sort | Practice Medium 0 attempts
GeeksforGeeks ↗

Topological sort | Practice

Medium GraphBFSDFS GeeksforGeeks

Given a directed acyclic graph (DAG) with V vertices, produce an ordering of its vertices such that for every directed edge u → v, vertex u comes before vertex v in the ordering.

Input Format
Implement topologicalSort(V, adj). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement. Any result satisfying the statement is accepted.

Sample Input and Output

Example 1 · Run Sample

Input
V = 4
adj = [[],[0],[0],[0]]
Output
[1,2,3,0]

Example 2

Input
V = 1
adj = [[]]
Output
[0]
Constraints
  • 1 <= V <= 10^4
  • The adjacency list describes a directed acyclic graph on vertices 0 through V-1.
Test Cases (2)
Case 1
Args: [4,[[],[0],[0],[0]]] Expected: [1,2,3,0]
Case 2
Args: [1,[[]]] Expected: [0]
Topics
GraphBFSDFS

Kahn's Algorithm (BFS)

javascript
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);
  let head = 0;
  while (head < q.length) {
    const u = q[head++]; 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