What Is a Directed Acyclic Graph (DAG)? The Interview Guide

Every package manager you've ever used runs on one. So does your build system, your git commit history, and the dependency graph underlying almost every dynamic programming solution you've written. The directed acyclic graph, or DAG, shows up more often than most candidates realize. And in interviews, it's one of those structures that shows up in disguise: it's never labeled, but once you see it, the whole problem clicks.

What Two Rules Make a Graph a DAG?

Both have to hold at the same time.

Directed means every edge has a direction. An edge from node A to node B does not imply an edge from B to A. Think one-way streets, not your usual two-way road.

Acyclic means there is no path that starts at a node and follows directed edges back to that same node. No loops. No scenic detours that loop back. If you can start at A and somehow follow edges back to A, the graph has a cycle and it is not a DAG.

A directed graph with cycles is just a directed graph. A directed graph with no cycles is a DAG, and that single constraint unlocks a set of algorithms that simply don't work on cyclic graphs. The constraint sounds small. The payoff is enormous.

DAGs Live Wherever Dependencies Do

The acyclic property makes DAGs natural anywhere you have dependencies that can't be circular. Whenever something must come before something else, and that ordering can never loop back on itself, you've got a DAG.

Domain	Nodes	Directed edges mean
Package manager (npm, pip)	packages	"A requires B"
Build system (Make, Bazel)	build targets	"X must build before Y"
Course prerequisites	courses	"take A before B"
Git history	commits	"parent precedes child"
Task scheduling	tasks	"A must finish before B starts"
DP memoization	subproblems	"A uses the result of B"

That last row is the one most engineers miss entirely. Every memoized recursion defines a DAG implicitly. Each subproblem is a node. Each recursive call is a directed edge pointing toward a smaller subproblem. Because memoization only terminates when subproblems don't depend on themselves, the dependency graph is always acyclic. Always a DAG.

Why Cycles Break Everything

Picture npm encountering a circular dependency: package A requires B, B requires C, C requires A. Which one do you install first? There is no valid answer. The whole operation deadlocks before a line of code runs. You just wanted to add a date formatting library. Now you're staring at an error and reconsidering your career.

Every sufficiently old Linux installation has its own load-bearing GNOME.

The acyclic constraint is what makes ordering possible. If a directed graph has no cycles, you can always arrange its nodes in a line such that every edge points from left to right. That arrangement is called a topological ordering, and it only exists for DAGs.

Try to run topological sort on a cyclic graph and one of two things happens: your algorithm hangs, or it silently finishes without processing all nodes. Kahn's algorithm actually uses this as a cycle detection mechanism. If the output list is shorter than the total node count, a cycle exists somewhere.

How to Check If a Directed Graph Has a Cycle

Three-color DFS is the standard approach. Assign each node one of three states:

• White: unvisited
• Gray: currently on the DFS call stack (being explored right now)
• Black: fully explored and done

If you ever follow an edge to a gray node, you've found a back edge, which means a cycle. You're in the middle of exploring a node and just found a path back to it. Gray is the smoking gun.

def is_dag(graph: dict[int, list[int]]) -> bool:
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}

    def dfs(node: int) -> bool:  # returns True if cycle found
        color[node] = GRAY
        for neighbor in graph[node]:
            if color[neighbor] == GRAY:
                return True
            if color[neighbor] == WHITE and dfs(neighbor):
                return True
        color[node] = BLACK
        return False

    return not any(dfs(node) for node in graph if color[node] == WHITE)

A simple visited set works for undirected graphs. For directed graphs, you need the three-color distinction. Visited-but-not-done (gray) is what catches cycles that a boolean would miss. For a deeper look at how DFS works on graphs generally, see the guide on depth-first search.

How to Find a Topological Ordering

A topological ordering is a linear sequence of all nodes where every directed edge goes from earlier to later in the sequence. For any DAG, at least one such ordering exists. Often many do.

Two algorithms find one.

Kahn's algorithm (BFS-based): compute in-degree for every node. Nodes with in-degree 0 have no prerequisites and can come first. Push them into a queue. Process each node, decrement its neighbors' in-degrees, and add any neighbor that hits 0 to the queue. The processing order is a valid topological sort.

from collections import deque

def topological_sort(graph: dict[int, list[int]], num_nodes: int) -> list[int]:
    in_degree = [0] * num_nodes
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1

    queue = deque(n for n in range(num_nodes) if in_degree[n] == 0)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return order if len(order) == num_nodes else []

