GraphsData structureaka directed acyclic graph, dependency graph

DAG (Directed Acyclic Graph)

A directed graph with no cycles, guaranteeing a topological order in which every edge points forward.

▶ VisualizePattern: Depth-First SearchPractice (2)
Progress

Definition

A DAG is a Directed Graph in which no path returns to its starting vertex. Equivalently, its vertices can be arranged in a line — a topological order — so that every edge points left-to-right. Every DAG has at least one source (in-degree 0) and one sink (out-degree 0).

Acyclicity unlocks a family of linear-time algorithms that fail on general digraphs: Topological Sort via Kahn's Algorithm or DFS Topological Sort; single-source shortest and longest paths in O(V + E) by relaxing edges in topological order (DP on DAGs); counting paths; and critical-path scheduling.

DAGs are the natural model for dependencies (build targets, course prerequisites, spreadsheet cells), version histories, and any Dynamic Programming recurrence — the subproblem graph of a DP is always a DAG.

topological orderdependenciesDP on DAGlongest pathpartial order

Intuition

A mental model before the formal terms.

A to-do list with "must happen before" arrows. If the arrows never loop, you can always find *something* with no pending prerequisites, do it, cross it off, and repeat. That process is Kahn's algorithm, and the order you cross things off is a topological order. If you ever get stuck with items remaining, the arrows contain a cycle.

A DP table is a DAG: dp[i] depends on some earlier cells; filling the table in the right order is exactly evaluating vertices in topological order.

How it works

  1. Kahn (BFS) topological sort: compute indeg[]; push all vertices with in-degree 0; pop u, append to the order, decrement indeg[v] for each u → v, pushing v when it hits 0. If the order has fewer than V vertices, there is a cycle.
  2. DFS topological sort: DFS from every unvisited vertex, append each vertex to a list *after* its recursion finishes (post-order); reverse the list.
  3. Shortest/longest path: set dist[source] = 0, then for each u in topological order relax all u → v. Longest path uses max instead of min — no negative-weight worries because there are no cycles.
  4. Count paths from s to t: ways[s] = 1; in topological order, ways[v] += ways[u] for each u → v.
  5. Lexicographically smallest order: replace Kahn's queue with a Min-Heap.
  6. Verify a DAG: run Kahn and check that all V vertices were emitted, or DFS with three-colour marking.

Why it works

Every finite DAG has a vertex of in-degree 0: otherwise walking backward along in-edges forever would revisit a vertex, forming a cycle. Removing it leaves a smaller DAG, so induction produces a full order.

In DFS post-order, a vertex finishes only after all vertices reachable from it, so for any edge u → v, v finishes before u. Reversing finish order therefore puts u before v.

Relaxing edges in topological order guarantees that when u is processed, every path into u has already been considered, so dist[u] is final — the DAG version of Dijkstra's invariant, without needing a heap.

Operations

OperationDescriptionCost
addEdge(u, v)Append v to adj[u], increment indeg[v].O(1)
topoSort()Kahn or DFS post-order.O(V + E)
isDag()Kahn emits all V vertices ⇔ acyclic.O(V + E)
shortestPath(s)Relax in topological order.O(V + E)
longestPath(s)Relax with max in topological order.O(V + E)
countPaths(s, t)DP over topological order.O(V + E)

Recognition

How to tell a problem wants this.

  • "Prerequisites", "dependencies", "must come before", "build order", "task scheduling with precedence".
  • The problem guarantees "no cycles" or asks you to detect whether there is one.
  • "Longest path" in a directed graph — NP-hard in general, linear on a DAG.
  • Counting paths or DP over states where transitions never loop back.
“connected groups” → Depth-First Search“prerequisites” → Topological Sort“number of ways” → Dynamic Programming

Interactive demo

Play, step, change the input. ← → and space work too.

Showing the closely related Kahn's Algorithm visualization.

