Search tools and guides ⌘K
VI · Graphs & sets

DAG · directed acyclic graph

Order without cycles.

Foundational · Implicit since graph theory itself
The story

Not a single inventor — but a single, recurring shape. Build systems, package managers, version control, distributed schedulers, dataflow engines: anything where "X must happen before Y" is acyclic, and the natural representation is a DAG.

How it works

Vertices = tasks/objects; edges = dependencies. Topological sort produces an execution order in O(V + E). Cycles signal an error.

Where it lives

make, Bazel, Buck, Pants. Git's commit graph. Spark / Flink / Beam DAGs. Airflow / Prefect / Dagster. Kubernetes admission webhooks (validation order). Every dataflow engine ever shipped.

The key insight

When you find yourself with a cycle in something that should be a DAG, the answer is almost always: extract the cyclic part into a separate component and break it. Tools that allow cycles eventually wish they hadn't.

More in Graphs & sets
Adjacency list Each node, its neighbours. Disjoint Set / Union-Find Track connected components, in a forest. Merkle tree Hash of hashes; tamper-evident. LSM-tree Append-only, merged in the background.
Across the cabinet
VII Z-order / Hilbert curve Linearise space, preserve locality. I Array A row of equal-sized boxes. I Dynamic array (vector) An array that grows itself. I Linked list A chain you can splice. I Stack Last in, first out. I Queue First in, first out. I Deque Both ends, equally. I Ring buffer A fixed-size queue that never allocates.
← All data structures