A directed acyclic graph — DAG for short — is a graph with two rules bolted on: every edge points in one direction, and following those edges can never bring you back to a node you already visited. No loops, no cycles, ever. That constraint sounds small, but it is the reason DAGs became the default way to model dependencies in software: once a system enforces the no-cycles rule, you can always find a safe order to process everything in it.
What changed in 2026
- Agent and workflow frameworks lean on DAGs constantly. Tool-call chains and multi-step pipelines are represented as DAG nodes so a scheduler can run independent steps in parallel.
- Pipeline orchestrators validate before running, not after. Data and ML pipeline tools have kept DAGs as the core abstraction for years; more of them now flag a cycle at definition time instead of failing mid-run.
- Visual DAG debugging is standard now. Most build tools and orchestrators ship an interactive graph viewer, so tracing a hung build is less guesswork than before.
How a DAG is actually defined
Two properties, both required:
- Directed — every edge has a direction. An edge from A to B is not the same as one from B to A.
- Acyclic — there is no path that starts at a node and, by following directed edges, returns to that same node.
Drop either property and it stops being a DAG. Remove "directed" and you get an undirected acyclic graph — which is just a tree or a forest. Remove "acyclic" and you get a general directed graph, where cycles are allowed and a safe processing order is not guaranteed to exist at all.
Where DAGs show up in real systems
| System |
What the nodes are |
What an edge means |
| Build tools (Make, Bazel, Turborepo) |
Build targets or packages |
"depends on" |
| Task schedulers (Airflow-style orchestrators) |
Pipeline steps |
"must finish before" |
| Spreadsheets |
Cells with formulas |
"reads the value of" |
| Git history |
Commits |
"parent of" |
| Course catalogs |
Courses |
"is a prerequisite for" |
| Neural network graphs |
Layers or operations |
"feeds output into" |
The pattern repeats: whenever "X must happen before Y" is a rule in your domain, a DAG is very likely already the right model, whether you drew it that way or not.
DAG vs tree vs general graph
People often reach for "tree" when they mean DAG. A tree is a DAG with an extra restriction: every node has exactly one parent. A DAG allows a node to have multiple parents — think of a build target that two other targets both depend on. That is a valid DAG and an invalid tree.
How to detect a cycle
The standard approach is a depth-first search that tracks nodes currently in progress on the recursion stack, not just visited nodes:
def has_cycle(graph):
WHITE, GRAY, BLACK = 0, 1, 2
color = {node: WHITE for node in graph}
def visit(node):
color[node] = GRAY
for neighbor in graph[node]:
if color[neighbor] == GRAY:
return True # back edge -> cycle
if color[neighbor] == WHITE and visit(neighbor):
return True
color[node] = BLACK
return False
return any(color[n] == WHITE and visit(n) for n in graph)
A gray node is one still on the current path; hitting a gray node again is what a cycle looks like. This is the same check most schedulers run before attempting a topological sort — you cannot produce a valid order from a graph that already has a cycle in it.
Common mistakes
Assuming a dependency graph is acyclic because it should be. Config-driven systems such as feature flags accumulate accidental cycles as they grow. Validate the graph, do not assume it.
Confusing "no cycles" with "no shared dependencies." Diamonds — two paths from one node that both reach the same later node — are normal in a DAG. That is not a cycle.
Treating a DAG as a tree when writing traversal code. If you assume a single parent per node and one has two, you will double-process it. Track visited nodes explicitly instead of relying on a simple recursive walk.
FAQ
Is a linked list a DAG?
Yes, trivially. It is a very restricted one: a straight line with no branching and no cycles.
Can a DAG have more than one starting point?
Yes. Any node with no incoming edges is a valid starting point, and a DAG can have several of them at once.
How is a DAG different from a tree?
A tree requires each node to have at most one parent. A DAG allows multiple parents, as long as there is still no cycle anywhere in the graph.
Do I need a special library to work with DAGs?
For small graphs, a plain adjacency list and the cycle-detection code above are enough. For production pipelines, use an established orchestrator rather than hand-rolling scheduling and retry logic yourself.
Where to go next