Topological sort takes a directed acyclic graph and produces a line-up of its nodes where every edge points forward: if there is an edge from A to B, A appears before B in the result. It is the algorithm behind every "figure out what order to run these steps in" problem, from installing packages to compiling a spreadsheet formula by formula.
What changed in 2026
- Package managers lean on it more visibly. As dependency graphs grow deeper across monorepos and multi-language projects, more tools surface the resolved install order directly, rather than hiding it as an implementation detail — useful when a bad conflict needs debugging.
- Task orchestrators expose the ordering, not just the result. Modern pipeline tools increasingly let you inspect the computed topological order before execution, so you can catch a wrong dependency before it runs rather than after.
- Parallel scheduling got more attention. Because a topological order is rarely unique, schedulers increasingly exploit that freedom to run independent branches of the DAG concurrently instead of processing everything strictly in one line.
The two standard algorithms
Kahn approach (queue-based). Count the incoming edges for every node. Put every node with zero incoming edges in a queue. Repeatedly pop a node, add it to the result, and decrement the incoming-edge count of its neighbors — any neighbor that drops to zero joins the queue. If the queue empties before every node has been processed, the graph has a cycle.
from collections import deque
def topological_sort(graph):
indegree = {n: 0 for n in graph}
for n in graph:
for m in graph[n]:
indegree[m] += 1
queue = deque(n for n in indegree if indegree[n] == 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)
if len(order) != len(graph):
raise ValueError("graph has a cycle")
return order
DFS-based sort. Run a depth-first search from every unvisited node, and once a node has no more unvisited neighbors to explore, push it onto a stack. Reverse the stack at the end. It works because a node only gets pushed after everything reachable from it has already been pushed.
Both produce a valid order. Neither is "more correct" than the other — pick Kahn when you also want cycle detection and parallel-batch information for free, and DFS-based sort when you are already doing a DFS pass for another reason.
Comparing the two approaches
| Approach |
How it works |
Detects cycles as a side effect |
Natural fit for |
| Kahn (queue) |
Repeatedly remove zero-indegree nodes |
Yes — leftover nodes mean a cycle |
Parallel scheduling, build systems |
| DFS-based |
Postorder traversal, then reverse |
Yes, with a gray/visiting marker |
Compilers, single-pass static analysis |
Why the order is not unique
If a graph has two nodes that do not depend on each other at all, either can legally come first. A build system with ten independent packages has 10-factorial valid orders. This is a feature: it is exactly the freedom a scheduler needs to run those ten packages in parallel instead of picking an arbitrary sequence and serializing everything.
Common mistakes
Forgetting to check for a cycle at all. A naive implementation can silently return a partial or wrong order instead of failing loudly on a graph that was never a valid DAG to begin with.
Assuming the topological order is the fastest execution order. Order determines correctness, not speed. Combine it with knowledge of which branches are independent if you actually want to parallelize.
Re-sorting after every small graph change. For a graph that changes incrementally (adding one task at a time), a full re-sort is wasteful. Incremental algorithms exist for that case — reach for one before assuming a full re-run is required.
FAQ
Does topological sort work on an undirected graph?
No. The whole concept depends on edges having a direction, which is what defines "comes before."
What happens if I run it on a graph with a cycle?
A correct implementation should detect this and fail explicitly rather than return a silently wrong order. Both the Kahn and DFS approaches can be adapted to report the cycle.
Is topological sort the same as sorting numbers?
No. Numeric sorting has one correct output. Topological sort usually has many valid outputs; it only enforces relative order between connected nodes.
Which is faster, Kahn or DFS-based sort?
Both run in linear time relative to the number of nodes and edges. In practice, pick based on what else your pipeline is already doing, not on raw speed.
Where to go next