Topological Sort Complete Guide

Algorithm • extra hard

Topological sort returns a valid order of tasks in a directed acyclic graph (DAG) where dependencies appear before dependents.

If a cycle exists, no topological order is possible.

Core algorithms: Kahn's BFS by indegree and DFS finishing-order approach.

Typical Complexity Baseline

Metric	Value
Complexity Note 1	`O(V + E)`

See It

Concept Diagram

A small animated SVG that illustrates the core idea the moving parts you need to keep in your head when you read the rest of the guide.

Topological sort schedule a DAG

Peel nodes whose dependencies are already done. Arrows always point earlier → later.

Step 1/10Init: in-degrees calculated. Seed queue with nodes whose in-degree is 0 → [A].

Speed

Watch First

Video Explainer

A quick visual walkthrough before the detailed sections pick the format that helps you learn fastest.

Topological Sort Visualized and Explained

Channel: Carl the Person

Watch on YouTube →

Mechanics

Core Concepts

The building blocks and terminology you need before everything else clicks. Skim or deep-read.

Indegree

What it is Count of incoming edges per node. Number of prerequisites for node.

Why it matters Indegree is a required building block for understanding how Topological Sort stays correct and performant on large inputs. Number of prerequisites for node. In Topological Sort, this definition helps you reason about correctness and complexity when inputs scale.

Zero-indegree queue

What it is Nodes currently ready to execute.

Why it matters Zero-indegree queue is a required building block for understanding how Topological Sort stays correct and performant on large inputs.

Adjacency list

What it is Outgoing dependency edges.

Why it matters Adjacency list is a required building block for understanding how Topological Sort stays correct and performant on large inputs.

Processed count

What it is Used to detect cycles if < total nodes.

Why it matters Processed count is a required building block for understanding how Topological Sort stays correct and performant on large inputs.

Order result

What it is Final topological sequence.

Why it matters Order result is a required building block for understanding how Topological Sort stays correct and performant on large inputs.

DAG

What it is Directed acyclic graph.

Why it matters Directed acyclic graph. In Topological Sort, this definition helps you reason about correctness and complexity when inputs scale.

Kahn's algorithm

What it is BFS-like topological sort via indegree updates.

Why it matters BFS-like topological sort via indegree updates. In Topological Sort, this definition helps you reason about correctness and complexity when inputs scale.

Cycle detection

What it is Detect dependency loop preventing valid ordering.

Why it matters Detect dependency loop preventing valid ordering. In Topological Sort, this definition helps you reason about correctness and complexity when inputs scale.

Prerequisite graph

What it is Directed graph where edges represent dependency direction.

Why it matters Directed graph where edges represent dependency direction. In Topological Sort, this definition helps you reason about correctness and complexity when inputs scale.

Walkthrough

Putting It All Together

Every frame of the concept diagram, laid out top-to-bottom so you can scroll through the algorithm at your own pace.

Step 1/10

Init: in-degrees calculated. Seed queue with nodes whose in-degree is 0 → [A].

Step 2/10

Process A. Drop its outgoing edges → B, C hit in-degree 0, enqueue them.

Step 3/10

Process B. Drop its outgoing edges → D hit in-degree 0, enqueue them.

Step 4/10

Process C. Drop its outgoing edges → E, F hit in-degree 0, enqueue them.

Step 5/10

Process D. Drop its outgoing edges. Nothing new to enqueue.

Step 6/10

Process E. Drop its outgoing edges → G hit in-degree 0, enqueue them.

Step 7/10

Process F. Drop its outgoing edges → H hit in-degree 0, enqueue them.

Step 8/10

Process G. Drop its outgoing edges. Nothing new to enqueue.

Step 9/10

Process H. Drop its outgoing edges. Nothing new to enqueue.

Step 10/10

Queue empty. Topological order: A → B → C → D → E → F → G → H.

Tradeoffs

How It Compares

When this technique wins, when it loses, and what to reach for instead.

vs. DFS traversal

Choose this when Choose topological sort when dependency order output is required.

Tradeoff Plain DFS does not guarantee dependency-valid order.

vs. Union-Find

Choose this when Choose topo sort for directed dependency constraints.

Tradeoff Union-Find targets undirected connectivity sets.

vs. Manual ordering

Choose this when Choose algorithmic order for large dynamic dependency graphs.

