A directed acyclic graph (DAG) is a graph whose edges have direction and which contains no directed cycles, so no path returns to its starting vertex. This structure naturally encodes ordered dependencies, enabling a topological ordering of vertices and making DAGs foundational for scheduling, dependency resolution, version histories, and certain distributed-ledger designs. The absence of cycles guarantees that dependency chains terminate, which underpins many algorithms built on top of the structure.
Overview
- A DAG combines directed edges with the acyclicity constraint, so dependencies always point forward and never loop back.
- Topological sorting produces a linear ordering consistent with all edge directions, which is the basis for scheduling dependent tasks.
- Build systems, data pipelines, and version-control histories model their dependency relationships as DAGs.
- Some distributed ledgers replace the linear chain of blocks with a DAG of transactions to allow concurrent appends.
Key aspects
- Acyclicity guarantees that dependency traversal terminates and a topological order exists.
- Vertices commonly represent tasks, commits, transactions, or data nodes.
- Edges encode precedence, parentage, or reference relationships.
- Git models commit history as a DAG of parent references.
- DAG-based ledgers contrast with linear blockchains and with the Merkle DAG content-addressing structure.
Applications
- Scheduling dependent jobs in Workflow Orchestration engines.
- Representing commit ancestry in distributed Version Control systems.
- Modelling data lineage and transformation pipelines.
- Structuring concurrent transactions in DAG-based distributed-ledger designs.