Topological Sort: Complete Guide with Kahn's and DFS

Topological sort is the algorithm that turns a pile of dependencies into a working order. A build system uses it to decide which modules compile first. A package manager uses it to figure out the install order. A scheduler uses it to sequence tasks that wait on other tasks. In every case the input is a directed graph, and the output is a linear order that respects every edge.

Formally, a topological sort of a directed graph is an ordering of its vertices such that for every edge u to v, u appears before v. This is only possible when the graph has no cycles, so the pattern applies to directed acyclic graphs, or DAGs.

Real-World Analogy

Picture cooking dinner for guests. Some steps have hard dependencies. You cannot stir-fry the vegetables until they are chopped. You cannot plate the roast until it has finished cooking. But plenty of steps are independent. Boiling water, chopping herbs, and setting the table can happen whenever there is a free moment. A meal plan is valid as long as every step that depends on another step comes after it, and the plan is never unique. You can chop herbs before or after you set the table, and the dinner still works out.

That is exactly what a topological sort gives you. It is any complete ordering of the tasks that satisfies every dependency, and usually several valid orders exist.

Visual Explanation: Kahn’s Algorithm

Kahn’s algorithm is the most direct way to compute a topological order. It repeatedly removes nodes whose prerequisites are all satisfied. A node’s indegree is the number of incoming edges, which is the number of prerequisites it still has. Nodes with indegree zero are ready, and removing one lowers the indegree of every node that depends on it.

    graph TD
    A["Build adjacency list, count indegrees"] --> B["Queue every node with indegree 0"]
    B --> C{"Queue empty?"}
    C -->|No| D["Pop u, append to order"]
    D --> E["Lower indegree of every neighbor"]
    E --> F{"Neighbor indegree 0?"}
    F -->|Yes| G["Queue that neighbor"]
    G --> C
    F -->|No| C
    C -->|Yes| H{"Order length equals V?"}
    H -->|Yes| I["Order is valid"]
    H -->|No| J["Cycle exists"]
  

The interesting part is the last decision. When the queue empties, either every node was processed, or some nodes are stuck in a cycle where each one waits on another and none ever reaches indegree zero. Comparing the order length against the node count is the whole cycle check.

Here is the algorithm on a small graph where node 0 points at 1 and 2, and both 1 and 2 point at 3.

Node 0 starts alone in the queue because nothing points at it. After it is removed, nodes 1 and 2 both reach indegree zero and join. The order [0, 1, 2, 3] is valid, and so is [0, 2, 1, 3]. Both respect every edge, which is all a topological sort promises.

The DFS Alternative

Depth-first search produces a topological order as a side effect. Run DFS from every unvisited node, and record a node only after all of its descendants have been recorded. Reversing that recorded list gives a valid topological order. The reversal is needed because a node is appended when it finishes, which puts dependents ahead of the dependencies they rely on.

    graph TD
    A["DFS from an unvisited node"] --> B{"Reached a node still in progress?"}
    B -->|Yes| C["Back edge: cycle"]
    B -->|No| D["Recurse into unvisited neighbors"]
    D --> E["Mark node done, append to order"]
    E --> F{"All nodes visited?"}
    F -->|No| A
    F -->|Yes| G["Reverse the order"]
  

Each node carries one of three states: unvisited, in progress, or done. Hitting a node that is still in progress means a back edge exists, which is a cycle. This approach uses the call stack instead of a queue, so very large graphs can overflow the stack. Kahn’s algorithm has no such limit.

When to Use This Pattern

• The problem describes tasks with prerequisites and asks whether all of them can be completed, or in what order. Course scheduling is the canonical example.
• The input is a set of constraints of the form “A must come before B,” and you need one sequence that honors every constraint.
• You need to detect whether a directed graph contains a cycle, and a valid order proves the graph is acyclic whenever one exists.
• The problem asks for the minimum number of rounds to finish everything, where independent tasks run in parallel. Each layer of ready tasks is one round.
• You need a fixed processing order to run dynamic programming over a DAG, for example the longest path in a dependency graph.

Complexity Analysis

Let V be the number of vertices and E the number of edges.

Every edge is touched exactly once, when its source node leaves the queue. Every node is touched exactly once, when it enters and leaves the queue. That is where the O(V + E) bound comes from. The DFS version has the same time complexity, and it uses O(V) extra space for the call stack on top of the graph storage.

Common Mistakes

Forgetting the final cycle check. Kahn’s algorithm runs to completion even on a cyclic graph, but the order it produces is missing the nodes that are stuck in the cycle. If you return the order without comparing its length to V, a cyclic input produces an incomplete order instead of a failure. This is the single most common bug in the pattern. Catch it by testing with a self-loop and a two-node cycle before anything else.

Reversing edge direction when building the graph. The indegree of a node is the number of incoming edges, meaning the number of prerequisites it still has. It is easy to count outgoing edges instead, especially when the problem describes dependencies in words rather than arrows. A flipped graph produces a meaningless order or reports a cycle that is not there. Catch it by tracing a two-node example on paper. If the rule is “A before B,” then B must have indegree one and A must have indegree zero.

Seeding the queue with one source instead of all of them. A DAG can have several nodes with indegree zero, especially when the graph is disconnected. Starting from a single node only produces the order for the component that contains it. Catch it by scanning every node when you build the initial queue.

Treating the DFS record order as the final answer. The DFS approach appends nodes when they finish, which puts dependents before the dependencies they rely on. Returning that list directly is wrong. The reversal step is the point of the algorithm, and skipping it is a common slip under time pressure. Catch it with a two-node chain. For the edge 0 to 1, the finished order reads [1, 0], and the answer is [0, 1].

Related Patterns

• Graph Traversal . Kahn’s algorithm is BFS with an indegree twist, and the DFS alternative is plain DFS with a recording step. The graph traversal pages cover the underlying machinery.
• Cycle Detection . The final length check in Kahn’s and the in-progress state in DFS are cycle detection in disguise. Course Schedule appears on both pages for exactly this reason.
• Shortest Path . In a DAG, relaxing edges in topological order computes shortest paths in linear time, so topological order is a building block for DAG shortest path algorithms.

Next Steps

Once the ordering logic makes sense, make the code automatic. The code templates cover Kahn’s algorithm and the DFS alternative in 6 languages. The practice problems walk through Course Schedule, Alien Dictionary, and the rest with full solutions.