Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesMathReviewsAbout
Language
EnglishTürkçe

Pattern #20

Topological Sort

Advanced

Order nodes so every directed edge goes from earlier to later.

When to use

Prerequisites, build order, or any DAG dependency constraints.

Recognition cues

  • Course schedule / order
  • Alien dictionary
  • Indegree queue (Kahn) or DFS postorder

Common pitfalls

  • Not detecting cycles (incomplete order)
  • Building the graph in the wrong direction
  • Multiple valid orders: any is fine unless specified

90-second recognition drill

Which pattern fits best?

  • Course schedule / order
  • Alien dictionary
  • Indegree queue (Kahn) or DFS postorder

Interactive

Mental model

A full worked walkthrough of the invariant. Pause, scrub the dots, or use ← →. Aim to narrate each step yourself.

Step 1 of 8
A
B
C
D

indegree A0 B1 C1 D2

Prereq graph: A before B and C; B and C before D.

How to think about it

In a DAG, nodes with indegree 0 can come first. Kahn’s algorithm: queue them, emit, reduce neighbors’ indegrees. If you emit fewer than n nodes, a cycle exists. DFS variant: add node to front after exploring children.

Template shapes

Shape Core move Notes
Kahn BFS Indegree + queue Detect cycle by count
DFS Recursion stack colors Postorder prepend
Lex smallest Min-heap instead of queue Deterministic order

Complexity baseline

O(V+E) time and space.

From template to problem

  1. Build adjacency list and indegree array.
  2. Enqueue all indegree 0.
  3. Pop, append to order, decrement neighbors; enqueue if 0.
  4. If order.length < n → cycle / impossible.

Template

Same skeleton in TypeScript, Python, and C#. Adapt the invariant; keep the structure.

Topological Sort · Template
/** Topo template: Kahn BFS; empty array if cycle. */
export function topoSort(n: number, edges: number[][]): number[] {
  const g: number[][] = Array.from({ length: n }, () => []);
  const indeg = new Array(n).fill(0);
  for (const [u, v] of edges) {
    g[u!]!.push(v!);
    indeg[v!]++;
  }
  const q: number[] = [];
  for (let i = 0; i < n; i++) if (indeg[i] === 0) q.push(i);
  const order: number[] = [];
  while (q.length) {
    const u = q.shift()!;
    order.push(u);
    for (const v of g[u]!) if (--indeg[v]! === 0) q.push(v);
  }
  return order.length === n ? order : [];
}

/** Topo template: Kahn BFS; empty array if cycle. */
export function topoSort(n: number, edges: number[][]): number[] {
  const g: number[][] = Array.from({ length: n }, () => []);
  const indeg = new Array(n).fill(0);
  for (const [u, v] of edges) {
    g[u!]!.push(v!);
    indeg[v!]++;
  }
  const q: number[] = [];
  for (let i = 0; i < n; i++) if (indeg[i] === 0) q.push(i);
  const order: number[] = [];
  while (q.length) {
    const u = q.shift()!;
    order.push(u);
    for (const v of g[u]!) if (--indeg[v]! === 0) q.push(v);
  }
  return order.length === n ? order : [];
}

Path

Start pathView in problem browser →
#StatusProblemTypeDone
  1. 1#207 Course ScheduleGuide
  2. 2#210 Course Schedule IIGuide
  3. 3#269 Alien DictionaryGuide
  4. 4#310 Minimum Height TreesGuide
  5. 5#1136 Parallel CoursesGuide
  6. 6#1203 Sort Items by Groups Respecting DependenciesGuide