Topological sort (Kahn's algorithm)

How does Topological sort (Kahn's algorithm) work?

Count how many edges point into each node. That number is its in-degree.

Put every node with in-degree zero into a queue. Those owe nothing and can go first.

Take one node out and append it to the answer. It is now placed for good.

Walk its outgoing edges and drop each target's count by one. That target has one fewer debt.

A count that reaches zero joins the queue. All of its dependencies are already placed.

If the answer is shorter than the node count, a cycle exists. Nodes inside a cycle never reach zero.

1. in-degrees: A 0, B 1, C 1, D 2Edges are A to B, A to C, B to D and C to D.
2. queue = [A], output = []Only A owes nothing, so it is the single starting point.
3. take A, output = [A]B and C each lose one debt. Both reach zero.
4. queue = [B, C]D still owes two. It has to wait.
5. output = [A, B, C, D]D joins once both of its debts are cleared.

function topoSort(n, adj) {
    const indeg = new Array(n).fill(0);
    for (const u in adj) for (const v of adj[u]) indeg[v]++;
    const queue = [];
    for (let i = 0; i < n; i++) if (indeg[i] === 0) queue.push(i);
    const order = [];
    while (queue.length) {
        const u = queue.shift();
        order.push(u);
        for (const v of adj[u] || []) {
            if (--indeg[v] === 0) queue.push(v);
        }
    }
    return order.length === n ? order : null; // null: a cycle exists
}

A worked example of Topological sort (Kahn's algorithm)

An order to take every course

You get a course count and a list of prerequisite pairs. Return an order that lets you take them all.

If no such order exists, return an empty list.

Build the adjacency list and the in-degree counts in one pass.

Then run the queue loop. An answer shorter than the course count means a cycle.

function findOrder(numCourses, prerequisites) {
    const next = Array.from({ length: numCourses }, () => []);
    const indegree = new Array(numCourses).fill(0);

    for (const [course, needs] of prerequisites) {
        next[needs].push(course);
        indegree[course]++;
    }

    const queue = [];
    for (let i = 0; i < numCourses; i++) {
        if (indegree[i] === 0) queue.push(i);
    }

    const order = [];
    for (let i = 0; i < queue.length; i++) { // index walk, never shift
        const node = queue[i];
        order.push(node);

        for (const target of next[node]) {
            if (--indegree[target] === 0) queue.push(target);
        }
    }

    // a short answer means some nodes never reached zero
    return order.length === numCourses ? order : [];
}

When should you use Topological sort (Kahn's algorithm)?

These phrases in a problem statement point here:

• •task must come before another
• •order that respects dependencies
• •detect a cycle in prerequisites
• •build order / course schedule / install order
• •directed graph, X must happen before Y

What is Topological sort (Kahn's algorithm) confused with?

• Graph BFS / DFS: A plain walk visits every node in whatever order it likes. Here the order is the answer.
• Connected components: Components ignore direction and only group nodes. Here direction defines the whole answer.
• Union-find (disjoint set): Union-find treats every edge as undirected. Direction is exactly what matters here.
• Greedy (exchange argument): The rule is greedy: take anything with no debts left. Removing a node can never add a dependency.

Common mistakes with Topological sort (Kahn's algorithm)

• Building the edges backwards

  A prerequisite pair reads as course then requirement. Reversing it silently solves a different problem.

• Not checking the length at the end

  A cycle gives a short answer, never an error. Compare the length against the node count.

• Expecting one unique order

  Several nodes can be ready at the same moment. Any order among them is correct.

• Using shift on the queue

  In JavaScript that is O(n) per removal. Walk the array with an index instead.

Which interview problems use Topological sort (Kahn's algorithm)?

• Course schedule: Only whether a valid order exists at all.
• Course schedule II: Return the order itself, not just a yes or no.
• Alien dictionary: Derive the edges by comparing adjacent words.
• Minimum height trees: Peel the leaves layer by layer instead.
• Sequence reconstruction: Check that exactly one node is ready at each step.
• Parallel courses: Count the rounds rather than producing an order.
• Sort items by group: Two orderings, one inside groups and one across them.

What is the time and space complexity of Topological sort (Kahn's algorithm)?

O(V+E)

V nodes and E edges give O(V + E). Every edge is removed exactly once.