Q21: Course Schedule (Topological Sort / Cycle Detection)

Determine if you can finish all courses given prerequisite pairs using Topological Sort / Kahn's Algorithm (In-degree array + BFS).

Kahn's Algorithm BFS Topological Sort

function canFinish(numCourses, prerequisites) {
  const inDegree = new Array(numCourses).fill(0);
  const adjList = new Map();
  
  for (let [course, pre] of prerequisites) {
    if (!adjList.has(pre)) adjList.set(pre, []);
    adjList.get(pre).push(course);
    inDegree[course]++;
  }
  
  const queue = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }
  
  let processedCount = 0;
  while (queue.length > 0) {
    const current = queue.shift();
    processedCount++;
    
    const neighbors = adjList.get(current) || [];
    for (let neighbor of neighbors) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }
  return processedCount === numCourses;
}

console.log(canFinish(2, [[1, 0]])); // true

💡 Calculates in-degree counts for each node. Courses with 0 prerequisites enter the BFS queue. Decrements in-degrees of dependent courses as completed; returns true if all courses can be processed.

Key Takeaways

If a directed graph contains a cycle, topological sorting is impossible.
Kahn's algorithm tracks in-degrees of nodes to identify valid task processing order.

Knowledge Check

What condition indicates that prerequisites contain a cyclic dependency loop?

Q21: Course Schedule (Topological Sort / Cycle Detection)

STAY UPDATED WITH BYTES!