Topological sorting

If task B must wait for A, a directed edge from A to B expresses the precedence. A topological order places every vertex in a sequence with all such edges pointing forward, providing one order consistent with the constraints.

Unconstrained tasks can trade positions, so the ordering need not be unique. It does not alone specify task duration, processor assignment, or actual starting times; those require a scheduling model beyond precedence.

References: [1]

If A precedes B, B precedes C, and C precedes A, no linear sequence satisfies all three strict constraints. A directed graph has a topological ordering exactly when it has no directed cycle.

An implementation must therefore report impossibility rather than silently discarding an edge and labeling arbitrary output valid. A cycle can reveal inconsistent dependency records or a relationship needing a different model; interpretation starts with what the edges mean.

References: [1]

One construction checks for directed cycles and uses depth-first search. Recording a vertex when its descendant work finishes produces postorder; reversing that order produces a topological sort of a DAG. Reversal without the acyclic condition does not provide the same guarantee.

With adjacency lists, cycle detection and traversal fit within O(V+E) time. The procedure must also cover vertices outside one root’s reachable region rather than mistaking a partial ordering of one component for complete processing.

References: [1]