Topological Sort — The Complete Guide

Kahn's Algorithm (BFS / In-degree approach):
  1. Count in-degrees (number of incoming edges) for each node
  2. Start with all nodes that have in-degree 0 (no dependencies)
  3. Process them, reduce in-degrees of their neighbors
  4. When a neighbor's in-degree hits 0, add it to the queue
  5. If all nodes are processed → valid order. If not → cycle exists.

DFS Post-Order approach:
  1. Run DFS from each unvisited node
  2. After visiting ALL descendants of a node, add it to a stack
  3. The stack (reversed) gives the topological order
  4. If you encounter a node that's "in progress" → cycle detected.

Both produce valid topological orderings. Kahn's is more intuitive
for most people and naturally gives the order left-to-right.
DFS is more concise and useful when you need post-order processing.

function topoSortKahn(
  numNodes: number,
  edges: [number, number][] // [from, to] = from must come before to
): number[] {
  // 1. Build adjacency list and in-degree array
  const graph: number[][] = Array.from({ length: numNodes }, () => []);
  const inDegree = new Array(numNodes).fill(0);

  for (const [from, to] of edges) {
    graph[from].push(to);
    inDegree[to]++;
  }

  // 2. Initialize queue with all in-degree 0 nodes
  const queue: number[] = [];
  for (let i = 0; i < numNodes; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  // 3. BFS: process nodes, reduce neighbors' in-degrees
  const order: number[] = [];

  while (queue.length) {
    const node = queue.shift()!;
    order.push(node);

    for (const neighbor of graph[node]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) {
        queue.push(neighbor);
      }
    }
  }

  // 4. Cycle detection: if not all nodes processed, cycle exists
  if (order.length !== numNodes) {
    return []; // cycle detected — no valid ordering
  }

  return order;
}
// Time: O(V + E) — each node and edge processed once
// Space: O(V + E) — adjacency list + in-degree array + queue

function topoSortDFS(
  numNodes: number,
  edges: [number, number][]
): number[] {
  const graph: number[][] = Array.from({ length: numNodes }, () => []);
  for (const [from, to] of edges) {
    graph[from].push(to);
  }

  // 0 = unvisited, 1 = in progress (gray), 2 = done (black)
  const state = new Array(numNodes).fill(0);
  const order: number[] = [];
  let hasCycle = false;

  function dfs(node: number): void {
    if (hasCycle) return;
    if (state[node] === 1) { hasCycle = true; return; } // cycle!
    if (state[node] === 2) return; // already processed

    state[node] = 1; // mark in progress

    for (const neighbor of graph[node]) {
      dfs(neighbor);
    }

    state[node] = 2; // mark done
    order.push(node); // post-order: add AFTER all descendants
  }

  for (let i = 0; i < numNodes; i++) {
    if (state[i] === 0) dfs(i);
  }

  if (hasCycle) return [];

  return order.reverse(); // reverse post-order = topological order
}
// Why reverse? In DFS post-order, a node is added AFTER its descendants.
// So descendants appear before the node in the array.
// Reversing gives us: node before descendants = topological order.

function alienOrder(words: string[]): string {
  // 1. Initialize graph for all characters that appear
  const graph = new Map<string, Set<string>>();
  const inDegree = new Map<string, number>();

  for (const word of words) {
    for (const ch of word) {
      if (!graph.has(ch)) graph.set(ch, new Set());
      if (!inDegree.has(ch)) inDegree.set(ch, 0);
    }
  }

  // 2. Derive edges by comparing adjacent words
  for (let i = 0; i < words.length - 1; i++) {
    const w1 = words[i], w2 = words[i + 1];
    // Edge case: "abc" before "ab" is invalid (longer word can't come first)
    if (w1.length > w2.length && w1.startsWith(w2)) return "";

    for (let j = 0; j < Math.min(w1.length, w2.length); j++) {
      if (w1[j] !== w2[j]) {
        // First difference: w1[j] comes before w2[j]
        if (!graph.get(w1[j])!.has(w2[j])) {
          graph.get(w1[j])!.add(w2[j]);
          inDegree.set(w2[j], (inDegree.get(w2[j]) ?? 0) + 1);
        }
        break; // only the FIRST difference matters
      }
    }
  }

  // 3. Kahn's algorithm
  const queue: string[] = [];
  for (const [ch, deg] of inDegree) {
    if (deg === 0) queue.push(ch);
  }

  const order: string[] = [];
  while (queue.length) {
    const ch = queue.shift()!;
    order.push(ch);
    for (const neighbor of graph.get(ch)!) {
      inDegree.set(neighbor, inDegree.get(neighbor)! - 1);
      if (inDegree.get(neighbor) === 0) queue.push(neighbor);
    }
  }

  // Cycle check
  if (order.length !== inDegree.size) return "";

  return order.join("");
}
// Key insight: only the FIRST differing character between adjacent
// words gives us an edge. Characters after that tell us nothing.

