Directed Acyclic Graph DAG from Scratch (2026)
A Directed Acyclic Graph (DAG) is a directed graph with no cycles. DAGs are fundamental in computer science for modeling dependencies, scheduling tasks, representing data flow, and solving optimization problems. The absence of cycles allows for topological ordering, which is a linear ordering of vertices such that for every directed edge (u, v), vertex u comes before v in the ordering.
In this tutorial, we will explore DAG properties, implement topological sorting using DFS and Kahn's algorithm, find the longest path in a DAG, and examine real-world applications like build systems, course prerequisites, and task scheduling.
Topological Ordering - DFS Approach
Topological sorting arranges the vertices of a DAG in a linear order where every directed edge points from an earlier vertex to a later vertex. The DFS approach works by performing a DFS and adding each vertex to the front of the result list when all its descendants have been visited (post-order). Reversing the post-order gives a valid topological order.
The DFS approach runs in O(V + E) time. It naturally detects cycles: if a vertex is encountered that is currently in the recursion stack, the graph has a cycle and topological ordering is not possible.
from collections import defaultdict
class DAG:
def __init__(self, vertices):
self.V = vertices
self.adj = defaultdict(list)
def add_edge(self, u, v):
self.adj[u].append(v)
def topological_sort_dfs(self):
visited = set()
stack = []
def dfs(v):
visited.add(v)
for nb in self.adj[v]:
if nb not in visited: dfs(nb)
stack.append(v)
for i in range(self.V):
if i not in visited: dfs(i)
return stack[::-1]
dag = DAG(6)
dag.add_edge(5, 2); dag.add_edge(5, 0)
dag.add_edge(4, 0); dag.add_edge(4, 1)
dag.add_edge(2, 3); dag.add_edge(3, 1)
print(dag.topological_sort_dfs()) # [5,4,2,3,1,0]Topological Ordering - Kahn's Algorithm
Kahn's algorithm uses BFS and in-degree counting to produce a topological ordering. We compute the in-degree of every vertex and add all vertices with in-degree zero to a queue. We repeatedly dequeue a vertex, add it to the result, and decrement the in-degree of its neighbors. If a neighbor's in-degree becomes zero, we enqueue it.
Kahn's algorithm also detects cycles: if not all vertices are processed, the remaining vertices form a cycle. This algorithm is simpler to implement and more intuitive than the DFS approach.
#include
#include
#include
using namespace std;
vector kahnTopologicalSort(vector>& adj, int V) {
vector inDegree(V, 0);
for (int i = 0; i < V; i++)
for (int nb : adj[i]) inDegree[nb]++;
queue q;
for (int i = 0; i < V; i++)
if (inDegree[i] == 0) q.push(i);
vector result;
while (!q.empty()) {
int u = q.front(); q.pop();
result.push_back(u);
for (int v : adj[u]) {
if (--inDegree[v] == 0) q.push(v);
}
}
if (result.size() != V) { cout << "Cycle!"; return {}; }
return result;
} Longest Path in a DAG
Finding the longest path in a general graph is NP-hard, but in a DAG it can be solved efficiently in O(V + E) time using dynamic programming with topological sort. After obtaining a topological order, we process vertices in that order, updating the longest distance to each vertex. For each vertex u, we relax all edges (u, v) by checking if dist[u] + weight(u, v) > dist[v].
This technique is used in project scheduling (critical path), longest chain in a sequence, and optimal ordering problems.
import java.util.*;
class DAG {
private int V;
private List> adj;
DAG(int v) { V = v; adj = new ArrayList<>();
for (int i = 0; i < v; i++) adj.add(new ArrayList<>()); }
void addEdge(int u, int v, int w) { adj.get(u).add(new int[]{v, w}); }
int[] longestPath(int source) {
int[] topo = topologicalSort();
int[] dist = new int[V];
Arrays.fill(dist, Integer.MIN_VALUE);
dist[source] = 0;
for (int u : topo) {
if (dist[u] != Integer.MIN_VALUE)
for (int[] e : adj.get(u))
dist[e[0]] = Math.max(dist[e[0]], dist[u] + e[1]);
}
return dist;
}
} DAG Applications and Properties
DAGs are used extensively in build systems (Make, Bazel) to represent compilation dependencies, in version control (Git) for commit history, in databases for query optimization, and in machine learning for computational graphs. Every finite DAG has at least one vertex with in-degree zero (source) and one with out-degree zero (sink).
DAGs also support dynamic programming directly: the lack of cycles means we can compute optimal substructure properties by processing vertices in topological order. This is the basis for solving many optimization problems on DAGs efficiently.
from collections import defaultdict
def is_dag(vertices, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
WHITE, GRAY, BLACK = 0, 1, 2
color = {v: WHITE for v in range(vertices)}
def has_cycle(v):
color[v] = GRAY
for nb in graph[v]:
if color[nb] == GRAY: return True
if color[nb] == WHITE and has_cycle(nb): return True
color[v] = BLACK
return False
for v in range(vertices):
if color[v] == WHITE and has_cycle(v): return False
return TrueFrequently Asked Questions
What is a DAG?
A Directed Acyclic Graph (DAG) is a directed graph with no directed cycles. It has a topological ordering and supports efficient algorithms for longest path, scheduling, and dependency resolution.
How to detect a cycle in a directed graph?
Use DFS with three colors (white/gray/black) or Kahn's algorithm with in-degree counting. If DFS encounters a gray vertex, or if Kahn's algorithm does not process all vertices, a cycle exists.
What is topological sort?
Topological sort is a linear ordering of vertices in a DAG such that for every directed edge (u, v), vertex u comes before v. It can be computed using DFS post-order or Kahn's BFS algorithm.
Why is longest path easy in a DAG?
Because a DAG has no cycles, we can process vertices in topological order and use dynamic programming. In a general graph, the longest path problem is NP-hard due to cycles.
Originally published on Ayodhyyya. Last updated June 1, 2026.