Module A-8·12 min read

Linear ordering of a DAG — Kahn's algorithm, DFS post-order, and cycle detection in directed graphs.

Written by Jatin Jain Saraf · Architect of SupraScan

Module A-8 — Topological Sort: Kahn's Algorithm and DFS-Based Ordering

What this module covers: Given a set of tasks with dependencies — task B can't run until task A finishes — what's a valid order to run all of them? This module covers two different ways to answer that question: Kahn's algorithm, built on Module F-7's queue and Module P-6's in-degree concept, and a DFS-based approach (Module A-4) that arrives at the same answer from the opposite direction. Both double as cycle detectors: no valid order exists if the dependencies contain a cycle.

The Problem: Ordering a DAG

A topological sort is a linear ordering of a directed graph's nodes such that for every edge u → v, u appears before v in the ordering. This only makes sense on a directed acyclic graph (DAG) — Module P-6 already flagged that this requires directionality; a cycle makes the question unanswerable, since a cycle A → B → A would require A before B and B before A simultaneously.

Kahn's Algorithm: Start With What Has No Prerequisites

Kahn's algorithm is structurally a BFS (Module A-5): repeatedly process nodes with no remaining unprocessed dependencies, using Module P-6's in-degree (number of incoming edges) to track exactly that.

function topologicalSortKahn(graph: Map<string, string[]>): string[] | null {
  const inDegree = new Map<string, number>();
 
  // Initialize every node's in-degree to 0, then count actual incoming edges
  for (const node of graph.keys()) inDegree.set(node, 0);
  for (const neighbors of graph.values()) {
    for (const neighbor of neighbors) {
      inDegree.set(neighbor, (inDegree.get(neighbor) ?? 0) + 1);
    }
  }
 
  // Start with every node that has NO prerequisites at all
  const queue: string[] = [];
  for (const [node, degree] of inDegree) {
    if (degree === 0) queue.push(node);
  }
 
  const order: string[] = [];
  while (queue.length > 0) {
    const node = queue.shift()!; // Module F-7
    order.push(node);
 
    for (const neighbor of graph.get(node) ?? []) {
      inDegree.set(neighbor, inDegree.get(neighbor)! - 1); // one of this neighbor's prerequisites is now satisfied
      if (inDegree.get(neighbor) === 0) queue.push(neighbor); // all its prerequisites are now satisfied
    }
  }
 
  // If not every node made it into the order, some nodes' in-degree never hit zero — a cycle
  return order.length === inDegree.size ? order : null;
}

Every node starting with in-degree 0 has no unmet dependency — it's safe to run first. Processing it "removes" its outgoing edges by decrementing each neighbor's in-degree, and any neighbor whose in-degree just hit zero has had its last remaining prerequisite satisfied, making it newly eligible. This is precisely BFS's layer-by-layer discipline (Module A-5), just measuring "layer" by dependency depth rather than hop distance from a single start node. The cycle check is built directly into the completion condition: if a cycle exists, every node inside it permanently retains an in-degree above zero (each depends on another node in the same cycle, which can never be fully "satisfied" first), so those nodes never enter the queue at all — the final order comes up short, and the length mismatch is the detection signal.

DFS-Based Topological Sort: Postorder, Then Reverse

A different route to the same answer, built on Module A-4's DFS and Module P-4's postorder traversal: run DFS, and every time a node finishes being explored (everything reachable from it — every node that depends on it — has been fully processed) push it onto a result list — then reverse that list at the end.

function topologicalSortDFS(graph: Map<string, string[]>): string[] | null {
  const visited = new Set<string>();
  const inProgress = new Set<string>(); // nodes currently on the current DFS path — detects back-edges
  const result: string[] = [];
  let hasCycle = false;
 
  function dfs(node: string): void {
    if (hasCycle) return;
    if (inProgress.has(node)) { hasCycle = true; return; } // reached a node already on the current path — a cycle
    if (visited.has(node)) return;
 
    inProgress.add(node);
    for (const neighbor of graph.get(node) ?? []) {
      dfs(neighbor);
    }
    inProgress.delete(node);
 
    visited.add(node);
    result.push(node); // postorder — Module P-4: push AFTER everything this node points to is fully explored
  }
 
  for (const node of graph.keys()) {
    if (!visited.has(node)) dfs(node);
  }
 
  return hasCycle ? null : result.reverse();
}