Menu
CoddyTech
Start learning

Topological Sort

Last updated

A topological sort of a directed acyclic graph (DAG) is a linear ordering of its nodes such that for every edge u → v, u comes before v. It answers questions like "in what order can I run these tasks so every prerequisite finishes first?" Press play above to watch Kahn's algorithm peel nodes off in a valid order.

Kahn's algorithm repeatedly takes a node with no remaining incoming edges (indegree 0), appends it to the order, and removes its outgoing edges - which may free up new indegree-0 nodes. It only works on a DAG: if a cycle exists, some nodes never reach indegree 0 and no valid order exists. It runs in O(V + E) time.

Time & space complexity

MeasureComplexityNotes
TimeO(V + E)Each node emitted once, each edge removed once
SpaceO(V)Indegree counts + ready set + order
RequiresA DAGCycles have no topological ordering
ResultNot uniqueMany valid orders can exist

Step by step (Kahn's algorithm)

StepWhat happens
1Compute the indegree (incoming edge count) of every node.
2Collect all nodes with indegree 0 into a ready set.
3Take a ready node, append it to the output order.
4Decrement the indegree of each of its successors.
5Any successor that reaches indegree 0 joins the ready set.
6Repeat until the ready set is empty.

Worked example

Sorting the DAG with edges A→C, B→C, C→D, C→E, D→F, E→F (starting indegrees A:0 B:0 C:2 D:1 E:1 F:2):

StepReady setOrderAction
0{A, B}[]A and B start with indegree 0, so both are ready.
1{B}[A]Emit A; its edge A→C drops C's indegree 2 → 1.
2{C}[A, B]Emit B; its edge B→C drops C 1 → 0, so C becomes ready.
3{D, E}[A, B, C]Emit C; edges C→D and C→E drop D and E to 0, both become ready.
4{E}[A, B, C, D]Emit D; its edge D→F drops F's indegree 2 → 1.
5{F}[A, B, C, D, E]Emit E; its edge E→F drops F 1 → 0, so F becomes ready.
6{}[A, B, C, D, E, F]Emit F; ready set is empty and all 6 nodes are ordered - done.

When to use topological sort

Use it whenAvoid it when
You need an order that respects dependencies (build steps, package installs, course prerequisites).The graph is undirected - topological order is only defined for directed graphs.
The graph is a DAG and you want any one valid linear ordering.The graph may contain cycles and you need a total order anyway (there is none).
You want to detect cycles cheaply - a failed topological sort proves one exists.You need the shortest or optimal ordering by some weight; plain topological sort ignores weights.
You will process the ordering once in O(V + E).Edges change constantly and you must re-sort on every update, where an incremental structure fits better.

Topological Sort code

A clean, runnable Topological Sort implementation in Python, JavaScript, Java, C++, C. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.

Topological Sort code in Python

Python
1from collections import deque2
3
4def topological_sort(graph):5    # Kahn's algorithm: repeatedly remove nodes with no incoming edges6    in_degree = {node: 0 for node in graph}7    for node in graph:8        for neighbor in graph[node]:9            in_degree[neighbor] += 110    queue = deque(node for node in graph if in_degree[node] == 0)11    order = []12    while queue:13        node = queue.popleft()14        order.append(node)15        for neighbor in graph[node]:16            in_degree[neighbor] -= 117            if in_degree[neighbor] == 0:18                queue.append(neighbor)19    if len(order) != len(graph):20        raise ValueError("Graph has a cycle, no topological order")21    return order22
23
24graph = {25    "shirt": ["tie", "jacket"],26    "tie": ["jacket"],27    "pants": ["shoes", "jacket"],28    "socks": ["shoes"],29    "shoes": [],30    "jacket": [],31}32
33print(" -> ".join(topological_sort(graph)))
Run this code in the Python Playground

Topological Sort FAQ

What is a topological sort used for?

It orders tasks so every dependency comes before the thing that needs it. Real uses include build systems and package managers (compile dependencies first), course scheduling with prerequisites, and spreadsheet formula evaluation order.

What is the time complexity of topological sort?
Both Kahn's algorithm and the DFS-based approach run in O(V + E) time, since each node is processed once and each edge is examined once. They use O(V) extra space.
Why does topological sort require a DAG?
A directed cycle creates a contradiction: if a must come before b and b must come before a, no linear order satisfies both. So a topological ordering exists if and only if the graph is a directed acyclic graph. Kahn's algorithm detects a cycle when it finishes before emitting every node.
What is the difference between Kahn's algorithm and DFS topological sort?
Kahn's algorithm is iterative and BFS-like: it repeatedly removes indegree-0 nodes, which makes cycle detection and ordering fully explicit. The DFS approach recursively visits nodes and prepends each one to the order as its recursion finishes, producing the reverse of the finish times. Both are O(V + E); Kahn's avoids deep recursion and reports the ready set naturally, while DFS is often shorter to write.
When should I use topological sort instead of a regular sort?
Use topological sort when the order is defined by dependencies between items rather than by a comparable key. A regular comparison sort like O(n log n) mergesort orders by value; topological sort orders by "must come before" edges, and unlike a comparison sort it can produce many valid answers for the same input.
Is the result of a topological sort unique?

Usually not. Whenever two or more nodes are ready (indegree 0) at the same time, you may emit them in any order, so most DAGs admit several valid topological orderings. The order is unique only when there is exactly one ready node at every step, which happens when the DAG forms a single chain (a Hamiltonian path).

Related resources

More visualizations

Coddy programming languages illustration

Master algorithms with Coddy

Get started