function minimumSemesters(n: number, relations: number[][]): number {
  const graph: number[][] = Array.from({ length: n + 1 }, () => []);
  const inDegree = new Array(n + 1).fill(0);

  for (const [prev, next] of relations) {
    graph[prev].push(next);
    inDegree[next]++;
  }

  const queue: number[] = [];
  for (let i = 1; i <= n; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  let semesters = 0;
  let processed = 0;

  while (queue.length) {
    semesters++;
    const levelSize = queue.length; // courses this semester

    for (let i = 0; i < levelSize; i++) {
      const course = queue.shift()!;
      processed++;

      for (const next of graph[course]) {
        inDegree[next]--;
        if (inDegree[next] === 0) queue.push(next);
      }
    }
  }

  return processed === n ? semesters : -1; // -1 if cycle
}
// Same as regular Kahn's, but we count BFS levels.
// Each level = one semester of parallel courses.

Graph (6 nodes, edges represent "must come before"):
  5 → 0, 5 → 2
  4 → 0, 4 → 1
  2 → 3
  3 → 1

Adjacency list:
  0: []    1: []    2: [3]    3: [1]    4: [0, 1]    5: [0, 2]

In-degrees:
  0: 2 (from 5, 4)
  1: 2 (from 4, 3)
  2: 1 (from 5)
  3: 1 (from 2)
  4: 0 ← start here
  5: 0 ← start here

Step 1: Queue = [4, 5], order = []
  Process 4: reduce in-degree of 0 (→1), 1 (→1)
  Process 5: reduce in-degree of 0 (→0 ✓), 2 (→0 ✓)
  Queue = [0, 2], order = [4, 5]

Step 2: Queue = [0, 2]
  Process 0: no neighbors
  Process 2: reduce in-degree of 3 (→0 ✓)
  Queue = [3], order = [4, 5, 0, 2]

Step 3: Queue = [3]
  Process 3: reduce in-degree of 1 (→0 ✓)
  Queue = [1], order = [4, 5, 0, 2, 3]

Step 4: Queue = [1]
  Process 1: no neighbors
  Queue = [], order = [4, 5, 0, 2, 3, 1]

All 6 nodes processed → valid topological order: [4, 5, 0, 2, 3, 1]

Note: [5, 4, 2, 0, 3, 1] is also valid — topo sort isn't unique.

Same graph: 5→0, 5→2, 4→0, 4→1, 2→3, 3→1

DFS from node 0 (unvisited):
  0 has no neighbors → post-order: add 0
  Stack: [0]

DFS from node 1 (unvisited):
  1 has no neighbors → post-order: add 1
  Stack: [0, 1]

DFS from node 2 (unvisited):
  Visit 3 → visit 1 (already done, skip) → add 3
  Back to 2 → add 2
  Stack: [0, 1, 3, 2]

DFS from node 3 (already done, skip)

DFS from node 4 (unvisited):
  Visit 0 (done), visit 1 (done) → add 4
  Stack: [0, 1, 3, 2, 4]

DFS from node 5 (unvisited):
  Visit 0 (done), visit 2 (done) → add 5
  Stack: [0, 1, 3, 2, 4, 5]

Reverse stack: [5, 4, 2, 3, 1, 0]

Valid topological order: [5, 4, 2, 3, 1, 0] ✓
(Different from Kahn's result, but both are valid.)

Graph with cycle: 0→1, 1→2, 2→0 (cycle: 0→1→2→0)

═══ Kahn's Algorithm ═══
In-degrees: 0:1, 1:1, 2:1
No node has in-degree 0 → queue starts empty!
Processed = 0, numNodes = 3 → 0 ≠ 3 → CYCLE DETECTED

═══ DFS Three-State ═══
DFS from 0: state[0] = GRAY (in progress)
  Visit 1: state[1] = GRAY
    Visit 2: state[2] = GRAY
      Visit 0: state[0] = GRAY → CYCLE DETECTED!
      (We found a node that's still "in progress" — we're in a loop)

Both methods detect the cycle. Kahn's detects it passively
(not all nodes processed). DFS detects it actively (gray node revisited).

Is there a dependency/ordering relationship?
├── YES → Model as directed graph (prerequisite → dependent)
│   ├── "Can all tasks be completed?" (cycle detection)
│   │   → Kahn's: check processed === numNodes
│   ├── "Find a valid ordering"
│   │   → Kahn's: return the order array
│   ├── "Minimum time with parallel execution"
│   │   → Kahn's with level counting (BFS levels = time units)
│   ├── "Lexicographically smallest ordering"
│   │   → Kahn's with min-heap instead of queue
│   ├── "Derive ordering from comparisons" (alien dictionary)
│   │   → Extract edges from adjacent comparisons → Kahn's
│   ├── "Longest path in DAG"
│   │   → Topo sort → DP forward pass
│   └── "Is the ordering unique?"
│       → Kahn's: unique iff queue never has > 1 element
└── NO → Not a topological sort problem
    → Consider: BFS/DFS traversal, Union-Find, shortest path