Topological Sort
DSA · Graphs
Theory
A topological sort orders the vertices of a directed acyclic graph (DAG) so that every edge goes from earlier to later in the order. Kahn's algorithm counts incoming edges (in-degree) for each vertex, starts with vertices that have none, and repeatedly removes them while decreasing their neighbours' in-degrees. If not every vertex is output, the graph has a cycle. It runs in O(V + E).
Why we use it
It produces a valid order for tasks that depend on each other.
When to use it
Use it for build systems, course prerequisites, data pipeline task ordering (Airflow DAGs), spreadsheet recalculation and package installation.
How it works
- Count in-degree of every node
- queue = nodes with in-degree 0
- Queue empty? Yes: Done. No: Pop u, add to order.
- For each edge u -> v: in-degree[v] -= 1; if 0 push v
- Order has all nodes? Yes: Valid order. No: Graph has a cycle.
Syntax
indeg = count incoming edges
queue = vertices with indeg 0
while queue:
v = pop; output v
for nb in graph[v]:
indeg[nb] -= 1
if indeg[nb] == 0: push nb
Time: O(V + E)Example
from collections import deque
tasks = {
"extract": ["clean"],
"clean": ["join", "validate"],
"validate": ["load"],
"join": ["load"],
"load": ["report"],
"report": [],
}
indeg = {t: 0 for t in tasks}
for t in tasks:
for nxt in tasks[t]:
indeg[nxt] += 1
q = deque([t for t in tasks if indeg[t] == 0])
order = []
while q:
t = q.popleft()
order.append(t)
for nxt in tasks[t]:
indeg[nxt] -= 1
if indeg[nxt] == 0:
q.append(nxt)
print("Run order:", " -> ".join(order))Key points
- Only works on DAGs
- Kahn's algorithm uses in-degrees
- Missing vertices in the output mean a cycle
- O(V + E) time