Kahn's Algorithm for Topological Sorting

Hello! In our previous lesson, we explored how to detect cycles in directed graphs using a three-state DFS. This was crucial because cycles represent impossible situations, like a set of tasks where each depends on the next in a circular fashion.

Today, we'll focus on what we can do with directed graphs that are guaranteed to have no cycles: Directed Acyclic Graphs (DAGs). For these graphs, we can compute a topological ordering—a linear sequence of all the nodes that respects their dependencies. This is a fundamental pattern with direct applications in areas you might be familiar with, such as resolving module dependencies in a JavaScript project, scheduling build tasks, or managing course prerequisites.

By the end of this lesson, you will be able to produce a topological ordering for any DAG using a popular and intuitive method called Kahn's algorithm, which is based on node "in-degrees."

What is a Topological Ordering?

Imagine you have a list of tasks, where some tasks must be completed before others. A topological sort gives you a valid sequence in which to perform these tasks. Formally, for every directed edge from node U to node V in the graph, U must appear before V in the linear ordering.

A key insight is that such an ordering is only possible if the graph is acyclic. If there's a cycle, it's impossible to satisfy the dependencies. As a front-end developer, you've likely seen this manifest as "circular dependency" errors from module bundlers like Webpack or Rollup when Module A imports Module B, and Module B imports Module A.

To dive deeper into the definition and see why cycles make this impossible, the following resource from AlgoMonster is a great start.

Kahn's Algorithm: An Intuitive, Queue-Based Approach

There are a couple of ways to generate a topological sort, but the most common one in interviews is Kahn's algorithm. It's an iterative approach that mirrors how you might naturally schedule tasks:

1. Find all tasks that have no prerequisites. You can start with any of these.
2. Pick one such task, complete it, and add it to your sorted list.
3. By completing this task, you might have fulfilled a prerequisite for other tasks. Re-evaluate the remaining tasks to see if any new ones now have all their prerequisites met.
4. Repeat this process until all tasks are completed.

Kahn's algorithm formalizes this using the concept of in-degree, which is simply the count of incoming edges for a node. A node with an in-degree of 0 has no prerequisites.

The algorithm proceeds as follows:

1. Compute In-degrees: Calculate the in-degree for every node in the graph.
2. Initialize Queue: Create a queue and add all nodes with an in-degree of 0.
3. Process Nodes:
   • While the queue is not empty:
     • Dequeue a node and add it to our result list (the topological order).
     • For each of the node's neighbors, decrement their in-degree by 1. This signifies that one of their prerequisites has just been met.
     • If a neighbor's in-degree becomes 0, add it to the queue.
4. Check for Cycles: If the final sorted list contains fewer nodes than the graph, it means there was a cycle. The nodes in the cycle (and those that depend on them) never had their in-degrees reduced to 0, so they were never added to the queue.

This flowchart provides a great visual summary of the process.

A Worked Example: Getting Dressed

To see Kahn's algorithm in action, let's watch a detailed walkthrough. The following video uses a "getting dressed" analogy (e.g., you must wear socks before shoes). The presenter does an excellent job of visually tracking the in-degrees and the state of the queue.

From Concept to Code

Now, let's translate this logic into a TypeScript function. Our goal is to create a function that takes the number of nodes and a list of edges (prerequisites) and returns a valid topological order. We'll use an adjacency list for the graph and an array to store the in-degrees.

The code for this pattern is very similar to BFS, with two key differences:

1. The queue is initialized only with nodes that have an in-degree of 0.
2. A node is added to the queue only when its in-degree is decremented to 0.

The following JavaScript code from AlgoMonster provides a solid foundation for our implementation.

Building on that structure, here is a complete TypeScript implementation that you can use as a template for interview problems.

/**
 * Produces a topological ordering of a directed acyclic graph.
 * @param numNodes The total number of nodes (labeled 0 to numNodes-1).
 * @param prerequisites An array of pairs [u, v] where v is a prerequisite for u (v -> u).
 * @returns An array representing a valid topological order, or an empty array if a cycle is detected.
 */
function topologicalSort(numNodes: number, prerequisites: number[][]): number[] {
    // 1. Build adjacency list and in-degree array
    const adj: number[][] = Array.from({ length: numNodes }, () => []);
    const inDegree: number[] = new Array(numNodes).fill(0);

    for (const [course, prereq] of prerequisites) {
        adj[prereq].push(course);
        inDegree[course]++;
    }

    // 2. Initialize the queue with all nodes having an in-degree of 0
    const queue: number[] = [];
    for (let i = 0; i < numNodes; i++) {
        if (inDegree[i] === 0) {
            queue.push(i);
        }
    }

    // 3. Process the queue
    const sortedOrder: number[] = [];
    while (queue.length > 0) {
        const node = queue.shift()!; // Non-null assertion is safe here
        sortedOrder.push(node);

        // For each neighbor, decrement its in-degree
        for (const neighbor of adj[node]) {
            inDegree[neighbor]--;
            // If a neighbor's in-degree becomes 0, add it to the queue
            if (inDegree[neighbor] === 0) {
                queue.push(neighbor);
            }
        }
    }

    // 4. Check for cycles
    if (sortedOrder.length === numNodes) {
        return sortedOrder;
    } else {
        // If the sorted order has fewer nodes, a cycle must have been present.
        return [];
    }
}

// Example: LeetCode 210 "Course Schedule II"
// numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
// Edges: 0->1, 0->2, 1->3, 2->3
const result = topologicalSort(4, [[1,0],[2,0],[3,1],[3,2]]);
console.log(result); // A possible valid output: [0, 1, 2, 3] or [0, 2, 1, 3]

Complexity Analysis

• Time Complexity: $O(V+E)$, where $V$ is the number of vertices (nodes) and $E$ is the number of edges. Building the adjacency list and in-degrees takes $O(E)$. Then, every node is enqueued and dequeued exactly once ($O(V)$), and every edge is processed exactly once when we decrement the neighbors' in-degrees ($O(E)$).
• Space Complexity: $O(V+E)$. This is for storing the adjacency list ($O(V+E)$), the in-degree array ($O(V)$), and the queue (which can hold up to $O(V)$ nodes).

Application: "Course Schedule II" (LeetCode 210)

This algorithm directly solves the classic interview problem "Course Schedule II". The problem gives you a number of courses and a list of prerequisites and asks you to return one possible order in which to take the courses. This is a textbook application of topological sort.

The following video walks through how to apply Kahn's algorithm to this exact problem, reinforcing the implementation steps we just covered.

Conclusion

You have now learned one of the most practical graph algorithms. Topological sorting is the definitive way to handle dependency resolution in directed acyclic graphs.

Key Takeaways:

• What it is: A topological sort is a linear ordering of a DAG's nodes where for every edge U -> V, U comes before V.
• Why it's useful: It solves problems involving dependencies, like task scheduling, build systems, and course prerequisites.
• Kahn's Algorithm: An intuitive, queue-based method that works by repeatedly processing nodes with no remaining dependencies (in-degree of 0).
• Implementation: The process involves calculating in-degrees, initializing a queue with zero-in-degree nodes, and then iteratively processing the queue while updating the in-degrees of neighbors.
• Cycle Detection: Kahn's algorithm provides a simple way to detect cycles: if the final sorted list is smaller than the total number of nodes, a cycle exists.

In our next lesson, we will move from ordering nodes to finding optimal paths. We'll explore Dijkstra's algorithm, which finds the shortest path between nodes in a weighted graph, another cornerstone algorithm for your interview toolkit.