← Back to the graphs page
DAG (Directed Acyclic Graph)
A digraph with no cycles — there is always a valid linear ordering of nodes (topological order). The backbone of schedulers and build systems.
What to know
- Topological order is not unique; any order respecting all edges is valid.
- Dynamic programming on a DAG processes nodes in topological order.
- Longest path is NP-hard on general graphs but linear-time on DAGs.
- Course Schedule (LeetCode 207/210) is the canonical interview DAG problem.
In the wild: Makefiles/CI pipelines, Airflow task DAGs, Git commit history, spreadsheet formula evaluation.
Algorithms to reach for
Topological sort (Kahn or DFS)
O(V + E)Linearize dependencies (build order, course order)
DAG shortest/longest path (DP)
O(V + E)Critical path in project scheduling
Memoized DFS counting
O(V + E)Count paths between nodes without recomputation
Practice problems — with full guides
Each problem has its own page: progressive hints, how to approach it, and the full solution.