directed acyclic graph (DAG)

A directed acyclic graph (DAG) is a directed graph, a set of vertices joined by one-way edges, that contains no cycles, so following its edges in their given direction never leads back to a vertex already visited.

Each edge in a DAG points one way, from one vertex to another, and usually means “comes before” or “depends on.” A graph with even one loop, such as A to B to C and back to A, doesn’t qualify. Paths can still split apart and later rejoin, as in A to B to D and A to C to D, as long as no path leads back to where it started.

Without cycles, every DAG has a few useful properties:

  • Sources and sinks: Every finite, non-empty DAG has at least one vertex with no incoming edges and at least one with no outgoing edges.
  • Topological order: The vertices can always be lined up so that every edge points forward, which is what a topological sort produces.
  • Fast path problems: Shortest and longest paths can be computed in linear time by processing vertices in topological order.

In the graph below, switch on extra edges one at a time to see which ones keep it acyclic and which ones close a loop, taking away its topological order and sometimes its sources and sinks:

Interactive diagram — enable JavaScript to view.

A DAG is the natural model for any set of tasks where some must finish before others start. Build tools compile files in dependency order, and workflow schedulers run the steps of a data pipeline as a DAG. Spreadsheets track which cells depend on which as a DAG and recalculate them in that order, and a Git history forms one, because a merge commit has several parents but no commit can be its own ancestor.

Tools that sort or schedule a DAG first confirm that it really has no cycles. A depth-first search finds a cycle when it meets an edge back to a vertex still on its current path. Python’s graphlib module sorts a DAG and raises CycleError when the input contains a cycle.

Build a Maze Solver in Python Using Graphs

Tutorial

Build a Maze Solver in Python Using Graphs

In this step-by-step project, you'll build a maze solver in Python using graph algorithms from the NetworkX library. Along the way, you'll design a binary file format for the maze, represent it in an object-oriented way, and visualize the solution using scalable vector graphics (SVG).

intermediate projects

For additional information on related topics, take a look at the following resources:

Have a question about this? Mentor AI can show you examples, compare related terms, and point you to tutorials.

  • Ask Mentor AI
  • Pick a question and Mentor AI takes it from here.
By Martin Breuss • Updated Oct. 29, 2026
Computer Science Glossary Share Feedback