Topological Sort (Kahn’s Algorithm & DFS)

1// Kahn's Algorithm (BFS-based Topological Sort)
2function topologicalSort(numCourses, prerequisites) {
3  const inDegree = new Array(numCourses).fill(0);
4  const adj = Array.from({ length: numCourses }, () => []);
5 
6  // Build adjacency list & count in-degrees
7  for (const [u, v] of prerequisites) {
8    adj[v].push(u); // edge v -> u (v is prerequisite for u)
9    inDegree[u]++;
10  }
11 
12  const queue = [];
13  for (let i = 0; i < numCourses; i++) {
14    if (inDegree[i] === 0) queue.push(i);
15  }
16 
17  const result = [];
18  while (queue.length > 0) {
19    const node = queue.shift();
20    result.push(node);
21 
22    for (const neighbor of adj[node]) {
23      inDegree[neighbor]--;
24      if (inDegree[neighbor] === 0) {
25        queue.push(neighbor);
26      }
27    }
28  }
29 
30  // If result length !== numCourses, cycle exists!
31  return result.length === numCourses ? result : [];
32}