Topological Sort, Two Ways

A topological order on a DAG is any ordering of the vertices where every edge u → v has u before v. Build systems, course prerequisites, package managers, schedulers — all topological sorts in disguise.

There's no topological order if the graph has a cycle. The algorithms below detect that.

Method 1: Kahn's algorithm (BFS)

Repeatedly: pick a vertex with no incoming edges, output it, remove it from the graph.

from collections import deque

def kahn(graph, n):
    indeg = [0] * n
    for u in range(n):
        for v in graph[u]:
            indeg[v] += 1

    q = deque(u for u in range(n) if indeg[u] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    if len(order) != n:
        raise ValueError("graph has a cycle")
    return order

This is O(V + E). The cycle detection is free: if any vertex still has incoming edges at the end, the graph isn't a DAG.

Method 2: DFS with finishing times

Run DFS. Whenever you finish processing a node (i.e., return from its recursive call), prepend it to the output. The reverse of finishing order is a topological order.

def dfs_topo(graph, n):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
    order = []

    def visit(u):
        if color[u] == GRAY:
            raise ValueError("cycle detected")
        if color[u] == BLACK:
            return
        color[u] = GRAY
        for v in graph[u]:
            visit(v)
        color[u] = BLACK
        order.append(u)

    for u in range(n):
        if color[u] == WHITE:
            visit(u)
    return order[::-1]

The three-color scheme is the classic cycle-detection idiom: WHITE = unvisited, GRAY = on the current DFS path, BLACK = fully processed. If you ever traverse to a GRAY vertex, you've found a back-edge — a cycle.

Pick whichever fits the constraint

Kahn's algorithm is iterative and gives you a clean place to plug in priority (e.g., always process tasks with shorter duration first when ties exist). DFS-based topo sort is shorter to write and natural when you're already in a DFS-style traversal.