Topological Sort

Concept

LeetCode #210. Course Schedule II.
Problem: You are given numCourses and a list of prerequisites. Return the exact ordering of courses you should take to finish all courses. If it is impossible, return an empty array.

This problem requires a Topological Sort.
A Topological Sort takes a Directed Acyclic Graph (DAG) and flattens it into a 1D array such that for every directed edge U -> V, node U mathematically comes before node V in the array.

Kahn’s Algorithm (BFS)

Kahn’s Algorithm is the standard way to perform a Topological Sort. It mimics how humans actually solve prerequisite chains: “Find the easiest thing with no dependencies, do it, and cross it off the list.”

The Architecture:

1. Adjacency List: Maps Course -> [Dependent Courses].
2. In-Degree Array: An array of integers. inDegree[i] stores exactly how many prerequisites course i still needs before you can take it.

// Time Complexity: O(V + E)
// Space Complexity: O(V + E) (Adjacency List + InDegree Array + Queue)

function findOrder(numCourses: number, prerequisites: number[][]): number[] {
    const adjList = new Map<number, number[]>();
    const inDegree = new Array(numCourses).fill(0);
    
    // 1. Initialize Adjacency List
    for (let i = 0; i < numCourses; i++) adjList.set(i, []);
    
    // 2. Build the Graph AND tally the In-Degrees
    for (let [course, preReq] of prerequisites) {
        adjList.get(preReq)!.push(course); // preReq points to course
        inDegree[course]++;                // course has 1 more incoming requirement!
    }
    
    // 3. Find all courses with ZERO prerequisites to start our Queue
    const queue: number[] = [];
    for (let i = 0; i < numCourses; i++) {
        if (inDegree[i] === 0) {
            queue.push(i);
        }
    }
    
    const topoOrder: number[] = [];
    
    // 4. Process the Queue
    while (queue.length > 0) {
        // In JS, shift() is O(N), but we use it here for clarity. 
        // A real queue or an index pointer makes this O(1).
        const currentCourse = queue.shift()!;
        
        // We took the course! Add it to our final transcript.
        topoOrder.push(currentCourse);
        
        // Inform all dependent courses that a prerequisite was fulfilled
        for (let dependentCourse of adjList.get(currentCourse)!) {
            inDegree[dependentCourse]--;
            
            // If the dependent course now has ZERO prerequisites, it's safe to take!
            if (inDegree[dependentCourse] === 0) {
                queue.push(dependentCourse);
            }
        }
    }
    
    // 5. Did we take all courses? Or was there a deadlock cycle?
    if (topoOrder.length === numCourses) {
        return topoOrder;
    } else {
        return []; // Cycle detected! Impossible to finish.
    }
}

The DFS Alternative

Can you do Topological Sort using DFS? Yes!

In the previous section, we used DFS to detect cycles by marking nodes as Fully Processed when we safely survived all their dependent paths.
Think about the geometry of that: The very first node to be marked Fully Processed is the node that has absolutely no dependent paths below it! (The very last course in the chain).

If you take a standard DFS Cycle Detection algorithm, and simply push nodes into an array the exact moment you mark them Fully Processed, that array will contain the exact Topological Order… in reverse!
At the very end of the algorithm, you simply array.reverse(), and you have a perfect $O(V + E)$ Topological Sort.

Interview Questions

Q: A Topological Sort returns [0, 1, 2, 3]. Another algorithm running on the exact same graph returns [0, 2, 1, 3]. Can they both be correct?
A: Yes! Topological Sorts are rarely unique. If Course 1 and Course 2 both only require Course 0, you can legally take them in either order. [0, 1, 2] and [0, 2, 1] are both perfectly valid topological orderings of the exact same graph.

Q: Can you run Kahn’s Algorithm on an Undirected Graph?
A: No. Kahn’s Algorithm strictly relies on tracking In-Degree arrows. In an Undirected Graph, edges are two-way. Node A points to B, and B points back to A. Every single connected node instantly has an In-Degree of at least 1, creating an infinite cycle. The Queue will start entirely empty, and the algorithm will fail immediately. Topological Sort only exists for Directed Acyclic Graphs (DAGs).