Tradeoff Manual ordering fails at scale and is error-prone.

In Production

Real-World Stories

Where this shows up at real companies and what the on-call engineer learned the hard way.

Bazel and modern build systems

Build graphs are DAGs; topological ordering ensures dependencies build before targets.

Takeaway Topological sort is a practical CI/CD primitive.

Package managers (npm/pnpm ecosystem)

Dependency installation and resolution rely on DAG ordering and cycle checks.

Takeaway Correct dependency order avoids broken installations.

Airflow/Orchestration platforms

Workflow DAG schedulers execute tasks only when upstream dependencies complete.

Takeaway Topological constraints model production workflow orchestration.

Code

Implementation

A clean reference implementation in TypeScript, Python, and Go. Switch languages with the toggle.

Push all zero-indegree nodes, pop/process, decrement neighbors indegree.

Complexity: Time O(V+E), Space O(V+E)

Kahn's algorithm

Language

function topologicalOrder(nodeCount: number, edges: Array<[number, number]>): number[] {
  const adjacencyByNode: number[][] = Array.from({ length: nodeCount }, () => [])
  const indegreeByNode = new Array<number>(nodeCount).fill(0)
  for (const [fromNode, toNode] of edges) {
    adjacencyByNode[fromNode].push(toNode)
    indegreeByNode[toNode] += 1
  }

  const queue: number[] = []
  for (let nodeId = 0; nodeId < nodeCount; nodeId += 1) if (indegreeByNode[nodeId] === 0) queue.push(nodeId)

  const order: number[] = []
  while (queue.length > 0) {
    const node = queue.shift()!
    order.push(node)
    for (const neighbor of adjacencyByNode[node]) {
      indegreeByNode[neighbor] -= 1
      if (indegreeByNode[neighbor] === 0) queue.push(neighbor)
    }
  }

  return order.length === nodeCount ? order : []
}

Watch Out

Common Problems and Failure Modes

The bugs and edge cases that bite engineers most often. Skim before you ship.

Not handling disconnected DAG components.
Forgetting cycle detection check (processed count).
Wrong edge direction when building graph.
Mutable indegree reuse across multiple runs.
Assuming unique order; many DAGs allow multiple valid orders.

Pro Tips

Tips and Tricks

Small habits that pay off every time you reach for this pattern.

Topological sort applies only to DAGs; cycle detection is part of the solution.
Edge direction should always represent dependency flow consistently.
Kahn's algorithm is often easier to reason about for interview constraints.
Multiple valid orders may exist; tests should not assume a single sequence unless required.

Pattern Recognition

When to Use

Concrete signals that tell you this is the right pattern both at work and on LeetCode.

Real-system usage signals

Dependency resolution for build, package, and task pipelines.
Detects impossible dependency cycles.
Produces deterministic execution order when DAG constraints exist.

LeetCode-specific tips (pattern-identification signals)

Identification signal: dependency ordering where prerequisites must come before dependents.
Identification signal: graph is directed and cycles invalidate a feasible ordering.
Course scheduling and build pipeline ordering map directly to topological sort.
For Topological Sort questions, start by naming the core invariant before writing code.
Use the constraint section to set time/space target first, then pick the data structure/algorithm.
Solve one tiny example by hand and map each transition to your variables before implementing.
Run adversarial cases: empty input, duplicates, max-size input, and sorted/reverse patterns when relevant.
During interviews, explain why your approach is the right pattern for this prompt, not just why the code works.

Practice

LeetCode Progression

A curated easy-to-hard problem ladder. Each one reinforces a specific aspect of the pattern.

#	Problem	Difficulty	Typical Complexity
1	Course Schedule	Medium	`O(V+E)`
2	Course Schedule II	Medium	`O(V+E)`
3	Parallel Courses	Medium	`O(V+E)`
4	Sequence Reconstruction	Medium	`O(V+E)`
5	Minimum Height Trees	Medium	`O(V+E)`
6	Loud and Rich	Medium	`O(V+E)`
7	Alien Dictionary	Hard	`O(V+E)`
8	Sort Items by Groups Respecting Dependencies	Hard	`O(V+E)`
9	Build a Matrix With Conditions	Hard	`O(V+E)`
10	Maximum Employees to Be Invited to a Meeting	Hard	`O(V)`