Directed acyclic graph

A directed acyclic graph (DAG) is a directed graph containing no directed cycles: following edges in their indicated directions can never lead back to the starting vertex. DAGs are studied in graph theory and widely used in computer science to represent relationships that admit a consistent forward ordering, such as prerequisites and computational dependencies. Every finite DAG has a topological ordering, making it possible to process its vertices without encountering a circular dependency. (algs4.cs.princeton.edu)

Definition and basic properties

A directed graph is commonly written $G=(V,E)$, where $V$ is a set of vertices and $E\subseteq V\times V$ is a set of ordered pairs representing edges. An edge $(u,v)$, written $u\to v$, points from $u$ to $v$. A directed path follows successive edges in their specified directions; a directed cycle returns to its initial vertex. A DAG excludes every such cycle, including a self-loop $v\to v$. Unless otherwise stated, algorithmic discussions concern finite graphs. (algs4.cs.princeton.edu)

The indegree of a vertex counts incoming edges, while its outdegree counts outgoing edges. A vertex with indegree zero is a source; one with outdegree zero is a sink. Every nonempty finite DAG has at least one source and one sink. Vertices reachable from a vertex are its descendants, and vertices from which it is reachable are its ancestors. These terms refer to paths, not only direct edges. (networkx.org)

Acyclicity concerns direction, rather than the appearance of a drawing. For example, the edges $A\to B$, $B\to C$, and $A\to C$ form a DAG, although ignoring their directions produces an undirected triangle. DAGs need not be connected or have a unique source. (networkx.org)

Topological ordering

A topological ordering lists vertices so that every edge points from an earlier vertex to a later one. A finite directed graph admits such an ordering if and only if it is acyclic. The ordering need not be unique: vertices unconstrained by the dependency relation may occur in different positions. Thus, a DAG specifies precedence constraints rather than necessarily specifying one execution sequence. (algs4.cs.princeton.edu)

One algorithm repeatedly selects a source, appends it to the ordering, and removes its outgoing edges. Newly created sources become available for selection. If vertices remain when no source is available, the remaining graph contains a directed cycle. Another method uses depth-first search: after checking for cycles, vertices are listed in reverse finishing order. (algs4.cs.princeton.edu)

With adjacency lists, both methods have time complexity $O(|V|+|E|)$, expressed using big-O notation. Source removal also gives a constructive explanation of the ordering theorem: successive choices can continue until every vertex has been processed precisely when no directed cycle obstructs them. (networkx.org)

Reachability and partial orders

DAGs connect graph structure with partial orders. Define $u\preceq v$ when $u=v$ or a directed path leads from $u$ to $v$. This binary relation is reflexive and transitive; it is antisymmetric because paths in both directions between distinct vertices would create a cycle. Vertices with no path between them in either direction are incomparable. A topological ordering extends this partial order to a linear ordering. (courses.csail.mit.edu)

The transitive closure records every relationship implied by reachability, adding $u\to v$ whenever a positive-length path connects them. The transitive reduction instead removes redundant edges while preserving reachability. For a finite DAG, the reduction is unique. In the triangle example, $A\to C$ is redundant because $A\to B\to C$ already establishes the same precedence. Reduction preserves reachability, but not necessarily edge weights or direct-dependency information. (networkx.org)

Path algorithms and dependency scheduling

A topological ordering supports dynamic programming because predecessor results are available before a vertex is processed. For the single-source shortest-path problem, initialize the source distance to zero and other distances to infinity. Process vertices in topological order and relax each outgoing edge:

Each edge is examined once, giving $O(|V|+|E|)$ running time, including ordering. Negative edge weights are permitted because directed cycles—and therefore negative cycles—are absent. (cs.princeton.edu)

Longest paths can likewise be computed by replacing minimization with maximization and initializing unreachable distances to negative infinity. This supports the critical-path method for scheduling tasks with durations and precedence constraints. Under the model of unlimited processors and no additional resource constraints, a longest dependency path determines the minimum completion time. A topological ordering alone does not determine the optimal schedule when limited resources introduce further constraints. (algs4.cs.princeton.edu)

Probabilistic and computational models

In a Bayesian network, DAG vertices represent random variables, while the graph encodes conditional independence assumptions. Together with local conditional distributions, it represents a joint probability distribution through

where $\operatorname{Pa}(X_i)$ denotes the parents of $X_i$. The graphical criterion of d-separation identifies independence statements implied by this factorization. An arrow need not imply statistical dependence for every possible parameter choice. (cs.cmu.edu)

DAGs also represent computational graphs used in automatic differentiation. Operations depend on earlier values during forward evaluation; backpropagation traverses those dependencies backward, applying the chain rule to accumulate derivatives. Shared intermediate results allow one computed value to contribute to several later operations without duplicating its computation. Here, acyclicity applies to the recorded dependencies of the evaluated computation, even when the program generating that computation contains loops. (docs.pytorch.org)