shirt0tie1jacket2pants0belt2shoes2socks0
Queue
shirtpantssocks
Topological order
empty
1/16Count incoming edges. Nodes with in-degree 0 have no prerequisites, so they can go first: shirt, pants, socks.
Current node (label = in-degree)In queue (in-degree 0)EmittedEdge being removedStuck in a cycle
PseudocodeLearn Kahn's Algorithm →
1indeg[v] = number of incoming edges
2queue = [v for v in nodes if indeg[v] == 0]
3while queue not empty:
4  u = queue.popleft(); order.append(u)
5  for v in neighbors(u):
6    indeg[v] -= 1
7    if indeg[v] == 0: queue.append(v)
8if len(order) < n: cycle detected
Complexity
best O(V + E)
avg O(V + E)
worst O(V + E)
space O(V)
Speed

Pseudocode

1kahn(): q = [u for u if indeg[u] == 0]; order = []
2  while q: u = q.pop(); order.append(u)
3    for v in adj[u]: indeg[v] -= 1; if indeg[v] == 0: q.append(v)
4  if len(order) < V: cycle
5longest_path(s): dist = [-inf]*V; dist[s] = 0
6  for u in order: for v, w in adj[u]: dist[v] = max(dist[v], dist[u] + w)

Implementation

1from collections import deque
2 
3 
4class Dag:
5    """A directed acyclic graph: direction plus the guarantee of no cycle.
6    That guarantee is what makes a topological order — and DP over it —
7    exist."""
8 
91 · State: successors plus the in-degree count Kahn's algorithm consumes
10    def __init__(self, n: int) -> None:
11        self.out: list[list[int]] = [[] for _ in range(n)]
12 
13    def add_edge(self, u: int, v: int) -> None:
14        self.out[u].append(v)
15 
16    def __len__(self) -> int:
17        return len(self.out)
18 
192 · Kahn's algorithm: repeatedly emit a vertex with no unmet dependency
20    def topological_order(self) -> list[int]:
21        indeg = [0] * len(self.out)
22        for row in self.out:
23            for v in row:
24                indeg[v] += 1
25        ready = deque(u for u, d in enumerate(indeg) if d == 0)
26        order: list[int] = []
27        while ready:
28            u = ready.popleft()
29            order.append(u)
30            for v in self.out[u]:
31                indeg[v] -= 1
32                if indeg[v] == 0:
33                    ready.append(v)
343 · A short order proves a cycle: the input was not actually a DAG
35        return order if len(order) == len(self.out) else []
36 
374 · DP over the topological order: every predecessor is already final
38    def longest_path_lengths(self) -> list[int]:
39        order = self.topological_order()
40        best = [0] * len(self.out)
41        for u in order:
42            for v in self.out[u]:
43                best[v] = max(best[v], best[u] + 1)
44        return best
45 
465 · Counting paths is the same sweep with addition instead of max
47    def path_counts_from(self, src: int) -> list[int]:
48        order = self.topological_order()
49        ways = [0] * len(self.out)
50        ways[src] = 1
51        for u in order:
52            if ways[u] == 0:
53                continue
54            for v in self.out[u]:
55                ways[v] += ways[u]
56        return ways
Walkthrough
  1. deque(u for u, d in enumerate(indeg) if d == 0) seeds the ready queue from a generator in one expression.
  2. indeg[v] -= 1 then if indeg[v] == 0 is spelled out because Python has no -- operator and no assignment expression that reads as cleanly here.
  3. len(order) == len(self.out) is the cycle test, and [] is returned otherwise.
  4. path_counts_from returns list[int] and is *exact* at any magnitude, because Python integers are arbitrary precision — the one language here with no overflow story to tell.
  5. if ways[u] == 0: continue skips vertices unreachable from src, which matters on graphs where the source reaches only a small subgraph.
Complexity (this implementation)
time O(V + E) for the topological order and each DP sweep · space O(V)

Arbitrary-precision path counts cost more than fixed-width ones once the numbers get large, but they are never wrong.

