# Directed acyclic graph

> Source: https://aiwiki.ai/wiki/directed_acyclic_graph
> Updated: 2026-11-18
> Fact-checked: 2026-11-18
> Categories: Algorithms, Computer Science, Machine Learning, Mathematics
> License: CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) - attribute to "AI Wiki (aiwiki.ai)"
> Cite as: AI Wiki. "Directed acyclic graph." aiwiki.ai, 18 Nov 2026. https://aiwiki.ai/wiki/directed_acyclic_graph
> From AI Wiki (https://aiwiki.ai), the free encyclopedia of artificial intelligence. Reuse freely with attribution.

A **directed acyclic graph** (**DAG**) is a directed graph that contains no directed cycle: no path that follows the edges in their direction ever returns to the vertex it started from [1]. The structure is also called an acyclic directed graph or an oriented acyclic graph [1]. Every DAG has a topological ordering, a way of lining up its vertices so that all edges point the same way, so the vertices can always be processed with each one coming after everything it depends on [2]. In [machine learning](https://aiwiki.ai/wiki/machine_learning) DAGs appear in several roles: as the graph of a [Bayesian network](https://aiwiki.ai/wiki/bayesian_network) [3], as the causal diagram in [causal inference](https://aiwiki.ai/wiki/causal_inference) [3][4], as the [computational graph](https://aiwiki.ai/wiki/computational_graph) that deep learning frameworks differentiate [5], and as the dependency graph of data and training pipelines [21].

Learning a DAG from data is hard. Finding a high-scoring Bayesian network structure is NP-hard even with large samples, and the number of possible DAGs grows superexponentially with the number of nodes [7][8]. Continuous-optimization methods such as NOTEARS were designed to avoid that combinatorial search [8], and graph neural networks have been built specifically for DAG-shaped inputs [9][10].

<figure>
<img src="/images/media-2026-11-18-directed_acyclic_graph-828dd47474c5.png" alt="Directed graph of eleven numbered nodes with arrows pointing downward and no cycles" width="1200" height="965" />
<figcaption>An example of a directed acyclic graph: every arrow points downward and no path returns to its starting node. Johannes Rössel, via <a href="https://commons.wikimedia.org/wiki/File:Directed_acyclic_graph_2.svg">Wikimedia Commons</a>, Public domain.</figcaption>
</figure>

## Definition and basic properties

A directed graph $G = (V, E)$ consists of a set of vertices $V$ and a set of ordered pairs of vertices $E$, the edges, each written $u \to v$. A **directed cycle** is a path $v_0 \to v_1 \to \cdots \to v_k$ with $v_k = v_0$. A DAG is a directed graph in which no such path exists [1][2].

Two kinds of vertex are named in every DAG. A **source** has no incoming edges and a **sink** has no outgoing edges. Every DAG has at least one source and at least one sink, and it may have many of each: in a graph with $n$ vertices and no edges, every vertex is both [2].

### Topological ordering

A **topological ordering** of a directed graph is a total order of its vertices in which $u$ comes before $v$ for every edge $u \to v$; drawn on a horizontal line, all edges point from left to right [2]. A graph with a directed cycle has no such ordering, because the rightmost vertex of the cycle would need an edge pointing left. Conversely, every DAG has at least one topological ordering, so a directed graph is acyclic exactly when it can be topologically ordered [2]. The ordering need not be unique [11].

Topological sorting can also be described as arranging items "according to a partial order" when some pairs of items are not comparable [12]. Reachability in a DAG supplies that order: one vertex precedes another when a directed path leads from the first to the second. The 2021 DAGNN paper describes this partial ordering as the inductive bias its architecture is built around [10].

### Relation to other graphs

Every directed graph, cyclic or not, has an associated DAG. Contracting each strongly connected component (a maximal set of vertices that can all reach one another) to a single vertex yields the **strong component graph**, also called the condensation, and that graph is always acyclic. A directed graph is itself a DAG if and only if each of its strong components contains a single vertex [2].

Acyclicity can also be read off the adjacency matrix. For a binary adjacency matrix $B \in \{0,1\}^{d \times d}$, the trace $\operatorname{tr}(B^k)$ counts the closed walks of length $k$ in the graph, so $B$ describes a DAG exactly when $(B^k)_{ii} = 0$ for every vertex $i$ and every $k \geq 1$ [8]. Zheng and colleagues used this fact to show that $B$ is a DAG if and only if $\operatorname{tr}(e^{B}) = d$, where $e^{B}$ is the matrix exponential, a characterization that underlies the NOTEARS method described below [8].

### Counting DAGs

The number of DAGs on $n$ labeled vertices is sequence A003024 in the On-Line Encyclopedia of Integer Sequences, whose references include Robert W. Robinson's 1973 chapter "Counting labeled acyclic digraphs" [13]. With $a(0) = 1$, the counts satisfy

$$a(n) = \sum_{k=1}^{n} (-1)^{k+1} \binom{n}{k} \, 2^{k(n-k)} \, a(n-k).$$

| Labeled vertices $n$ | Number of DAGs |
|---|---|
| 1 | 1 |
| 2 | 3 |
| 3 | 25 |
| 4 | 543 |
| 5 | 29281 |
| 6 | 3781503 |
| 7 | 1138779265 |
| 8 | 783702329343 |
| 9 | 1213442454842881 |

The counts grow quickly: nine labeled vertices already admit more than $10^{15}$ DAGs [13]. The NOTEARS paper describes the growth as superexponential in the number of nodes [8].

<figure class="embedvideo">
<iframe src="https://www.youtube-nocookie.com/embed/Sdw8_0RDZuw" title="2.6.1 DAGs: Video"></iframe>
<figcaption>"2.6.1 DAGs: Video", video from MIT OpenCourseWare, published September 12, 2016. <a href="https://www.youtube.com/watch?v=Sdw8_0RDZuw">Watch on YouTube</a>.</figcaption>
</figure>

## Algorithms on DAGs

### Detecting cycles

Whether a directed graph is a DAG can be decided in $O(V + E)$ time with depth-first search. One version computes a postordering of the vertices and checks every edge: if some edge $u \to v$ has $u$ finishing before $v$, the graph contains a directed path from $v$ back to $u$ and therefore a cycle. Another version marks vertices as active while the search is inside them and reports a cycle as soon as it meets an edge into an active vertex [2].

### Topological sorting

Two classic algorithms produce a topological ordering in linear time:

| Algorithm | Idea | Running time |
|---|---|---|
| Depth-first search | Reverse any postordering of the vertices | $O(V + E)$ [2] |
| Kahn's algorithm (1962) | Repeatedly remove a source, output it, and lower the in-degree of its out-neighbors | $\Theta(V + E)$ with adjacency lists [14] |

The depth-first method works because, in a DAG, every edge $u \to v$ has $u$ finishing after $v$, so reversing the postorder puts every edge in left-to-right order [2]. Kahn's method, published by A. B. Kahn in *Communications of the ACM* in November 1962 under the title "Topological sorting of large networks", keeps a set of current sources and an in-degree count for each vertex. When a vertex is removed, only its out-neighbors can become new sources. If the set of sources runs out before every vertex has been output, the graph is not a DAG [14][15]. With an adjacency matrix rather than adjacency lists, the same procedure takes $\Theta(V^2)$ time [14].

### Longest paths and dynamic programming

Some problems that are hard on general graphs become easy on DAGs. Finding the longest path between two vertices is NP-hard in general directed graphs, but in a DAG it can be computed in linear time by evaluating the recurrence

$$\mathrm{LLP}(v) = \max_{v \to w \in E} \bigl(\ell(v \to w) + \mathrm{LLP}(w)\bigr), \qquad \mathrm{LLP}(t) = 0,$$

where $\ell$ is the edge weight and $t$ the target vertex, in reverse topological order [2].

The same idea explains [dynamic programming](https://aiwiki.ai/wiki/dynamic_programming) in general. The dependency graph of a recurrence, with one vertex per subproblem and an edge from one subproblem to another when evaluating the first requires the second, must be acyclic for the recursion to terminate, and a dynamic programming algorithm evaluates that DAG in reverse topological order so that each subproblem is solved after the subproblems it depends on. Jeff Erickson's *Algorithms* textbook states it as "every dynamic programming algorithm is equivalent to a postorder traversal of the dependency graph of its underlying recurrence" [2]. Edit distance, subset sum and longest increasing subsequence can all be recast as shortest or longest path problems in such a DAG [2].

## DAGs in probabilistic modeling

### Bayesian networks

A Bayesian network is a DAG whose vertices are random variables, together with a conditional distribution for each variable given its parents. The graph encodes a factorization of the joint distribution. In [Judea Pearl](https://aiwiki.ai/wiki/judea_pearl)'s 1995 *Biometrika* paper, the factorization is written as

$$P(x_1, \ldots, x_n) = \prod_{i} P(x_i \mid \mathrm{pa}_i),$$

where $\mathrm{pa}_i$ are the values of the parents of $X_i$ in the graph [3]. Pearl described DAGs as "economical schemes for representing conditional independence assumptions" [3]. The independencies implied by the factorization can be read directly off the graph with the **d-separation** test. A set of variables $Z$ blocks a path between two variables if the path passes through a vertex where the arrows converge and neither that vertex nor any of its descendants is in $Z$, or through a non-converging vertex that is in $Z$. $Z$ d-separates two sets of vertices when it blocks every path between them, and the conditional independencies implied by the factorization correspond one to one with the d-separation statements of the graph [3].

### Causal diagrams

Given a causal reading, the same kind of graph becomes a model of interventions. In Pearl's formulation each variable is determined by its parents and an independent disturbance term,

$$X_i = f_i(\mathrm{pa}_i, \varepsilon_i), \qquad i = 1, \ldots, n,$$

and the causal links stand for autonomous physical mechanisms [3]. An external intervention that sets $X_i$ to a fixed value removes the factor $P(x_i \mid \mathrm{pa}_i)$ from the product above; graphically, the arrows into $X_i$ are deleted and the rest of the network is left intact [3].

The paper also sets out the **back-door criterion**, a graphical test for which covariates to adjust for that Pearl had first presented in 1993 [3]. A set $Z$ satisfies it relative to a treatment $X$ and an outcome $Y$ if no member of $Z$ is a descendant of $X$ and $Z$ blocks every path between $X$ and $Y$ that contains an arrow into $X$. When the criterion holds, the causal effect is identifiable from observational data through the adjustment formula [3]

$$P(y \mid \hat{x}) = \sum_{z} P(y \mid x, z) \, P(z).$$

Causal DAGs have become an established framework for causal inference in epidemiology, often used to choose covariate adjustment sets [16]. A 2021 review in the *International Journal of Epidemiology* found 234 applied health research articles published between 1999 and 2017 that reported using DAGs, which the review describes as an increasingly popular approach for identifying the confounding variables that need to be conditioned on. The largest DAG in each article averaged 12 nodes, 62% of the articles made at least one DAG available, and 48% reported the adjustment sets their DAGs implied [4]. The authors called the variation in reporting substantial and made recommendations for improving it [4]. DAGitty, a free web application for drawing and analyzing causal DAGs, and its R package can test whether a DAG is consistent with a dataset, enumerate DAGs that are statistically equivalent but causally different, and find adjustment sets that remain valid across them [16].

In machine learning fairness research, [counterfactual fairness](https://aiwiki.ai/wiki/counterfactual_fairness), proposed by Kusner, Loftus, Russell and Silva at NIPS 2017, builds on a causal model whose graph is assumed to be a DAG. A predictor is counterfactually fair toward an individual if its decision would be the same in a counterfactual world where the individual belonged to a different demographic group [17].

### Learning DAGs from data

Structure learning tries to recover the DAG itself from observations. Chickering, Heckerman and Meek showed in 2004 that identifying high-scoring Bayesian network structures is NP-hard even with large samples, and that it stays NP-hard under several restrictions, for example when each node may have at most $k$ parents for any $k \geq 3$ [7]. Classical score-based methods therefore search the combinatorial space of DAGs with heuristics such as greedy search or search over topological orderings [8].

NOTEARS (Zheng, Aragam, Ravikumar and Xing, 2018) replaced the discrete acyclicity constraint with a smooth equation over real weighted adjacency matrices $W \in \mathbb{R}^{d \times d}$. Its main result is that $W$ is a DAG if and only if

$$h(W) = \operatorname{tr}\left(e^{W \circ W}\right) - d = 0,$$

where $\circ$ is the elementwise (Hadamard) product. Squaring the entries makes the matrix nonnegative, so the closed-walk argument above still applies, and $h$ has the simple gradient $\nabla h(W) = \left(e^{W \circ W}\right)^{\top} \circ 2W$ [8]. Structure learning then becomes an equality-constrained continuous optimization problem, which the authors solve for linear structural equation models with a least-squares loss and an $\ell_1$ penalty using standard numerical solvers [8].

## DAGs in deep learning

### Computational graphs and automatic differentiation

Deep learning frameworks record computations as graphs and differentiate them. [PyTorch](https://aiwiki.ai/wiki/pytorch)'s autograd tutorial states that autograd keeps a record of tensors and executed operations "in a directed acyclic graph (DAG) consisting of Function objects", in which the leaves are the input tensors and the roots are the output tensors [5]. During the forward pass, autograd runs each operation and stores the operation's gradient function in the DAG; calling `.backward()` on a root traces the graph back to the leaves, applying the chain rule and accumulating gradients in each leaf tensor's `.grad` attribute [5]. In PyTorch the DAG is dynamic: after each `.backward()` call autograd starts a new graph, which is what allows control flow statements inside a model and lets the shape, size and operations change from one iteration to the next [5]. This record is the computational graph behind reverse-mode [automatic differentiation](https://aiwiki.ai/wiki/automatic_differentiation) and [backpropagation](https://aiwiki.ai/wiki/backpropagation); [graph execution](https://aiwiki.ai/wiki/graph_execution) and [eager execution](https://aiwiki.ai/wiki/eager_execution) describe the two ways frameworks build and run it.

Not every framework graph is acyclic. [TensorFlow](https://aiwiki.ai/wiki/tensorflow) represents computation, shared state and the operations that mutate that state as a dataflow graph, and implements loops inside the graph with Switch and Merge primitives [18]. The 2018 EuroSys paper on TensorFlow's dynamic control flow states that the while-loop graph "is cyclic so the result of the loop body can go from one iteration to the next" [19].

[Recurrent neural networks](https://aiwiki.ai/wiki/recurrent_neural_network) are the textbook case of a cyclic description that becomes acyclic in practice. The *Deep Learning* textbook by Goodfellow, Bengio and Courville describes RNNs as computational graphs that include cycles, and explains that unfolding the recurrence for a finite number of time steps yields an expression that "can now be represented by a traditional directed acyclic computational graph", with one node per variable per time step and parameters shared across steps [6]. Training needs no special algorithm: the gradient is computed by applying ordinary back-propagation to the unrolled graph [6].

### Architectures and architecture search

The D-VAE paper (NeurIPS 2019) observes that many machine learning models, including neural networks and Bayesian networks, are realized as computations on DAGs [9]. [Neural architecture search](https://aiwiki.ai/wiki/neural_architecture_search) uses this directly. In DARTS (Liu, Simonyan and Yang, ICLR 2019), the searched building block is a cell defined as "a directed acyclic graph consisting of an ordered sequence of N nodes", where each node is a latent representation such as a feature map, each edge carries an operation, and each intermediate node is computed from all of its predecessors [20]. DARTS relaxes this architecture representation into a continuous one so that the architecture can be searched with gradient descent [20].

Because DAGs are a common input type, researchers have designed [graph neural networks](https://aiwiki.ai/wiki/graph_neural_network) specifically for them. D-VAE encodes DAGs with an asynchronous message-passing scheme that follows the computation the DAG represents, rather than the simultaneous message passing used by standard GNNs, and applies the resulting latent space to neural architecture search and Bayesian network structure learning with [Bayesian optimization](https://aiwiki.ai/wiki/bayesian_optimization) [9]. DAGNN (Thost and Chen, ICLR 2021) processes information in the order defined by the DAG's partial order and was evaluated on source code, neural architectures and probabilistic graphical models [10].

## Workflows and data pipelines

Systems that schedule work across many machines commonly describe a job as a DAG of tasks, where an edge means that one task needs another's output.

| System | What the vertices are | What the edges mean |
|---|---|---|
| Apache Airflow | Tasks in a workflow | Dependencies that set the order and conditions for running tasks [21] |
| Apache Spark | Stages of pipelined transformations | Dependencies between stages, built from the lineage graph and cut at shuffles [22] |
| MapReduce, Dryad | Tasks within a job | Dependencies tracked for recovery [22] |
| PyTorch autograd | Function objects (operations) | Tensors flowing from inputs to outputs [5] |
| Git | Commit objects | Parent links between commits [23] |

Apache Airflow, an open-source workflow orchestrator, names its central concept after the structure. Its documentation defines a Dag as "a model that encapsulates everything needed to execute a workflow": the schedule, the tasks, the dependencies between them and related settings. The Dag is concerned only with how to run the tasks, not with what happens inside them [21]. Airflow was started by Maxime Beauchemin at Airbnb in October 2014, was open source from its first commit, entered the Apache Software Foundation's Incubator in March 2016, and became an Apache Top-Level Project in January 2019 [24].

In Apache Spark, whenever a user runs an action on a resilient distributed dataset (RDD), the scheduler examines the dataset's lineage graph and builds a DAG of stages to execute, pipelining as many narrow transformations as possible inside each stage and cutting stages at the shuffles that wide dependencies require [22]. The RDD paper (NSDI 2012) notes that MapReduce and Dryad likewise track dependencies among a DAG of tasks within a job, though they discard that lineage once the job ends [22].

The same distinction shows up in software for [large language model](https://aiwiki.ai/wiki/large_language_model) applications. When LangChain introduced [LangGraph](https://aiwiki.ai/wiki/langgraph) in January 2024, the announcement noted that chains built with the LangChain Expression Language are directed acyclic graphs, like most data orchestration frameworks, and presented an easy way to add cycles as LangGraph's main contribution, because more complex applications, such as [agents](https://aiwiki.ai/wiki/ai_agents), often run a model in a loop so that it can reason about what to do next [25].

## Other uses

Version control is a familiar example outside machine learning. Git's glossary defines its commit history as a DAG: commits point to their parents, and no chain of commits begins and ends at the same object [23].

## See also

- [Bayesian network](https://aiwiki.ai/wiki/bayesian_network)
- [Causal inference](https://aiwiki.ai/wiki/causal_inference)
- [Computational graph](https://aiwiki.ai/wiki/computational_graph)
- [Graph](https://aiwiki.ai/wiki/graph)
- [Probabilistic graphical model](https://aiwiki.ai/wiki/probabilistic_graphical_model)
- [Graph neural network](https://aiwiki.ai/wiki/graph_neural_network)
- [Judea Pearl](https://aiwiki.ai/wiki/judea_pearl)

## References

1. Paul E. Black. "directed acyclic graph". Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology, 19 April 2004. https://xlinux.nist.gov/dads/HTML/directAcycGraph.html
2. Jeff Erickson. "Depth-First Search" (Chapter 6). Algorithms, 1st edition, 2019. https://jeffe.cs.illinois.edu/teaching/algorithms/book/06-dfs.pdf
3. Judea Pearl. "Causal diagrams for empirical research". Biometrika 82(4): 669-688, 1995. https://doi.org/10.1093/biomet/82.4.669 (technical report version: https://ftp.cs.ucla.edu/pub/stat_ser/R218-B.pdf)
4. Peter W. G. Tennant, Eleanor J. Murray, Kellyn F. Arnold, et al. "Use of directed acyclic graphs (DAGs) to identify confounders in applied health research: review and recommendations". International Journal of Epidemiology 50(2): 620-632, 2021. https://doi.org/10.1093/ije/dyaa213
5. PyTorch. "A Gentle Introduction to torch.autograd". PyTorch Tutorials. https://docs.pytorch.org/tutorials/beginner/blitz/autograd_tutorial.html
6. Ian Goodfellow, Yoshua Bengio and Aaron Courville. "Sequence Modeling: Recurrent and Recursive Nets" (Chapter 10). Deep Learning, MIT Press, 2016. https://www.deeplearningbook.org/contents/rnn.html
7. David Maxwell Chickering, David Heckerman and Christopher Meek. "Large-Sample Learning of Bayesian Networks is NP-Hard". Journal of Machine Learning Research 5: 1287-1330, 2004. https://www.jmlr.org/papers/v5/chickering04a.html
8. Xun Zheng, Bryon Aragam, Pradeep Ravikumar and Eric P. Xing. "DAGs with NO TEARS: Continuous Optimization for Structure Learning". NIPS 2018 (arXiv:1803.01422). https://arxiv.org/abs/1803.01422
9. Muhan Zhang, Shali Jiang, Zhicheng Cui, Roman Garnett and Yixin Chen. "D-VAE: A Variational Autoencoder for Directed Acyclic Graphs". NeurIPS 2019 (arXiv:1904.11088). https://arxiv.org/abs/1904.11088
10. Veronika Thost and Jie Chen. "Directed Acyclic Graph Neural Networks". ICLR 2021 (arXiv:2101.07965). https://arxiv.org/abs/2101.07965
11. NetworkX developers. "topological_sort". NetworkX documentation. https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.dag.topological_sort.html
12. Paul E. Black. "topological sort". Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology, 21 April 2022. https://xlinux.nist.gov/dads/HTML/topologicalSort.html
13. OEIS Foundation. "A003024: Number of acyclic digraphs (or DAGs) with n labeled nodes". The On-Line Encyclopedia of Integer Sequences. https://oeis.org/A003024
14. University of Alaska Fairbanks. "CS 411 Fall 2025: Outline & Supplemental Notes for September 19, 2025" (Topological Sort). 19 September 2025. https://www.cs.uaf.edu/~chappell/class/2025_fall/cs411/lect/lec-20250919-topsort.html
15. A. B. Kahn. "Topological sorting of large networks". Communications of the ACM 5(11): 558-562, November 1962. https://doi.org/10.1145/368996.369025
16. Johannes Textor, Benito van der Zander, Mark S. Gilthorpe, Maciej Liśkiewicz and George T. H. Ellison. "Robust causal inference using directed acyclic graphs: the R package 'dagitty'". International Journal of Epidemiology 45(6): 1887-1894, 2016. https://doi.org/10.1093/ije/dyw341
17. Matt J. Kusner, Joshua R. Loftus, Chris Russell and Ricardo Silva. "Counterfactual Fairness". NIPS 2017 (arXiv:1703.06856). https://arxiv.org/abs/1703.06856
18. Martín Abadi, Paul Barham, Jianmin Chen, et al. "TensorFlow: A system for large-scale machine learning". arXiv:1605.08695, 2016. https://arxiv.org/abs/1605.08695
19. Yuan Yu, Martín Abadi, Paul Barham, Eugene Brevdo, Mike Burrows, Andy Davis, et al. "Dynamic Control Flow in Large-Scale Machine Learning". EuroSys '18, Porto, April 2018 (arXiv:1805.01772). https://arxiv.org/abs/1805.01772
20. Hanxiao Liu, Karen Simonyan and Yiming Yang. "DARTS: Differentiable Architecture Search". ICLR 2019 (arXiv:1806.09055). https://arxiv.org/abs/1806.09055
21. Apache Software Foundation. "Dags". Apache Airflow documentation (version 3.4.0). https://airflow.apache.org/docs/apache-airflow/stable/core-concepts/dags.html
22. Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, Ankur Dave, Justin Ma, Murphy McCauley, Michael J. Franklin, Scott Shenker and Ion Stoica. "Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing". NSDI 2012. https://www.usenix.org/system/files/conference/nsdi12/nsdi12-final138.pdf
23. Git. "gitglossary: A Git Glossary". Git documentation. https://git-scm.com/docs/gitglossary
24. Apache Software Foundation. "Project". Apache Airflow documentation. https://airflow.apache.org/docs/apache-airflow/stable/project.html
25. The LangChain Team. "LangGraph". LangChain Blog, 17 January 2024. https://www.langchain.com/blog/langgraph

