Topological Sort: Kahn's Algorithm & DFS Ordering

A topological sort of a DAG (Directed Acyclic Graph) is a linear ordering of its vertices such that for every directed edge u → v, u comes before v. It answers “in what order can I do these tasks given their dependencies?” — compiling modules, scheduling courses, resolving build steps. A topological order exists if and only if the graph has no cycle; both algorithms below detect that case.

Kahn’s algorithm (BFS / in-degree)

Kahn’s algorithm repeatedly removes vertices that have no remaining prerequisites (in-degree 0):

Compute the in-degree of every vertex.
Put all in-degree-0 vertices in a queue.
Pop one, append it to the order, and decrement the in-degree of each neighbor; if a neighbor drops to 0, enqueue it.
If the final order has fewer than V vertices, the graph had a cycle.

std::vector<int> topoSortKahn(const std::vector<std::vector<int>>& adj) {
    int n = adj.size();
    std::vector<int> indeg(n, 0), order;
    for (int u = 0; u < n; u++) for (int v : adj[u]) indeg[v]++;
    std::queue<int> q;
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u]) if (--indeg[v] == 0) q.push(v);
    }
    if ((int)order.size() != n) return {};   // cycle -> no valid order
    return order;
}

List<Integer> topoSortKahn(List<List<Integer>> adj) {
    int n = adj.size();
    int[] indeg = new int[n];
    for (int u = 0; u < n; u++) for (int v : adj.get(u)) indeg[v]++;
    Queue<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
    List<Integer> order = new ArrayList<>();
    while (!q.isEmpty()) {
        int u = q.poll();
        order.add(u);
        for (int v : adj.get(u)) if (--indeg[v] == 0) q.add(v);
    }
    if (order.size() != n) return new ArrayList<>();  // cycle
    return order;
}

function topoSortKahn(adj) {
  const n = adj.length;
  const indeg = new Array(n).fill(0);
  for (let u = 0; u < n; u++) for (const v of adj[u]) indeg[v]++;
  const queue = [];
  for (let i = 0; i < n; i++) if (indeg[i] === 0) queue.push(i);
  const order = [];
  let head = 0;
  while (head < queue.length) {
    const u = queue[head++];
    order.push(u);
    for (const v of adj[u]) if (--indeg[v] === 0) queue.push(v);
  }
  return order.length === n ? order : [];   // cycle -> empty
}

from collections import deque

def topo_sort_kahn(adj):
    n = len(adj)
    indeg = [0] * n
    for u in range(n):
        for v in adj[u]:
            indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else []   # cycle -> empty

Tip: Swap the queue for a min-priority-queue to get the lexicographically smallest topological order — a common interview follow-up.

DFS-based topological sort

Run DFS; when a vertex finishes (all its descendants are processed), push it onto a stack. The reversed finish order is a valid topological order. Intuitively, a vertex finishes only after everything it points to, so it ends up earlier when reversed.

void dfsTopo(int u, const std::vector<std::vector<int>>& adj,
             std::vector<bool>& visited, std::vector<int>& out) {
    visited[u] = true;
    for (int v : adj[u]) if (!visited[v]) dfsTopo(v, adj, visited, out);
    out.push_back(u);                 // push on finish
}
std::vector<int> topoSortDFS(const std::vector<std::vector<int>>& adj) {
    int n = adj.size();
    std::vector<bool> visited(n, false);
    std::vector<int> out;
    for (int i = 0; i < n; i++) if (!visited[i]) dfsTopo(i, adj, visited, out);
    std::reverse(out.begin(), out.end());
    return out;
}

void dfsTopo(int u, List<List<Integer>> adj, boolean[] visited, Deque<Integer> out) {
    visited[u] = true;
    for (int v : adj.get(u)) if (!visited[v]) dfsTopo(v, adj, visited, out);
    out.push(u);                      // push on finish (stack)
}
List<Integer> topoSortDFS(List<List<Integer>> adj) {
    int n = adj.size();
    boolean[] visited = new boolean[n];
    Deque<Integer> out = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (!visited[i]) dfsTopo(i, adj, visited, out);
    return new ArrayList<>(out);      // popping the stack = reversed finish
}

function topoSortDFS(adj) {
  const n = adj.length;
  const visited = new Array(n).fill(false);
  const out = [];
  function dfs(u) {
    visited[u] = true;
    for (const v of adj[u]) if (!visited[v]) dfs(v);
    out.push(u);                      // push on finish
  }
  for (let i = 0; i < n; i++) if (!visited[i]) dfs(i);
  return out.reverse();
}

def topo_sort_dfs(adj):
    n = len(adj)
    visited = [False] * n
    out = []
    def dfs(u):
        visited[u] = True
        for v in adj[u]:
            if not visited[v]:
                dfs(v)
        out.append(u)                 # push on finish
    for i in range(n):
        if not visited[i]:
            dfs(i)
    out.reverse()
    return out

Pitfall: The plain DFS version does not report cycles — on a cyclic graph it still returns an order. If you need cycle safety, prefer Kahn’s algorithm (it naturally returns fewer than V vertices) or add the three-color cycle check to the DFS.

Complexity and uses

Both algorithms run in O(V + E) time and O(V) extra space. Use topological sort for dependency resolution, course scheduling (the classic course schedule problem), build systems, and as a preprocessing step for shortest/longest paths on a DAG.

Next up: weighted shortest paths with Dijkstra’s algorithm.