Topological Sort Calculator

Pseudocode

Two standard formulations, both linear. Kahn works forward from nodes with no prerequisites; the DFS version works backward from finish times.

// Kahn: repeatedly remove a node with no incoming edges
compute indegree[v] for every vertex
queue = all vertices with indegree 0
order = []

while queue is not empty:
    u = queue.pop()
    order.append(u)
    for each edge (u, v):
        indegree[v] -= 1
        if indegree[v] == 0: queue.push(v)

if order.length < V: the graph has a cycle

// DFS variant: reverse of finish order
run DFS; push each vertex onto a stack when it finishes
the stack, popped, is a valid topological order

Kahn has one practical advantage worth knowing: because it detects a cycle by counting how many nodes it managed to emit, the vertices left over are exactly those involved in or downstream of a cycle. That makes it far more useful than a boolean when you need to report which dependencies are circular.

Worked example, step by step

Run Kahn on a small build-dependency graph, where an edge X to Y means X must be built before Y.

Example graph: Directed edges A to C, B to C, C to D, B to D.

1. Compute indegrees. A has 0, B has 0, C has 2 (from A and B), D has 2 (from C and B). Queue starts with A and B.
2. Emit A. Order is [A]. Decrement C to indegree 1. Not zero yet, so C is not enqueued.
3. Emit B. Order is [A, B]. Decrement C to 0, so C is enqueued. Decrement D to 1.
4. Emit C. Order is [A, B, C]. Decrement D to 0, so D is enqueued.
5. Emit D. Order is [A, B, C, D]. The queue is empty and all four nodes were emitted, so no cycle exists.

A valid order is A, B, C, D. Note that B, A, C, D is equally valid: A and B are both prerequisite-free and their relative order is unconstrained. Topological order is not unique unless the graph is a single chain, which is why tests should verify that every edge points forward rather than compare against one expected sequence.

Complexity, and where it comes from

Time: O(V + E) · Space: O(V)

Computing all indegrees requires one scan of every edge, O(E). Each vertex is enqueued and dequeued exactly once, O(V). Each edge is examined exactly once, when its source is emitted and the target indegree is decremented, another O(E). Space holds the indegree array, the queue and the output list, all O(V). The DFS variant has the same bounds, with the recursion stack replacing the queue. Neither can be improved, since any correct algorithm must read every edge to know the constraints.

When to use Topological Sort, and when not to

Kahn and DFS produce equally valid orders. Choose on what you need alongside the ordering.

Common pitfalls

• Running it on a graph with a cycle and not noticing. A cyclic graph has no topological order at all. Kahn will silently emit a partial order unless you compare the output length against V. That check is the cycle test, and skipping it produces a plausible but incomplete build order.
• Expecting a unique answer. Any two nodes with no path between them can appear in either order. Comparing against one hardcoded sequence makes tests fail on correct implementations; assert instead that every edge points forward in the output.
• Confusing edge direction. If an edge X to Y means "X depends on Y", the topological order is the reverse of what you want. Fix the convention once, at the point where the graph is built, rather than reversing the output and hoping.
• Applying it to undirected graphs. Topological order is only defined for directed acyclic graphs. An undirected edge is a two-cycle, so no undirected graph with any edge has a topological order.
• Recursing too deep in the DFS variant. A dependency chain of tens of thousands of nodes will overflow the call stack. Kahn is iterative and has no such limit, which is one reason build tools tend to prefer it.

Frequently asked questions

What is topological sorting used for?

It orders the vertices of a directed acyclic graph so that every edge points forward, which answers "in what order can these tasks run given their dependencies". It schedules build systems such as Make and Gradle, resolves package installation order, orders university courses with prerequisites, sequences spreadsheet cell evaluation, and schedules instructions in compilers.

What is the difference between Kahn and the DFS approach?

Kahn repeatedly removes nodes with indegree zero using a queue, working forward from things with no prerequisites. The DFS approach runs a depth-first search and outputs vertices in reverse finish order. Both are O(V + E) and both give valid orders. Kahn is iterative and reports which nodes are in cycles; DFS is shorter but recursive.

Can a graph have more than one topological order?

Almost always. Any two vertices with no directed path between them may appear in either order, so a graph with V vertices and few edges can have very many valid orderings. The order is unique only when the graph contains a Hamiltonian path, which for a DAG means a single chain through all vertices.

How do you detect a cycle during topological sorting?

With Kahn, count the emitted vertices: if fewer than V come out, the remaining ones are in or downstream of a cycle, because none of them ever reached indegree zero. With the DFS variant, a back edge into a vertex still on the recursion stack proves a cycle.

What is the time complexity of topological sort?

O(V + E) time and O(V) space for both Kahn and the DFS variant. Every vertex is processed once and every edge is examined once. This is optimal, since any algorithm must at minimum read all the dependency edges.