Algorithm • extra-hard

Topological Sort Complete Guide

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)`

Video Explainer

Prefer video learning? This explainer gives a quick visual walkthrough of the core idea before you dive into the detailed sections below.

Topological Sort Visualized and Explained

Channel: Carl the Person

Full video link:

https://www.youtube.com/watch?v=7J3GadLzydI

Topological Sort Visualizer

Kahn’s algorithm repeatedly processes nodes with indegree zero to respect dependencies.

Topological Sort VisualizerStep 1 / 3

Compute indegree and seed queue with zero-indegree nodes.

Edges

A->C, B->C, C->D, C->E

Indegree

A:0, B:0, C:2, D:1, E:1

Queue

[A, B]

Order

[]

Core Concepts

Learn the core building blocks and terminology in one place before comparisons, so the mechanics are clear and duplicates are removed.

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.

Putting It All Together

This walkthrough connects the core concepts of Topological Sort into one end-to-end execution flow.

Step 1

Indegree

Count of incoming edges per node.

Before

Dependencies: A->C, B->C, C->D
Compute indegree for each node

→

After

Order starts with independent tasks
Cycle-free progress can begin

Transition

Push indegree-0 nodes into queue

→Initial queue=[A,B]

Why this step matters: Indegree is a required building block for understanding how Topological Sort stays correct and performant on large inputs.

Step 2

Zero-indegree queue

Nodes currently ready to execute.

Before

Queue=

Order=[]

→

After

Order=

Queue updates after indegree changes

Transition

Pop A then B

→Append each to output order

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

Step 3

Adjacency list

Outgoing dependency edges.

Before

Node C indegree becomes 0
Queue now includes C

→

After

Order=

ABC

D becomes eligible next

Transition

Pop C

→Decrease indegree of D

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

Step 4

Processed count

Used to detect cycles if < total nodes.

Before

Process remaining queue
Expected nodes count = graph size

→

After

Topological order=

ABCD

If count mismatch -> cycle detected

Transition

Append D

→Check output length

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

How It Compares

vs DFS traversal

When to choose this: Choose topological sort when dependency order output is required.

Tradeoff: Plain DFS does not guarantee dependency-valid order.

vs Union-Find

When to choose this: Choose topo sort for directed dependency constraints.

Tradeoff: Union-Find targets undirected connectivity sets.

vs Manual ordering

When to choose this: Choose algorithmic order for large dynamic dependency graphs.

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

Real-World Stories and Company Examples

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.

Implementation Guide

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

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

Language

Kahn's algorithm

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 : []
}

Common Problems and Failure Modes

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.

Tips and Tricks

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.

When to Use

Use these signals to decide if this data structure/algorithm is the right fit before implementation.

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 (including 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.

LeetCode Progression (Easy to Hard)

Back to DSA Guide Catalog

#	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)`