Directed Acyclic Graphs — Graph Theory

Overview

What this concept solves

A directed acyclic graph is a directed graph with no way to loop back. Every edge is an arrow with a direction, and no matter which arrow you start on or how you follow them, you can never return to where you began. That single 'no cycles' property is the whole concept — and it is more powerful than it looks, because it guarantees the vertices can always be laid out in a straight line where every arrow points forward. That line is called a topological order.

You have used DAGs all day without naming them. A build system is a DAG: compile a.o before linking it into the binary. A spreadsheet is a DAG of cells: a formula depends on the cells it references, and a circular reference is an error precisely because it would break acyclicity. Package managers, task schedulers, course prerequisites, and git commit history are all DAGs. The arrows mean 'must come before' or 'depends on', and topological sort is the universal answer to 'in what order can I do all of this?'.

The reason 'acyclic' matters so much: a cycle is a dependency loop, and a loop has no valid order. If A must come before B, B before C, and C before A, there is no first thing to do — the task is impossible. So the same algorithm that produces an order also detects whether the graph is a true DAG: if a topological sort can place every vertex, the graph is acyclic; if it gets stuck with vertices left over, those leftovers form a cycle and no order exists.

Mechanics

How it works

Kahn's algorithm — topological sort by in-degree

Compute the in-degree of every vertex — the number of arrows pointing into it. A vertex with in-degree 0 has no prerequisites.
Put every in-degree-0 vertex into a ready queue. These can go first, in any order.
Pop a vertex from the queue, append it to the order, and for each of its outgoing arrows, decrement the target's in-degree (the arrow is now 'satisfied').
Any target whose in-degree just hit 0 has all its prerequisites placed — add it to the ready queue.
Repeat until the queue is empty. If you placed all V vertices, the order is a valid topological sort. If not, the unplaced vertices form a cycle — the graph is not a DAG.

Two algorithms, same answer

Kahn's algorithm (above) is the in-degree / queue approach the prototype animates. The other classic is DFS-based: run depth-first search and emit each vertex once you finish exploring all its descendants — the reverse of that finish order is a topological sort. DFS also catches cycles via a 'grey' (on-the-stack) edge. Both run in O(V + E); Kahn's is easier to watch because the ready queue makes the 'no remaining prerequisites' condition visible.

The order is not unique. Whenever two vertices are both ready at the same time — neither depends on the other — you may take either one first, and each choice leads to a different valid order. A DAG therefore encodes a partial order: it fixes the relative order of any two vertices joined by a chain of arrows, and leaves incomparable vertices free to swap. The number of valid topological orders can be huge; any line that respects every arrow counts.

Detecting the cycle is the point

When Kahn's algorithm stalls, the vertices it never placed are exactly those still trapped in a cycle — every one of them still has an incoming arrow from another unplaced vertex, so none can ever reach in-degree 0. That is why spreadsheets can flag a circular reference and build tools can report a dependency cycle: the same topological sort that orders the work also proves when ordering is impossible.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › Directed Acyclic Graphs

About this simulation

A six-vertex directed graph across four tabs. Topological order runs Kahn's algorithm on a valid DAG — counting in-degrees, seeding a ready queue with the in-degree-0 vertices, then placing one at a time and decrementing successors. Add a back edge → cycle runs the same algorithm on the graph plus a back edge: the queue empties early and the leftover vertices light up red. Many valid orders shows two different correct orders for the same DAG side by side. Free play lets you click a source then a target to add a forward arrow, drag vertices, and hit Topological sort to get an order or a 'cycle — not a DAG' verdict, with a live placed count.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Topological order

