Mathwords logoMathwords

Directed Acyclic Graph — Definition & Example

A directed acyclic graph (DAG) is a graph whose edges are one-way arrows, arranged so that you can never follow the arrows and return to where you started.

A directed graph G=(V,E)G = (V, E) is acyclic if it contains no directed cycle. A directed cycle is a sequence v0→v1→⋯→vk=v0v_0 \to v_1 \to \cdots \to v_k = v_0 with k≥1k \ge 1 and each (vi,vi+1)∈E(v_{i}, v_{i+1}) \in E. Equivalently, a finite GG is a DAG if and only if it has a topological ordering. A topological ordering is a list of all vertices in which uu appears before vv for every edge (u,v)∈E(u, v) \in E.

Worked Example

Problem: A math department lists five courses with prerequisites: Calculus I (C1) before Calculus II (C2), C1 before Linear Algebra (L), C2 before Differential Equations (D), L before D, and C2 before Real Analysis (R). Model this as a directed graph, confirm it is a DAG, and find an order in which you could take all five courses.
Step 1: Draw an edge from each prerequisite to the course it unlocks. Then count the in-degree of each vertex, which is the number of arrows pointing into it. C1 has 0, C2 has 1, L has 1, D has 2, and R has 1. The in-degrees add up to 5, which matches the 5 edges.
0+1+1+2+1=5=∣E∣0 + 1 + 1 + 2 + 1 = 5 = |E|
Step 2: Repeatedly remove a vertex with in-degree 0 and delete its outgoing edges. This is Kahn's algorithm. Remove C1, and C2 and L drop to in-degree 0. Remove C2, and R drops to 0 while D drops to 1. Remove L, and D drops to 0. Remove D, then R.
C1, C2, L, D, R\text{C1},\ \text{C2},\ \text{L},\ \text{D},\ \text{R}
Step 3: Every vertex was removed, so no directed cycle exists and the graph is a DAG. If a cycle existed, its vertices would never reach in-degree 0, and the process would stall before removing them.
Answer: The graph is a DAG. One valid course order is C1, C2, L, D, R. Other orders also work, such as C1, L, C2, R, D. A DAG usually has more than one topological ordering.

Why It Matters

DAGs model systems of dependencies that contain no cycles. Examples include course prerequisite charts, the build order of software packages, spreadsheet formulas that reference other cells, and Git commit histories. In a discrete math or algorithms course, you use topological sorting of a DAG to schedule tasks and to find longest paths in project planning, known as the critical path method.

Common Mistakes

Mistake: Assuming a DAG must look like a tree, or that its undirected version must also be acyclic.
Correction: The edges A→B, B→C, and A→C form a DAG, because no arrow path returns to A. If you ignore the arrow directions, though, the same three edges form a triangle. Only directed cycles are forbidden, so always check that the arrows line up head-to-tail around the loop.

Related Terms