Directed Acyclic Graph
Subject: Computer and Technology noun /dɪˈrɛk.tɪd ˌeɪˈsaɪ.klɪk ɡræf/ 1 definition
- data-structures
- graph-theory
- algorithms
- computer-science
-
Definition (noun)
Entry #47 · UpdatedA Directed Acyclic Graph (DAG) is a graph data structure composed of vertices (nodes) connected by directed edges (one-way links) such that following edges in their assigned direction never forms a closed loop back to a previously visited vertex. By prohibiting circular dependencies, a DAG establishes a partial order across elements and guarantees at least one topological sorting—a linear sequence in which the source vertex of every directed edge precedes its target. Unlike general directed graphs that permit feedback cycles, or standard rooted trees that restrict each non-root node to a single parent, a DAG allows nodes to have multiple parents while ensuring traversal and dependency resolution remain deterministic.
Common Forms
Dependency and Workflow DAGs: Model prerequisite relationships in build systems (such as Make and Bazel), package managers, and data orchestrators (such as Apache Airflow), enabling parallel execution of independent branches and safe topological scheduling.
Expression and Computation DAGs: Represent algebraic operations in optimizing compilers and tensor operations in machine-learning frameworks, supporting common subexpression elimination, operator fusion, and automatic differentiation across shared intermediate results.
Merkle DAGs: Link content-addressed nodes using cryptographic hashes—powering systems such as Git and IPFS—so each node's identifier verifies both its own payload and every linked node reachable from it.
Polytrees: Form a structural subclass of DAGs whose underlying undirected graph contains no cycles, allowing nodes to have multiple parents without alternate parallel paths—a property used for exact probabilistic inference in Bayesian networks.
Example
In an Apache Airflow analytics pipeline,
extract_ordersandextract_usersrun in parallel before feeding a sharedjoin_customer_metricstask, which then triggersbuild_dashboardandtrain_churn_model. Because every dependency edge flows strictly forward without cycles, the scheduler executes the two extraction branches concurrently, waits for both upstream inputs before running the join, and guarantees the workflow terminates cleanly.