Topological Sort

Imagine registering for university courses. You can't take Calculus II before Calculus I. You can't take Algorithms before Data Structures. Every course has prerequisites, and you need to figure out a valid order to take them all.

That's exactly what topological sort does: given a set of tasks with dependencies ("A must come before B"), it finds an ordering where every dependency is satisfied. All edges in the result point forward — no item ever appears before something it depends on.

The One Hard Rule: No Cycles

Topological sort only works on a Directed Acyclic Graph (DAG) — a directed graph with no cycles. Why? If course A requires B, and B requires A, there's no valid order to take them. A cycle makes topological ordering impossible. Any algorithm that detects this impossible case is doing you a favor.

Kahn's Algorithm (BFS with In-Degree Tracking)

Think of in-degree as the number of prerequisites a task still has. Tasks with in-degree 0 have no unmet prerequisites — they're ready to go.

Kahn's algorithm:

Compute the in-degree of every vertex.
Enqueue all vertices with in-degree 0 into a queue.
Repeatedly dequeue a vertex u, add it to the result, and decrement the in-degree of every neighbor v. If v's in-degree drops to 0, enqueue it.
If the result contains all V vertices, it's a valid topological order. If not — a cycle exists and no valid order is possible.

The cycle detection is built-in and free: vertices stuck in a cycle never reach in-degree 0, so they're never added to the result.

DFS-Based Approach (Reverse Post-Order)

Run a standard DFS. When a vertex's DFS call returns (all its descendants have been fully explored), push it onto a stack. When DFS completes for all vertices, read the stack top-to-bottom — that's a valid topological order.

Why does this work? If there's an edge u → v, then DFS fully finishes v before finishing u (u's call can't return until all descendants are done). So u ends up deeper in the stack — earlier in the popped order.

Applications

Topological sort is everywhere: build systems (compile files in dependency order), package managers (install libraries before the code that uses them), course scheduling (take prerequisites first), and DP on DAGs (process states in reverse topological order so all sub-problems are ready).

Kahn's Algorithm and DFS-based Topological Sort

from collections import deque

def kahns_topo(n, edges):
    """Kahn's BFS-based topological sort. Returns [] if cycle detected."""
    adj = [[] for _ in range(n)]
    indegree = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indegree[v] += 1
    queue = deque(u for u in range(n) if indegree[u] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    return order if len(order) == n else []  # empty = cycle

def dfs_topo(n, edges):
    """DFS-based topological sort."""
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
    visited = [False] * n
    stack = []
    def dfs(u):
        visited[u] = True
        for v in adj[u]:
            if not visited[v]:
                dfs(v)
        stack.append(u)
    for u in range(n):
        if not visited[u]:
            dfs(u)
    return stack[::-1]

# 0->1, 0->2, 1->3, 2->3
edges = [(0,1),(0,2),(1,3),(2,3)]
print(kahns_topo(4, edges))  # [0, 1, 2, 3] or [0, 2, 1, 3]
print(dfs_topo(4, edges))    # [0, 2, 1, 3] or similar valid order

Output

[0, 1, 2, 3]
[0, 2, 1, 3]

Complexity

📋 Kahn's algorithm (BFS)Each vertex enqueued once; each edge processed once when its source is dequeued

Linear in graph size\(O(V+E)\)

🔍 DFS-based sortStandard DFS — same cost as one full graph traversal

Linear in graph size\(O(V+E)\)

💾 SpaceIn-degree array + queue/stack, each \(O(V)\)

Proportional to vertices\(O(V)\)

🔄 Cycle detection (Kahn's)If result has fewer than V vertices, a cycle exists — no separate detection needed