Topological Sorting for Dependency Problems

Model dependencies as a DAG

Represent a prerequisite relation as a directed edge from the prerequisite to the dependent task. A valid schedule is a sequence where each edge points forward. If the graph contains a directed cycle, every task in that cycle depends indirectly on itself, so no valid order exists.

A topological order is not necessarily unique. If several nodes currently have no prerequisites, any of them can be chosen next. This means the algorithm answers whether an order exists and returns one valid order—not necessarily a uniquely “best” schedule.

Kahn's algorithm: repeatedly remove ready tasks

Compute each vertex's indegree, the number of incoming edges. Put every zero-indegree vertex in a queue. Remove one, append it to the order, and decrement the indegree of its outgoing neighbors. Any neighbor that reaches zero is ready to process.

from collections import deque

def topological_order(graph, indegree):
    degree = indegree[:]
    ready = deque(i for i, d in enumerate(degree) if d == 0)
    order = []
    while ready:
        node = ready.popleft()
        order.append(node)
        for neighbor in graph[node]:
            degree[neighbor] -= 1
            if degree[neighbor] == 0:
                ready.append(neighbor)
    return order if len(order) == len(graph) else None

Returning fewer than V vertices means some vertices remain in cycles (or depend on cycles). With adjacency lists, time is O(V + E) and space is O(V).

DFS alternative and common uses

DFS topological sorting appends a vertex after all of its outgoing dependencies have been explored, then reverses the finish order. To detect cycles during that traversal, distinguish an active recursion path from a fully completed node; reaching an active node means there is a cycle.

• Course scheduling and build systems.
• Ordering compiler steps, migrations, and task pipelines.
• Evaluating expressions or dependencies whose prerequisites must be computed first.

Do not apply topological sorting to an undirected graph without first converting its relationships into meaningful directed prerequisites. The algorithm's order depends on edge direction.