Topological Sort: The Pattern for Dependency Ordering Problems

Topological sort is the graph pattern for problems where one task must happen before another. If you have dependencies, prerequisites, or ordering constraints, topological sorting should come to mind quickly.

The key condition is that the graph must be a directed acyclic graph, or DAG.

What Topological Sort Produces

A topological ordering is a sequence of nodes such that for every directed edge u -> v, node u appears before v.

That makes it perfect for:

• course prerequisite problems
• build systems
• job scheduling
• dependency resolution

Kahn's Algorithm

The most common approach uses indegrees.

1. Count incoming edges for every node.
2. Put all nodes with indegree 0 into a queue.
3. Pop nodes from the queue and reduce indegrees of their neighbors.
4. Any neighbor whose indegree becomes 0 goes into the queue.

from collections import deque

def topo_sort(num_courses: int, prerequisites: list[list[int]]) -> list[int]:
    graph = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses

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

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

    while queue:
        node = queue.popleft()
        order.append(node)

        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

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

If you cannot process all nodes, the graph contains a cycle and no valid topological ordering exists.

Why Cycles Break It

Imagine:

• A depends on B
• B depends on C
• C depends on A

No node can come first because each one is waiting on another. That is exactly why topological sort only works on DAGs.

DFS Alternative

You can also build a topological order with DFS postorder traversal, adding nodes after exploring their neighbors and then reversing the result.

That approach is elegant, but Kahn's algorithm is often easier to explain in interviews because cycle detection is explicit through indegree processing.

Recognition Signals

Look for phrases like:

• before and after
• prerequisite
• dependency
• valid ordering
• can all tasks be completed

Those are strong hints that you are dealing with a directed graph and possibly a topological sort.

Common Mistakes

• Treating an undirected graph like a dependency graph
• Forgetting to detect cycles
• Reversing edge direction accidentally
• Assuming the ordering is unique

Many DAGs have multiple valid topological orders.

Complexity

For V vertices and E edges:

Practice These Next

• Course Schedule
• Course Schedule II
• Alien Dictionary
• Parallel Courses

Topological sort is one of the cleanest examples of how graph structure maps directly to a real-world problem: dependency ordering.