directed acyclic graph

A directed graph with no cycles, so following edges can never bring you back to where you started.

In more detail

Build systems, course prerequisites, spreadsheet formulas and task pipelines are all DAGs of dependencies. Every DAG has at least one topological order, and only DAGs do.

Example

Dynamic programming subproblems also form a DAG.

Related terms

Taught in

References

Certification courses