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.

Sources: Wikipedia: Topological sorting, Kahn (1962), Topological sorting of large networks

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
}

function topoSort(n: number, adj: number[][]): number[] | null {
    const indeg = new Array<number>(n).fill(0);
    for (const edges of adj) for (const v of edges) indeg[v]++;
    const queue: number[] = [];
    for (let i = 0; i < n; i++) if (indeg[i] === 0) queue.push(i);
    const order: number[] = [];
    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
}

from collections import deque

def topo_sort(n, adj):
    indeg = [0] * n
    for u in adj:
        for v in adj[u]:
            indeg[v] += 1
    queue = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj.get(u, []):
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)
    return order if len(order) == n else None  # None: a cycle exists

function topoSort(int $n, array $adj): ?array {
    $indeg = array_fill(0, $n, 0);
    foreach ($adj as $u => $neighbors) {
        foreach ($neighbors as $v) $indeg[$v]++;
    }
    $queue = [];
    for ($i = 0; $i < $n; $i++) if ($indeg[$i] === 0) $queue[] = $i;
    $order = [];
    while ($queue) {
        $u = array_shift($queue);
        $order[] = $u;
        foreach ($adj[$u] ?? [] as $v) {
            if (--$indeg[$v] === 0) $queue[] = $v;
        }
    }
    return count($order) === $n ? $order : null; // null: a cycle exists
}

    public static List<Integer> topoSort(int n, List<List<Integer>> adj) {
        int[] indeg = new int[n];
        for (List<Integer> edges : adj) for (int v : edges) indeg[v]++;
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) if (indeg[i] == 0) queue.add(i);
        List<Integer> order = new ArrayList<>();
        while (!queue.isEmpty()) {
            int u = queue.poll();
            order.add(u);
            for (int v : adj.get(u)) {
                if (--indeg[v] == 0) queue.add(v);
            }
        }
        return order.size() == n ? order : null; // null: a cycle exists
    }

    public static List<int> TopoSort(int n, List<List<int>> adj) {
        var indeg = new int[n];
        foreach (var edges in adj) foreach (int v in edges) indeg[v]++;
        var queue = new Queue<int>();
        for (int i = 0; i < n; i++) if (indeg[i] == 0) queue.Enqueue(i);
        var order = new List<int>();
        while (queue.Count > 0) {
            int u = queue.Dequeue();
            order.Add(u);
            foreach (int v in adj[u]) {
                if (--indeg[v] == 0) queue.Enqueue(v);
            }
        }
        return order.Count == 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)?

Use Topological sort (Kahn's algorithm) when the problem statement says “task must come before another”, “order that respects dependencies” or “detect a cycle in prerequisites”. A solution built on it usually runs in O(V+E).

• •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

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

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

Topological sort (Kahn's algorithm) is most often confused with Graph BFS / DFS, Connected components, Union-find (disjoint set) and Greedy (exchange argument).

• 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)?

Interview problems solved with Topological sort (Kahn's algorithm) include Course schedule, Course schedule II, Alien dictionary, Minimum height trees, Sequence reconstruction, Parallel courses and Sort items by group.

• 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)?

The target complexity of Topological sort (Kahn's algorithm) is O(V+E).

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