Directed Acyclic Graph (DAG)

overview

Summary

A directed acyclic graph (DAG) is a directed graph with no cycles, which makes it perfect for modeling dependencies that must flow forward. DAGs guarantee at least one topological ordering of nodes that respects all edges. Many problems that are hard on general graphs become simple on DAGs, including scheduling and dynamic programming over edges. You’ll see DAGs behind build systems, data pipelines, version control histories, and probabilistic models.