A directed acyclic graph (DAG) is a directed graph with no directed cycles. Its acyclic structure makes dependency ordering possible: topological sort can arrange vertices so required relationships are respected. section 1.4 section 1.5
A DAG matters because its structural properties enable specific operations:
- Topological sort produces a flat ordering of vertices based on dependency links. section 1.4 section 1.4.1
- The worked algorithm tracks in-degree counts, stores zero-in-degree vertices in a queue, processes them, and updates dependent counts. section 1.4.1
- Acyclicity is a precondition rather than a minor graph detail; the ordering algorithm applies only to directed acyclic graphs. section 1.4
Job dependencies
Represent jobs as vertices and dependency links as directed edges. The example orders D before C, C before B, and all of them before A, giving a valid execution sequence derived from the dependency structure. section 1.4.1
















