Topological Sort

Only works on DAGs

A topological sort orders nodes of a Directed Acyclic Graph (DAG) so that for every edge u -> v, u comes before v. It only exists if the graph has no cycle — think task scheduling where some tasks depend on others.

Kahn's algorithm (BFS)

Repeatedly remove nodes with in-degree 0, decrementing their neighbours' in-degree. If fewer than n nodes get removed, a cycle exists.

from collections import deque

def topo_sort(n, edges):
    g = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        g[u].append(v)
        indeg[v] += 1

    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)

    return order if len(order) == n else []  # [] means a cycle exists

DFS variant

Run DFS and push each node to a stack after visiting all its descendants (post-order). Reversing that stack gives a valid topological order.

def topo_dfs(n, g):
    visited = [False] * n
    stack = []

    def dfs(u):
        visited[u] = True
        for v in g[u]:
            if not visited[v]:
                dfs(v)
        stack.append(u)

    for u in range(n):
        if not visited[u]:
            dfs(u)
    return stack[::-1]

Where it shows up

Build systems (compile order), course prerequisites, package managers resolving dependencies, and detecting cycles in a dependency graph all reduce to topological sort.