Language notes
  • graphlib.TopologicalSorter has been in the standard library since Python 3.9: TopologicalSorter(graph).static_order() raises CycleError on a cyclic input.
  • Python integers are unbounded, so DAG path counting is exact where C++ overflows long long and JavaScript loses precision past 2^53.
  • networkx.topological_sort and networkx.dag_longest_path cover both operations for labelled graphs.
  • deque is the right ready queue; a list with pop(0) would be O(n) per dequeue.
Common mistakes in this language
  • Returning [] for both "cycle" and "empty graph" — raising an exception (as graphlib does) is clearer.
  • Using list.pop(0) for the ready queue and making Kahn's algorithm quadratic.
  • Building indeg with a dict and missing vertices that have no incoming edges, so they never enter the ready queue.
Language differences that matter here
  • DAG path counting exposes the integer story sharply: Python is exact at any size, C++ needs long long and still overflows eventually, and JavaScript/TypeScript silently lose precision past 2^53 unless you move to BigInt.
  • Only Python has a standard-library topological sort (graphlib.TopologicalSorter, which raises CycleError); C++ has it in Boost.Graph, and JS/TS have nothing.
  • The ready queue needs collections.deque in Python and std::queue in C++, while JS/TS use the array-plus-head-cursor workaround because shift() is O(n).
  • Signalling "not a DAG": C++ and JS return an empty container, Python's graphlib raises CycleError, and TypeScript can express it in the type (number[] | null or a discriminated union) — only the last two make the caller handle it.

Complexity

OperationAverageWorstNote
AccessO(1)O(1)Vertex by id.
SearchO(deg(u))O(V)Edge (u, v) lookup by scanning u's list.
InsertO(1)O(1)Append an edge.
DeleteO(deg(u))O(V)Remove an edge from u's list.
UpdateO(deg(u))O(V)Find the edge, then change its weight.
Topological sortO(V + E)O(V + E)
Shortest / longest pathO(V + E)O(V + E)Any edge weights, including negative.
Count pathsO(V + E)O(V + E)
SpaceO(V + E)

Advantages & disadvantages

Advantages
  • Linear-time shortest and longest paths, path counting, and scheduling.
  • A guaranteed evaluation order for dependencies.
  • Cycle detection doubles as validation of the input.
Disadvantages
  • Only applies when the data is genuinely acyclic; a single back edge invalidates every DAG algorithm.
  • Topological orders are not unique, which complicates deterministic output unless a tiebreak is specified.
  • Undirected relationships and feedback loops cannot be modelled.

Use cases

  • Build systems (Make, Bazel), package installation order, CI pipelines.
  • Course Schedule II: emit a valid order or report impossibility.
  • Spreadsheet recalculation and reactive dataflow.
  • Critical-path / PERT scheduling (longest path).
  • Git history, blockchain DAGs, Merkle DAGs (IPFS).
  • Dynamic programming: memoized recursion evaluates the subproblem DAG in topological order.
Use it when
  • Ordering tasks with precedence constraints.
  • Shortest or longest path in a graph you know is acyclic.
  • Any DP whose state transitions form a graph — evaluate in topological order.
Avoid it when

Alternatives

Directed GraphStrongly Connected ComponentsTopological Sort

Common mistakes

  • Not checking that Kahn emitted all V vertices — a cycle silently truncates the order.
  • Forgetting to reverse the DFS post-order.
  • Relaxing edges in an arbitrary order instead of topological order for DAG shortest paths.
  • Mutating the stored in-degree array during Kahn without copying it, breaking a second call.
  • Trying to compute longest paths on a graph with cycles (NP-hard).

Interview patterns

  • Course Schedule I/II: cycle detection and order output.
  • Alien Dictionary: build a DAG of letters, Kahn with a min-heap for lexicographic order.
  • Longest Increasing Path in a Matrix: DFS + memo on the implicit DAG.
  • Parallel Courses / minimum semesters: longest path length.
  • Number of ways to reach a target: path counting DP.
Interview questions on this
Mock interviews

Interview problems

Course SchedulemediumAlien Dictionaryhard