Q20: How do you solve Course Schedule I using Topological Sort (Kahn's Algorithm)?

Model course dependencies as a Directed Graph. Detect if a Cycle exists using Kahn's Algorithm (BFS Topological Sort):

Build adjacency list and compute inDegree[] array for each node.
Add all nodes with inDegree == 0 to a Queue.
While queue is non-empty, poll node, increment processedCount, and decrement inDegree of neighbor nodes. If neighbor inDegree hits 0, offer to Queue.
Return processedCount == numCourses.

Kahn's Algorithm Course Schedule

import java.util.*;

public class CourseSchedule {
    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
        int[] inDegree = new int[numCourses];
        for (int[] p : prerequisites) {
            adj.get(p[1]).add(p[0]);
            inDegree[p[0]]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) queue.offer(i);
        }
        int processed = 0;
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            processed++;
            for (int neighbor : adj.get(curr)) {
                if (--inDegree[neighbor] == 0) queue.offer(neighbor);
            }
        }
        return processed == numCourses;
    }
}

💡 Validates graph acyclicity by verifying that all courses can be processed in topological order.

Key Takeaways

Topological Sort detects cycles in Directed Graphs.
Kahn's algorithm processes nodes with 0 in-degree using BFS.

Knowledge Check

If a directed graph contains a cycle, what will processedCount equal at the end of Kahn's Algorithm?

Q20: How do you solve Course Schedule I using Topological Sort (Kahn's Algorithm)?

STAY UPDATED WITH BYTES!