Algorithms also: Directed Acyclic Graph

DAG

Edges have direction; no cycles.

In plain terms

The natural shape for build systems, version control, schedulers, dataflow engines. Topological sort produces a valid execution order in O(V+E).

Origin

Topological sort dates to Kahn (1962). DAGs became central to modern build systems (Bazel, Buck), dataflow engines (Spark, Flink), and version control (Git).

Where it shows up in production

Apache Airflow Workflow = DAG. Tasks = nodes, dependencies = edges.
Bazel / Buck Build graph is a DAG; incremental builds rebuild only the affected subtree.
Git Commit graph is a DAG. Merge commits have multiple parents.

On Semicolony

Data structures data structures

Sources & further reading

Paper Kahn — topological sort (1962)

Found this useful?