Topological Sort Explained: Kahn's Algorithm and the DFS Version

A topological sort orders the nodes of a directed graph so that every edge points forwards — if u must happen before v, then u comes first. That is the whole definition, and it is the answer to every interview problem phrased as prerequisites, dependencies, build order, or a course schedule.

There are two standard ways to compute it, and both give you cycle detection for free. This covers Kahn's algorithm, the DFS variant, why the cycle check matters more than the ordering in most problems, and four worked problems in Python.

What the ordering actually is#

A valid ordering exists if and only if the graph is a directed acyclic graph — a DAG. If A depends on B and B depends on A, no ordering can satisfy both, and any correct implementation has to report that rather than emit nonsense.

Two things surprise people the first time:

The order is usually not unique. If three nodes have no unmet prerequisites, any of them may come next. Judges accept any valid ordering. If a problem wants a specific one — lexicographically smallest, most often — that is an extra requirement, and you satisfy it by replacing the queue with a min-heap.

The cycle check is frequently the actual question. Course Schedule does not ask for an order at all; it asks whether one exists. You compute the order anyway and check its length.

Kahn's algorithm: topological sort by counting prerequisites#

The idea in one sentence: repeatedly take any node with no remaining prerequisites, emit it, and remove its outgoing edges.

Concretely, count incoming edges for every node. Every node whose count is zero can go first, so they all start in a queue. Emitting a node decrements the count of each of its neighbours, and a neighbour joins the queue at the exact moment its last prerequisite disappears.

Here it is for Course Schedule II, where prerequisites[i] = [course, needed_first]:

from collections import deque

def find_order(num_courses, prerequisites):
    graph = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses

    for course, needed_first in prerequisites:
        graph[needed_first].append(course)
        indegree[course] += 1

    queue = deque(node for node in range(num_courses) if indegree[node] == 0)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            indegree[neighbour] -= 1
            if indegree[neighbour] == 0:
                queue.append(neighbour)

    return order if len(order) == num_courses else []

Walk it on four courses with [[1, 0], [2, 0], [3, 1], [3, 2]]:

Note that 0 2 1 3 would have been equally valid — the only reason the output is what it is comes down to the order the queue happened to be seeded in.

The direction of the edges is the one thing to get right, and it is the most common bug. LeetCode writes the pair as [course, needed_first], which reads left to right but means the edge points right to left. Write the edge direction down in a comment before you build the graph.

Complexity: O(V + E) time and O(V + E) space. Every node is enqueued once and every edge is examined once.

The DFS variant#

The same result from the other direction: visit a node's descendants first, append the node once they are all finished, and reverse at the end. The node whose subtree finishes last ends up first.

The subtlety is cycle detection. A two-state visited set is not enough, because "I have finished with this node" and "this node is on the path I am currently walking" are different facts and only the second means a cycle:

def dfs_order(num_courses, graph):
    """graph[node] is the list of nodes that depend on `node`."""
    finished = set()
    on_path = set()
    order = []

    def visit(node):
        if node in finished:
            return True
        if node in on_path:
            return False
        on_path.add(node)
        for neighbour in graph[node]:
            if not visit(neighbour):
                return False
        on_path.discard(node)
        finished.add(node)
        order.append(node)
        return True

    for node in range(num_courses):
        if not visit(node):
            return []

    order.reverse()
    return order

Reaching a node in finished is fine — it is a diamond in the graph, not a cycle. Reaching one in on_path means you have walked in a circle, and there is no valid ordering.

The recursion depth equals the longest path, so on a graph with tens of thousands of nodes in a chain this hits Python's recursion limit. That is the practical argument for preferring Kahn's algorithm in an interview: it has no such failure mode and its state is easier to narrate.

Worked problems#

Course Schedule and Course Schedule II#

Problem 207 asks only whether you can finish. Run the code above and return len(order) == num_courses. Problem 210 asks for the order itself and expects an empty list when a cycle exists. They are the same function with a different return statement, which is worth saying out loud if you get the second one after the first.

Alien Dictionary#

Problem 269 is the one that tests whether you can build the graph, which is usually the harder half. Given words sorted in an unknown alphabet, the only information available is the first differing character between each adjacent pair.

from collections import deque

def alien_order(words):
    graph = {char: set() for word in words for char in word}
    indegree = {char: 0 for char in graph}

    for first, second in zip(words, words[1:]):
        for a, b in zip(first, second):
            if a != b:
                if b not in graph[a]:
                    graph[a].add(b)
                    indegree[b] += 1
                break
        else:
            if len(first) > len(second):
                return ""

    queue = deque(char for char in indegree if indegree[char] == 0)
    order = []

    while queue:
        char = queue.popleft()
        order.append(char)
        for neighbour in graph[char]:
            indegree[neighbour] -= 1
            if indegree[neighbour] == 0:
                queue.append(neighbour)

    return "".join(order) if len(order) == len(indegree) else ""

Three details carry the whole problem. Only the first differing character gives an ordering, which is what the break enforces — everything after it is unconstrained. The for/else catches the invalid input where a word is followed by its own prefix, such as ["abc", "ab"], which no alphabet can explain. And the duplicate-edge guard matters: adding the same edge twice inflates the indegree and the node never reaches zero.

Complexity: O(total characters) time and O(1) space in the sense that the alphabet is bounded.

Minimum Height Trees#

Problem 310 is not a topological sort — the graph is undirected — but it runs the same indegree machinery, and recognising that is most of the solution. Peel the leaves layer by layer; whatever survives is the centre.

from collections import deque

def find_min_height_trees(n, edges):
    if n == 1:
        return [0]

    graph = [set() for _ in range(n)]
    for a, b in edges:
        graph[a].add(b)
        graph[b].add(a)

    leaves = deque(node for node in range(n) if len(graph[node]) == 1)
    remaining = n

    while remaining > 2:
        remaining -= len(leaves)
        for _ in range(len(leaves)):
            leaf = leaves.popleft()
            neighbour = graph[leaf].pop()
            graph[neighbour].discard(leaf)
            if len(graph[neighbour]) == 1:
                leaves.append(neighbour)

    return list(leaves)

A tree has at most two centres, which is why the loop stops at two rather than one. O(V) time.

Ordering that is really dynamic programming#

Longest Increasing Path in a Matrix is a DAG problem in disguise: each cell points at its strictly larger neighbours, so the graph cannot contain a cycle, and the answer at a cell depends only on cells after it in topological order. You can run Kahn's algorithm explicitly, but memoised DFS computes the same thing and is shorter to write — the recursion visits nodes in reverse topological order without ever naming it. That equivalence is worth holding onto: dynamic programming over a DAG and a topological sort are the same traversal, and whichever one is easier to write is the right answer.

What to say in an interview#

State the reduction first: "this is a dependency ordering, so it is a topological sort, and the cycle case is the one I need to handle." That sentence alone gets most of the credit for the approach.

Then be explicit about three things while you code:

1. The edge direction, out loud, before you build the graph.
2. What a short output means — the nodes that never reached indegree zero are exactly those in cycles.
3. The complexity, O(V + E), and why: each node enqueued once, each edge relaxed once.

More problems using this technique are collected on the topological sort pattern hub, and it sits next to BFS and union-find in the full pattern map. If you are working through a curated list, Course Schedule is the entry point on the Blind 75.

If you want help in the room rather than before it, Stealth Interview is a desktop app for macOS and Windows that reads the problem from a screenshot and walks through the approach, the code and the complexity with you, while staying invisible to screen sharing.