Topological Sort — Process Zero In-degree First

Build tools and package managers solve the same problem before running anything: in what order should dependent tasks run so that every prerequisite finishes before its dependents start. While organizing the graph topic I wrote the standard answer, topological sort, as a template, and the core loop turned out simpler than expected. Take a node with no remaining dependencies, process it, and erase its outgoing edges. That loop alone produces the order, and if the order comes up short, there is a cycle.

A topological sort arranges the nodes of a directed graph so that for every edge u → v, u comes before v. The premise is a DAG (Directed Acyclic Graph). With a cycle, the nodes are each other’s prerequisites and no valid order exists.

Kahn’s BFS

Kahn’s BFS takes the in-degree as its criterion. The in-degree is the number of incoming edges, which is the number of prerequisites not yet processed. A node with in-degree 0 has no remaining dependencies, so it can be processed now. Processing a node erases its outgoing edges, which lowers the in-degree of its neighbors, and any neighbor that reaches 0 becomes the next candidate.

flowchart LR
    A["0"] --> B["1"]
    A --> C["2"]
    B --> D["3"]
    C --> D

In the graph above, node 0 is the only one with in-degree 0. Processing 0 drops the in-degree of 1 and 2 to 0, so both enter the queue, and 3 follows once they are processed. The result is [0, 1, 2, 3] or [0, 2, 1, 3] — when several nodes hit in-degree 0 at the same time, more than one valid order exists.

from collections import defaultdict, deque


def topological_sort(n, edges):
    indegree = [0] * n
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    queue = deque(node for node in range(n) if indegree[node] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)

    return order if len(order) == n else []

The initial queue takes every node with in-degree 0. Assuming a single starting point and enqueueing only the first one misses independent components. Every node enters the queue once and every edge participates in one decrement, so the complexity is O(V + E). When the extraction order matters (the lexicographically smallest result, for instance), swap the queue for a heap.

Cycle Detection

The last line, len(order) == n, doubles as cycle detection. Nodes inside a cycle are each other’s prerequisites, so none of them ever reaches in-degree 0. When the queue is empty but fewer than N nodes were processed, the remaining nodes are part of a cycle or depend on one. A single count comparison settles the verdict without tracking visit states.

Course Schedule (LeetCode 207) is exactly this decision problem: N courses, prerequisite pairs, can all of them be taken? In the skeleton above, count processed nodes instead of collecting the order and return whether the count equals N. The follow-up, Course Schedule II (LeetCode 210), asks for the order itself, and the same skeleton answers it by returning the order instead.

The trap in both problems is edge direction. prerequisites[i] = [a, b] means “take b before a,” so the edge is b → a. Reversing it flips the in-degree computation and produces wrong answers. Most mistakes in this problem type happen while translating the statement’s precedence into edge direction.

DFS Post-order

A topological sort can also come from DFS. Visit all children of a node first, then append the node itself, and reverse the whole list at the end. Children are always appended before their parent, so the reversal puts prerequisites first.

A boolean visited array is not enough for cycle detection. When an already-visited node shows up again, it might be a cycle or it might be a node another path already finished, and a boolean cannot tell the two apart — it misjudges acyclic graphs as cyclic. So the state splits into three: unvisited, in progress (on the current recursion path), and done. Meeting an in-progress node again means a cycle; a done node is simply skipped.

from collections import defaultdict


def topological_sort_dfs(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)

    UNVISITED, IN_PROGRESS, DONE = 0, 1, 2
    state = [UNVISITED] * n
    order = []

    def visit(u):
        if state[u] == IN_PROGRESS:
            return False
        if state[u] == DONE:
            return True
        state[u] = IN_PROGRESS
        for v in graph[u]:
            if not visit(v):
                return False
        state[u] = DONE
        order.append(u)
        return True

    for node in range(n):
        if state[node] == UNVISITED and not visit(node):
            return []
    return order[::-1]

Recursion depth can grow as deep as the node count. Python’s default recursion limit is low, so large graphs need a raised limit or an iterative rewrite.

Selection Criteria

When Kahn’s BFS fits:

• Cycle detection and order production should share one skeleton
• The implementation should stay iterative and safe on deep graphs
• The extraction priority needs control, such as lexicographic order

When DFS post-order fits:

• A DFS traversal already exists and the sort comes along with it
• The cycle path itself must be reconstructed, not just detected
• The traversal doubles for other post-order computations

A build tool finishing dependencies before its target, a package manager deciding installation order — both run the same loop. Take the nodes with no remaining dependencies, lower the neighbors’ in-degrees as you go, and declare a circular dependency when not everything comes out. What I liked most while organizing this template is that a single criterion, in-degree 0, settles both the order and the cycle verdict.