Ordering tasks respecting dependency constraints
A topological sort arranges directed acyclic graph (DAG) nodes into a linear order such that every edge points forward. If task B depends on task A, A must appear before B in the topological order. This is essential for build systems, package managers, and workflow schedulers where prerequisites must complete before dependents can start.
Kahn's algorithm, the most intuitive approach, iteratively removes nodes with zero in-degree (no incoming edges). Each removal reduces in-degree of its successors. If a node never reaches zero in-degree, a cycle exists and no valid topological order is possible. This provides both a solution and a cycle-detection mechanism.
Implementation and cycle detection
Kahn's algorithm uses a queue: initialize in-degrees for all nodes, enqueue all zero in-degree nodes, then iteratively dequeue, decrement in-degrees of neighbors, and enqueue newly zeroed nodes. The output order is topological. If fewer than n nodes are processed, a cycle is present and the sort is impossible.
Depth-first search offers an alternative: perform DFS from each unvisited node, pushing to a stack only after visiting all descendants. Reversing the stack yields a topological order. Both approaches run in O(V + E) time and handle the cycle-detection requirement intrinsically.