Topological Sort —
Order tasks so prerequisites come first.
Topological sort produces a valid execution order for a directed acyclic graph (DAG) — every edge A→B means A must come before B. Kahn's algorithm builds that order using in-degree counts and a queue, no recursion needed. Watch each node's in-degree count down to zero and get released onto the result on LearnBug, one dependency at a time.
What is Topological Sort?
A linear ordering of a DAG's nodes such that for every directed edge A→B, A appears before B in the ordering. It only exists if the graph has no cycles — a cycle would mean A must come before B, and B must come before A, which is impossible to satisfy.
Why visualization helps
In-degree bookkeeping is easy to get backwards on paper — which count goes down, and when a node becomes "ready." LearnBug shows every node's in-degree live and highlights the exact moment it hits zero and joins the queue, so "released once all prerequisites are done" is something you watch happen, not something you have to trust the code did.
Kahn's algorithm (BFS) vs DFS postorder
Kahn's Algorithm — BFS ✓
Repeatedly process nodes with in-degree 0, decrementing their neighbors' in-degrees. Naturally detects cycles: leftover nodes at the end mean one exists.
DFS Postorder
Run DFS, and after fully exploring a node's descendants, push it onto a stack. Reversing that stack gives a valid topological order.
Not always unique
If multiple nodes are simultaneously ready (in-degree 0), any order between them is valid — a DAG can have several correct topological orders.
Kahn's algorithm on A→C, B→C, C→D
Compute in-degrees: A=0, B=0, C=2, D=1 — enqueue everything at 0
A and B have no incoming edges, so they're immediately "ready" — no prerequisites — and both start in the queue.
Pop A, decrement C's in-degree to 1 — C still has a pending prerequisite (B)
A only points to C. C's in-degree drops from 2 to 1, but that's not zero yet — B hasn't been processed, so C isn't ready.
Pop B, decrement C's in-degree to 0 — C becomes ready and enqueues
Now that both A and B are processed, C's last prerequisite is satisfied. C's in-degree hits zero and it joins the queue.
Pop C, decrement D's in-degree to 0 — D becomes ready, then finishes
C's only edge is to D. D's in-degree drops to 0, gets enqueued, then popped — it has no outgoing edges, so the queue empties.
Return: [A, B, C, D] ✓ every prerequisite processed before what depends on it
Kahn's algorithm with a queue
graph = {
"A": ["C"],
"B": ["C"],
"C": ["D"],
"D": [],
}
in_degree = {node: 0 for node in graph}
for node in graph:
for neighbor in graph[node]:
in_degree[neighbor] += 1
queue = [node for node in graph if in_degree[node] == 0]
order = []
while queue:
node = queue.pop(0)
order.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
if len(order) < len(graph):
# leftover nodes never hit in-degree 0 — a cycle exists
print("Cycle detected — no valid ordering")
else:
print(order)Complexity Notes
Frequently asked questions
What happens if the graph has a cycle?
No valid topological order exists. In Kahn's algorithm, nodes inside the cycle never reach in-degree 0 (each depends on another node still waiting), so they're never enqueued. Checking whether the final order's length equals the number of nodes is the standard way to detect this.
Is the topological order always unique?
No. Whenever more than one node has in-degree 0 at the same time, any order between them is valid — in the walkthrough above, A and B could have swapped positions and the result would still be correct. A DAG can have many valid topological orderings.
How does the DFS-based version differ from Kahn's algorithm?
DFS postorder pushes each node onto a stack only after all of its descendants have been fully explored, then reverses the stack for the final order. It uses recursion and implicit backtracking instead of in-degree bookkeeping and a queue — same result, different mechanism, same O(V+E) cost.
What's a real example of topological sort in use?
Course scheduling with prerequisites, build systems compiling files in dependency order, package manager install order, and spreadsheet formula recalculation order are all topological sort applied to a dependency DAG.
Watch each in-degree count down to zero
Paste your topological sort into LearnBug and see nodes get released one at a time.