Topological Sort and Dependency Order

Build A before B because B depends on A" is a dependency graph. Topological sort produces the execution order — the reason Makefiles, CI pipelines, and course planners work.

Kahn's algorithm (BFS-based)

def topo_sort(graph):
    in_degree = {n: 0 for n in graph}
    for n in graph:
        for m in graph[n]:
            in_degree[m] += 1
    queue = deque([n for n, d in in_degree.items() if d == 0])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for m in graph[node]:
            in_degree[m] -= 1
            if in_degree[m] == 0:
                queue.append(m)
    return order if len(order) == len(graph) else None   # cycle → impossible

Nodes with no dependencies go first; removing them reduces their dependents' in-degree. If the order is shorter than the graph, a cycle exists — "A depends on B, B depends on A" — which is a deadlock in build systems and circular-import bugs in code.

DFS-based topological sort

def dfs_topo(node, visited, order):
    if node in visited: return
    visited.add(node)
    for m in graph[node]:
        dfs_topo(m, visited, order)
    order.append(node)          # append *after* children — deepest first

Same result, different mechanics — the stack pops a node only after all its descendants are in the order.

::exercise(cycle-detector)

Field notes

• graphlib.TopologicalSorter in Python stdlib, kahn or tarjan in every language's graph lib — don't hand-roll unless learning.
• A topological sort isn't unique — multiple valid orders exist (any valid order works; sometimes you want the lexicographically smallest, which needs a priority queue).
• The cycle-detection property is the feature: "can't topologically sort" == "circular dependency".