12. Topological Sort

TL;DR

Topological sort produces a linear ordering of vertices in a directed acyclic graph (DAG) such that every edge u → v has u before v. Kahn’s algorithm repeatedly peels vertices with in-degree zero (BFS on the “ready” layer). DFS with three colors finishes with a reverse post-order list and detects cycles (back edges to gray vertices).

Core Basics

Object: DAG linearization; peel in-degree zero (Kahn) or reverse postorder from DFS 3-color (+ cycle detection).
Impossibility: unfinished nodes with empty ready queue ⇒ cycle.
Staff-level bar: compare with strongly connected components when the graph is not a DAG.

Recognition Cues

Phrases: “prerequisites,” “course schedule,” “ordering with constraints,” “dependencies,” “build order,” “Compilation order,” “Alien dictionary characters.”
Input: directed edges, often numCourses + edge list.
Output: any valid order, or impossible if cycle; sometimes lexicographically smallest (tie-break via min-heap).

Use-case Lens

Best when: tasks/courses/build steps have prerequisites and you need a valid order or cycle detection.
Not for: undirected connectivity; use DFS/BFS/DSU.
Main invariant: nodes with indegree 0 have no remaining unmet prerequisite and are safe to schedule.
Interview move: if output has fewer than n nodes, a cycle blocked some prerequisites.

Diagram

Loading diagram…

Step-by-step Visual

Example: Course edges 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3. A node can be taken only when indegree becomes 0.

Loading diagram…

Understanding

In-degree counts “how many parents must happen first.” When it hits zero, the task is ready. If you ever exhaust ready nodes but unfinished work remains, there is a cycle. In DFS coloring: white = unseen, gray = on recursion stack, black = done; an edge to gray means cycle. Topological order is reverse of DFS finish times.

Generic Recipe

Kahn

Build adjacency list and inDegree per node.
Initialize a queue with all nodes where inDegree == 0.
Pop node, append to order; for each neighbor, decrement inDegree; if neighbor hits 0, enqueue.
If order length equals total nodes, DAG OK; else cycle.

DFS 3-color

Mark all white; define recursive visit(node).
On entry: gray; for each edge node → next, if next is gray return cycle; if white, recurse.
On exit: black; push node to finish list.
Reverse finish list for topo order (or use prepend carefully).

Complexity

Time: O(V + E) for both Kahn and DFS over adjacency lists.
Space: O(V + E) for graph plus O(V) for queue/colors and output.

Memory Hooks

Operational mantra: build directed edges, drain zero-indegree nodes, and detect cycles by unfinished work.
Anti-panic: model edges direction first; wrong edge direction makes indegree and final order look plausible but wrong.

Study Pattern (SDE3+)

Recognition drill (10 min): identify prerequisite ordering, alien alphabet, build dependency, and cycle-only prompts.
Implementation sprint (25 min): code Kahn's algorithm and DFS color cycle detection on the same graph.
Staff follow-up (10 min): discuss multiple valid orders, disconnected DAGs, invalid prefix cases, and incremental dependency updates.

Generic Code Template

Go

func topologicalSortKahn(numNodes int, edges [][]int) ([]int, bool) {
	adj := make([][]int, numNodes)
	inDegree := make([]int, numNodes)
	for _, edge := range edges {
		from, to := edge[0], edge[1]
		adj[from] = append(adj[from], to)
		inDegree[to]++
	}
	queue := make([]int, 0)
	for node := 0; node < numNodes; node++ {
		if inDegree[node] == 0 {
			queue = append(queue, node)
		}
	}
	order := make([]int, 0, numNodes)
	head := 0
	for head < len(queue) {
		current := queue[head]
		head++
		order = append(order, current)
		for _, neighbor := range adj[current] {
			inDegree[neighbor]--
			if inDegree[neighbor] == 0 {
				queue = append(queue, neighbor)
			}
		}
	}
	if len(order) != numNodes {
		return nil, false
	}
	return order, true
}

const colorWhite = 0
const colorGray = 1
const colorBlack = 2

func topologicalSortDFS(numNodes int, edges [][]int) ([]int, bool) {
	adj := make([][]int, numNodes)
	for _, edge := range edges {
		from, to := edge[0], edge[1]
		adj[from] = append(adj[from], to)
	}
	color := make([]int, numNodes)
	finishOrder := make([]int, 0, numNodes)
	var hasCycle bool
	var visit func(int)
	visit = func(node int) {
		if hasCycle {
			return
		}
		color[node] = colorGray
		for _, neighbor := range adj[node] {
			if color[neighbor] == colorGray {
				hasCycle = true
				return
			}
			if color[neighbor] == colorWhite {
				visit(neighbor)
			}
		}
		color[node] = colorBlack
		finishOrder = append(finishOrder, node)
	}
	for node := 0; node < numNodes; node++ {
		if color[node] == colorWhite {
			visit(node)
		}
	}
	if hasCycle {
		return nil, false
	}
	for left, right := 0, len(finishOrder)-1; left < right; left, right = left+1, right-1 {
		finishOrder[left], finishOrder[right] = finishOrder[right], finishOrder[left]
	}
	return finishOrder, true
}

JavaScript

function topologicalSortKahn(numNodes, edges) {
  const adj = Array.from({ length: numNodes }, () => []);
  const inDegree = Array(numNodes).fill(0);
  for (const [from, to] of edges) {
    adj[from].push(to);
    inDegree[to] += 1;
  }
  const queue = [];
  for (let node = 0; node < numNodes; node++) {
    if (inDegree[node] === 0) queue.push(node);
  }
  const order = [];
  while (queue.length) {
    const current = queue.shift();
    order.push(current);
    for (const neighbor of adj[current]) {
      inDegree[neighbor] -= 1;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }
  if (order.length !== numNodes) return { order: null, ok: false };
  return { order, ok: true };
}

const COLOR_WHITE = 0;
const COLOR_GRAY = 1;
const COLOR_BLACK = 2;

function topologicalSortDFS(numNodes, edges) {
  const adj = Array.from({ length: numNodes }, () => []);
  for (const [from, to] of edges) adj[from].push(to);
  const color = Array(numNodes).fill(COLOR_WHITE);
  const finishOrder = [];
  let hasCycle = false;

  function visit(node) {
    if (hasCycle) return;
    color[node] = COLOR_GRAY;
    for (const neighbor of adj[node]) {
      if (color[neighbor] === COLOR_GRAY) {
        hasCycle = true;
        return;
      }
      if (color[neighbor] === COLOR_WHITE) visit(neighbor);
    }
    color[node] = COLOR_BLACK;
    finishOrder.push(node);
  }

  for (let node = 0; node < numNodes; node++) {
    if (color[node] === COLOR_WHITE) visit(node);
  }
  if (hasCycle) return { order: null, ok: false };
  finishOrder.reverse();
  return { order: finishOrder, ok: true };
}

Variants

Lexicographically smallest topo order: use min-heap instead of queue for Kahn.
All topological sorts: backtracking (exponential); rarely needed in interviews.
Alien dictionary: build graph between characters, topo sort; careful about cycles and implicit letters.

Representative Problems

207. Course Schedule — cycle / feasibility via Kahn or DFS
210. Course Schedule II — return one valid order
269. Alien Dictionary — implicit graph + topo

Anti-patterns

Assuming one unique order; many valid answers unless constrained.
Using undirected union-find when problem is directed dependency (wrong model).
DFS topo without reversing finish times (order ends up backward).
Building graph with wrong edge direction (prerequisite vs dependent).

On this page