DFS postorder reversal: run DFS on the whole graph. When DFS finishes exploring a node (all descendants done), append it to a list. Reverse at the end. That reversed postorder is a valid topological sort.

Both run in O(V + E). Kahn's has one practical advantage: a cycle shows up as an incomplete output list, so you get cycle detection for free without separate bookkeeping. The full breakdown with both implementations is in the topological sort guide.

DAGs and Dynamic Programming: The Same Idea Twice

This is the insight that clicks once and you can't unsee it: every bottom-up DP table is a topological traversal of a DAG.

When you write a 1D DP loop where dp[i] depends on dp[i-1], you are filling a DAG in topological order, left to right. When you fill a 2D grid top-to-bottom for a path problem, same thing. The cells form a DAG. The fill order is a topological sort of that DAG.

The subproblem dependency graph is always a DAG, and the order in which you fill the table is always a topological sort of that DAG. Once you see this, the relationship between graph problems and DP problems stops being mysterious. Longest path in a DAG is DP. Counting paths is DP. Both are O(V + E) because the acyclic structure lets you process each node exactly once.

See the dynamic programming guide for the full treatment.

What These Problems Look Like in the Wild

You will not see a problem titled "is this a DAG?" It shows up dressed as something else. The actual skill is pattern recognition.

Course Schedule (LeetCode 207): can you complete all courses given prerequisites? Cycle detection on a directed graph. If there's a cycle, the answer is no. Run three-color DFS or check whether Kahn's produces a full ordering.

Course Schedule II (LeetCode 210): return a valid order to take all courses. Topological sort. If no valid order exists, return an empty array.

Alien Dictionary (LeetCode 269): given words sorted in an alien language, determine the character order. Compare adjacent words to extract ordering constraints (each is a directed edge), then topological sort the character graph.

Parallel Courses (LeetCode 1136): minimum semesters to finish all courses. Topological sort plus BFS layer counting. Each BFS layer in Kahn's is one semester.

Longest increasing path in a matrix (LeetCode 329): each cell can only move to strictly larger neighbors, so the implicit graph is a DAG. Run DFS with memoization. No visited set needed because the structure guarantees termination.

Problem	LeetCode	Core operation
Course Schedule	207	Cycle detection
Course Schedule II	210	Topological sort
Alien Dictionary	269	Build graph + topo sort
Parallel Courses	1136	BFS layer count on DAG
Longest Increasing Path	329	DFS + memo on implicit DAG

DAG problems in an interview: same energy.

Every DAG Algorithm Runs O(V + E)

For a DAG with V vertices and E edges:

Operation	Time	Space
Cycle detection (DFS)	O(V + E)	O(V)
Topological sort (Kahn's)	O(V + E)	O(V)
Topological sort (DFS postorder)	O(V + E)	O(V)
Longest path via DP	O(V + E)	O(V)
Counting paths	O(V + E)	O(V)

Everything is O(V + E). The acyclic property guarantees DFS won't revisit nodes, and the directed structure gives you a processing order you can exploit. On a general directed graph with cycles, longest path and counting all paths both go NP-hard. The acyclic constraint is doing real work here.

Quick Reference

• Directed + no cycles = DAG. Both constraints must hold.
• Topological ordering: always exists for any DAG, never exists for cyclic graphs.
• Cycle detection: three-color DFS. A gray-to-gray back edge means a cycle.
• Topological sort: Kahn's (in-degree BFS) or DFS postorder reversal, both O(V + E).
• Kahn's cycle check: if len(output) < V, a cycle exists somewhere.
• Every DP table fill is a topological traversal of the subproblem DAG.
• Problems: Course Schedule 207/210, Alien Dictionary 269, Parallel Courses 1136, Longest Increasing Path 329.

If you want to practice walking through a DAG problem out loud, explaining your cycle detection choice, and extending the solution to the DP framing, SpaceComplexity runs voice-based mock interviews on exactly these kinds of graph problems with rubric-based feedback on your reasoning and communication. The gap between solving a problem silently and explaining it clearly is where most offers are won or lost.

Further Reading

• Directed acyclic graph, Wikipedia
• Topological sorting, Wikipedia
• Detect Cycle in a Directed Graph, GeeksforGeeks
• Topological Sorting, GeeksforGeeks
• Course Schedule, LeetCode