On Topological order, press Play to run Kahn's algorithm on the DAG. The first step counts every vertex's in-degree (shown as in N badges) and lights the in-degree-0 vertices blue — those seed the ready queue in the left panel. Each subsequent step pops a ready vertex (it flashes amber, then turns green with its position #k in the right-hand topological order panel) and decrements its successors' in-degrees; when one hits 0 it joins the queue. The final step shows the full order A → B → C → D → E → F and the is a DAG? stat flips to Yes ✓. Use Step / Back to move one decrement at a time.

try 02

Add a back edge → cycle

Switch to Add a back edge → cycle. The first step highlights the added arrow F→B in red — it closes the loop B→D→F→B. Play on, and watch the ready queue drain: a few vertices get placed, then the queue empties with B, D, F never placed. Those three light up red (in-degree-0 was never reached for any of them) and the is a DAG? stat reads No (cycle). The lesson: one back edge is enough to make a topological order impossible.

try 03

Many valid orders

On Many valid orders, Play to see the same DAG sorted two different ways. Order A breaks ties by smallest letter; Order B breaks them by largest. Both appear in side-by-side panels, and both are correct — trace any arrow and its tail still precedes its head in either line. The closing step names the idea: a DAG is a partial order, so incomparable vertices are free to swap and any arrow-respecting line is a valid sort.

try 04

Free play — break the acyclic rule yourself

Open Free play. Click a source vertex then a target to add a forward arrow; drag vertices to rearrange. The prototype refuses an arrow whose reverse already exists (that would make a 2-cycle) — a small taste of the validation a real dependency system must do. Hit Topological sort to run Kahn's on your graph: a valid DAG reports its order and turns every vertex green, while a graph with a cycle reports 'cycle — not a DAG' and reddens the trapped vertices. Watch the placed stat and the is a DAG? card update live.

In practice

When to use it — and what you give up

Model it as a DAG when

Relationships mean 'must come before' or 'depends on' — build targets, package dependencies, task prerequisites, course requirements, data-pipeline stages.
You need a valid execution order — topological sort hands you one in O(V + E), and tells you if none exists.
Cycles are illegal and you want to detect them — spreadsheet circular references, deadlock-free lock ordering, a Makefile that must not loop.
You're recording an immutable, branching history — git commits, blockchain blocks, and event-sourcing logs are DAGs where arrows point to ancestors.

Reach for something else when

The relationship can legitimately loop — web links, social follows, road networks, and state machines have cycles; use a general directed (cyclic) graph.
Direction is meaningless — if A relating to B always implies B relating to A (friendship, physical cables), an undirected graph is simpler and correct.
You need shortest paths with costs — that's a job for a weighted graph with Dijkstra or Bellman-Ford (though a DAG admits an even faster linear-time shortest path via topological order).

Pros

A valid order always exists and is cheap — topological sort runs in O(V + E), turning a tangle of dependencies into a flat to-do list.
Cycle detection comes free — the same sort that orders the work proves when ordering is impossible, with the offending cycle identified.
Unlocks linear-time DP — longest path, shortest path, and counting paths are all O(V + E) on a DAG because you can process vertices in topological order.
Matches how real systems think — builds, schedulers, and dependency resolvers map onto a DAG almost without translation.

Cons

The acyclic constraint is a real burden — you must guarantee no cycles ever form, which means validating every edge you add (the prototype refuses a reverse arrow for this reason).
Can't model genuine feedback loops — retries, mutual recursion, and cyclic state transitions don't fit; forcing them in loses information.
The order isn't unique — if you need a single canonical order you must add a deterministic tie-break, or downstream results may differ run to run.
One bad edge breaks everything — a single accidental back edge turns the whole graph into a non-DAG, and topological sort then refuses to produce any order at all.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

dag.ts

// Topological sort via Kahn's algorithm.
// Returns a valid linear order, or null if the graph has a cycle (not a DAG).
function topologicalSort(
  vertices: string[],
  edges: [string, string][], // [from, to] — "from must come before to"
): string[] | null {
  // 1. In-degree = number of arrows pointing INTO each vertex.
  const inDegree = new Map<string, number>(vertices.map((v) => [v, 0]));
  const out = new Map<string, string[]>(vertices.map((v) => [v, []]));
  for (const [u, v] of edges) {
    out.get(u)!.push(v);
    inDegree.set(v, inDegree.get(v)! + 1);
  }

  // 2. Seed the ready queue with every in-degree-0 vertex (no prerequisites).
  const ready = vertices.filter((v) => inDegree.get(v) === 0);
  const order: string[] = [];

  // 3. Place a ready vertex, then relax its outgoing arrows.
  while (ready.length > 0) {
    const u = ready.shift()!;
    order.push(u);
    for (const v of out.get(u)!) {
      inDegree.set(v, inDegree.get(v)! - 1); // this arrow is now satisfied
      if (inDegree.get(v) === 0) ready.push(v); // all prerequisites done
    }
  }

  // 4. Placed everything ⇒ DAG. Otherwise the leftovers form a cycle.
  return order.length === vertices.length ? order : null;
}

// const order = topologicalSort(
//   ["A", "B", "C", "D", "E", "F"],
//   [["A","C"],["B","C"],["B","D"],["C","E"],["D","E"],["D","F"],["E","F"]],
// ); // → ["A","B","C","D","E","F"]  (one of several valid orders)

References & further reading

6 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

What single property distinguishes a DAG from a general directed graph, and what does it guarantee?

question 02 / 03

In Kahn's algorithm, what does it mean if the ready queue empties before all vertices have been placed?

question 03 / 03

Why can the same DAG have more than one valid topological order?

0/3 answered