Topological Sorting (Ordering with Dependencies)

Topological sort orders a DAG so every edge goes forward—used for build order, prerequisites, and course schedules.

Why this shows up in the real world

Maps & routing, social networks, and dependency systems are modeled as graphs—vertices are places or tasks, edges are roads or prerequisites.

Core idea (explained for students)

Kahn: peel nodes with indegree 0. DFS: push node after visiting outgoing edges (reverse finish order). Cycle exists iff sort length < n.

Try this in Python

from collections import deque


def topo_sort(n: int, edges: list[tuple[int, int]]) -> list[int]:
    indeg = [0] * n
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order: list[int] = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else []


print(topo_sort(4, [(0, 1), (0, 2), (1, 3), (2, 3)]))

Common mistakes

• Trying topo sort on cyclic graph.
• Off-by-one indegree updates.

Key takeaways

• Longest path on DAG = DP in topo order.
• Critical path = longest path in project DAG.