Course Schedule: Master Topological Sort with Kahn's Algorithm

Have you ever looked at a university course catalog and realized you can't take "Advanced Algorithms" without finishing "Data Structures" first? In computer science, this is a Dependency Management problem.

In LeetCode terms, this is the Course Schedule problem, and it's the perfect way to learn about Topological Sorting in Directed Acyclic Graphs (DAGs).

The Problem

Given numCourses and a list of prerequisites (where [a, b] means you must take course b before course a), can you finish all courses?

Basically, we need to check if the graph contains a cycle. If there is a cycle (e.g., A needs B, B needs C, and C needs A), it’s impossible to finish.

The Strategy: Kahn’s Algorithm (BFS)

Kahn’s Algorithm works by looking at the indegree of each node. The indegree is simply the number of incoming edges (dependencies) a node has.

1. Build an Adjacency List: Represent the courses and their dependencies.


2. Calculate Indegrees: Count how many prerequisites each course has.


3. Queue the "Free" Courses: Any course with an indegree of 0 can be taken immediately. Add them to a Queue.


4. Process the Queue:
   
   
   
   
   • Pick a course, "take" it, and increment your finished count.
   
   
   • For every neighbor (the courses that depend on this one), decrement their indegree.
   
   
   • If a neighbor's indegree hits 0, add it to the queue.
   
   
   
   


5. Check the Result: If the count of finished courses equals the total number of courses, you're good to go!

Java Implementation

class Solution {

    public boolean canFinish(int numCourses, int[][] prerequisites) {

        List<List<Integer>> adjList = new ArrayList<>();

        Queue<Integer> q = new LinkedList<>();



        // 1. Build the Adjacency List

        adjList = buildAdj(numCourses, prerequisites);



        // 2. Calculate Indegrees

        int[] indegree = new int[numCourses];

        for (int i = 0; i < prerequisites.length; i++) {

            indegree[prerequisites[i][0]]++;

        }



        // 3. Add courses with no prerequisites to the queue

        int count = 0;

        for (int i = 0; i < indegree.length; i++) {

            if (indegree[i] == 0) {

                q.add(i);

                count++;

            }

        }



        // 4. BFS Traversal

        while (!q.isEmpty()) {

            int node = q.poll();

            for (int neighbour : adjList.get(node)) {

                indegree[neighbour]--;



                // If dependency count drops to 0, it's ready to be taken

                if (indegree[neighbour] == 0) {

                    q.add(neighbour);

                    count++;

                }

            }

        }



        // 5. If we processed all courses, no cycle exists

        return count == numCourses;

    }



    public List<List<Integer>> buildAdj(int numCourses, int[][] prerequisites) {

        List<List<Integer>> adjList = new ArrayList<>();

        for (int i = 0; i < numCourses; i++) {

            adjList.add(new ArrayList<>());

        }

        for (int i = 0; i < prerequisites.length; i++) {

            // Index 1 is the prerequisite, Index 0 is the course

            adjList.get(prerequisites[i][1]).add(prerequisites[i][0]);

        }

        return adjList;

    }

}

Complexity Analysis

Time Complexity: O(V + E)

We visit every vertex (course) and every edge (prerequisite) exactly once during the adjacency list construction and the BFS traversal.

Space Complexity: O(V + E)

We store the graph in an adjacency list (O(V+E)) and use an indegree array (O(V)) plus a queue (O(V)).