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 is acyclic if it contains no directed cycle. A directed cycle is a sequence with and each . Equivalently, a finite is a DAG if and only if it has a topological ordering. A topological ordering is a list of all vertices in which appears before for every edge .
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.
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.
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.
