---
# === IDENTITY ===
id: software/patterns/topological-sort/2026
canonical_question: "How do I implement topological sort and when to use it?"
aliases:
  - "topological ordering algorithm"
  - "DAG linearization"
  - "Kahn's algorithm BFS topological sort"
  - "DFS topological sort implementation"
  - "dependency graph ordering"
  - "task scheduling topological order"
entity_type: software_reference
domain: software > patterns > topological_sort
region: global
jurisdiction: global
temporal_scope: 1962-2026

# === VERIFICATION ===
last_verified: 2026-02-24
confidence: 0.95
version: 1.0
first_published: 2026-02-24

# === TEMPORAL VALIDITY ===
temporal_validity:
  status: stable
  last_breaking_change: null
  next_review: 2026-08-23
  change_sensitivity: low

# === CONSTRAINTS ===
constraints:
  - "Input graph MUST be a Directed Acyclic Graph (DAG); topological sort is undefined for graphs with cycles"
  - "A DAG may have multiple valid topological orderings; algorithms return one valid ordering unless explicitly enumerating all"
  - "Always run cycle detection before or during topological sort; silently ignoring cycles produces incorrect orderings"
  - "All-orderings enumeration is O(n! * V) worst case; never enumerate on graphs with more than ~20 vertices without pruning"

# === SKIP CONDITIONS ===
skip_this_unit_if:
  - condition: "Graph is undirected or contains cycles"
    use_instead: "Use cycle detection (DFS back-edge) first, or use strongly connected components (Tarjan/Kosaraju)"
  - condition: "Need shortest/longest path in weighted DAG"
    use_instead: "Use DAG relaxation with topological order (single-source shortest path in DAG)"
  - condition: "Need to find connected components, not ordering"
    use_instead: "software/patterns/union-find-disjoint-set"

# === AGENT HINTS ===
inputs_needed:
  - key: algorithm
    question: "Do you prefer BFS-based (Kahn's) or DFS-based topological sort?"
    type: choice
    options: ["Kahn's (BFS, iterative)", "DFS (recursive/stack)", "No preference"]
  - key: need_all_orderings
    question: "Do you need all valid topological orderings or just one?"
    type: choice
    options: ["Just one ordering", "All orderings (small graph only)"]
  - key: cycle_detection_needed
    question: "Does your input graph need cycle detection?"
    type: choice
    options: ["Yes, detect and report cycles", "No, input is guaranteed acyclic"]

# === DISTRIBUTION ===
canonical_source: "https://knowledgelib.io/software/patterns/topological-sort/2026"
suggested_citation: "Source: knowledgelib.io -- AI Knowledge Library (verified 2026-02-24)"

# === RELATED UNITS ===
related_kos:
  depends_on: []
  related_to:
    - id: "software/patterns/graph-algorithms/2026"
      label: "Graph Algorithms Overview"
    - id: "software/patterns/union-find-disjoint-set/2026"
      label: "Union-Find / Disjoint Set"
    - id: "software/patterns/dynamic-programming/2026"
      label: "Dynamic Programming Patterns"
  solves: []
  alternative_to: []
  often_confused_with:
    - id: "software/patterns/graph-bfs-dfs/2026"
      label: "BFS/DFS Graph Traversal (ordering vs traversal)"

# === SOURCES (7 authoritative sources) ===
sources:
  - id: src1
    title: "Topological sorting"
    author: Wikipedia
    url: https://en.wikipedia.org/wiki/Topological_sorting
    type: community_resource
    published: 2026-01-15
    reliability: high
  - id: src2
    title: "Topological Sorting - GeeksforGeeks"
    author: GeeksforGeeks
    url: https://www.geeksforgeeks.org/dsa/topological-sorting/
    type: community_resource
    published: 2025-12-10
    reliability: moderate_high
  - id: src3
    title: "Topological Sorting using BFS - Kahn's Algorithm"
    author: GeeksforGeeks
    url: https://www.geeksforgeeks.org/dsa/topological-sorting-indegree-based-solution/
    type: community_resource
    published: 2025-11-20
    reliability: moderate_high
  - id: src4
    title: "Topological Sorting - Algorithms for Competitive Programming"
    author: CP-Algorithms
    url: https://cp-algorithms.com/graph/topological-sort.html
    type: technical_blog
    published: 2025-08-15
    reliability: high
  - id: src5
    title: "Topological Sort - USACO Guide"
    author: USACO Guide
    url: https://usaco.guide/gold/toposort
    type: community_resource
    published: 2025-10-01
    reliability: high
  - id: src6
    title: "Detect cycle in Directed Graph using Topological Sort"
    author: GeeksforGeeks
    url: https://www.geeksforgeeks.org/dsa/detect-cycle-in-directed-graph-using-topological-sort/
    type: community_resource
    published: 2025-09-05
    reliability: moderate_high
  - id: src7
    title: "CS 106X Lecture 25: Topological Sort"
    author: Stanford University
    url: https://web.stanford.edu/class/archive/cs/cs106x/cs106x.1192/lectures/Lecture25/Lecture25.pdf
    type: academic_paper
    published: 2019-03-01
    reliability: authoritative
---

# Topological Sort: Linear Ordering of DAG Vertices

## TL;DR

- **Bottom line**: Topological sort produces a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every edge (u, v), vertex u appears before v -- essential for dependency resolution, build systems, and task scheduling.
- **Key tool/command**: Kahn's algorithm (BFS with in-degree tracking) or DFS with post-order reversal.
- **Watch out for**: Applying topological sort to a graph with cycles -- always detect cycles first or use Kahn's algorithm which detects them automatically (sorted count != vertex count).
- **Works with**: Any directed acyclic graph; language-agnostic algorithm (O(V+E) time, O(V) space).

## Constraints
<!-- Agents: read this section before recommending any action from this unit.
     These are hard constraints that must not be violated. -->

- Input graph MUST be a Directed Acyclic Graph (DAG); topological sort is undefined for graphs with cycles
- A DAG may have multiple valid topological orderings; algorithms return one valid ordering unless explicitly enumerating all
- Always run cycle detection before or during topological sort; silently ignoring cycles produces incorrect orderings
- All-orderings enumeration is O(n! * V) worst case; never enumerate on graphs with more than ~20 vertices without pruning

## Quick Reference

| Algorithm | Time | Space | Cycle Detection | All Orderings | Approach |
|---|---|---|---|---|---|
| Kahn's (BFS) | O(V+E) | O(V) | Yes (count != V) | No (one ordering) | In-degree queue; remove zero-indegree nodes iteratively |
| DFS-based | O(V+E) | O(V) | Yes (back-edge / color) | No (one ordering) | Post-order traversal, reverse the result |
| DFS + backtracking | O(V! * V) | O(V) | Yes | Yes (all orderings) | Enumerate all valid orderings via backtracking |
| Parallel Kahn's | O(V+E) work, O(D) depth | O(V) | Yes | No | Process all zero-indegree nodes in parallel per level |
| Coffman-Graham | O(V+E) | O(V) | Yes | No | Kahn's variant with lexicographic tie-breaking for scheduling |

**Key relationships**:
- V = number of vertices, E = number of edges, D = longest path in DAG (critical path)
- Kahn's and DFS have identical asymptotic complexity; Kahn's is preferred when you also need cycle detection or level-based parallelism
- DFS-based is often simpler to implement in recursive languages

## Decision Tree

```
START
├── Is the graph guaranteed to be a DAG (no cycles)?
│   ├── NO → Use Kahn's algorithm (detects cycles when sorted_count != V)
│   └── YES ↓
├── Do you need to identify parallelizable groups (levels)?
│   ├── YES → Use Kahn's algorithm with level tracking (nodes dequeued together = one level)
│   └── NO ↓
├── Do you need ALL valid topological orderings?
│   ├── YES → Use DFS + backtracking (only for small graphs, V <= 20)
│   └── NO ↓
├── Is the implementation language naturally recursive?
│   ├── YES → Use DFS-based topological sort (simpler code)
│   └── NO → Use Kahn's algorithm (iterative, no recursion stack overflow risk)
└── DEFAULT → Kahn's algorithm (most versatile, built-in cycle detection)
```

## Step-by-Step Guide

### 1. Build the adjacency list and compute in-degrees (Kahn's Algorithm)

Create an adjacency list representation of the graph and count incoming edges for each vertex. [src3]

```python
from collections import deque, defaultdict

def build_graph(num_vertices, edges):
    """Build adjacency list and in-degree array from edge list."""
    adj = defaultdict(list)
    in_degree = [0] * num_vertices
    for u, v in edges:
        adj[u].append(v)
        in_degree[v] += 1
    return adj, in_degree
```

**Verify**: `in_degree` array sums to E (total edge count): `assert sum(in_degree) == len(edges)`

### 2. Initialize queue with zero-indegree vertices

All vertices with in-degree 0 have no dependencies and can appear first in the ordering. [src3]

```python
def init_queue(in_degree):
    """Collect all vertices with no incoming edges."""
    queue = deque()
    for v in range(len(in_degree)):
        if in_degree[v] == 0:
            queue.append(v)
    return queue
```

**Verify**: If queue is empty but graph has vertices, the graph has a cycle.

### 3. Process vertices in BFS order (Kahn's core loop)

Dequeue a vertex, add it to the result, and decrement in-degrees of all its neighbors. If a neighbor reaches in-degree 0, enqueue it. [src1]

```python
def kahn_topological_sort(num_vertices, edges):
    """Return topological ordering or raise ValueError if cycle detected."""
    adj, in_degree = build_graph(num_vertices, edges)
    queue = init_queue(in_degree)
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in adj[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(result) != num_vertices:
        raise ValueError(f"Cycle detected: only {len(result)}/{num_vertices} vertices sorted")
    return result
```

**Verify**: `len(result) == num_vertices` -- if not, cycle exists.

### 4. DFS-based alternative implementation

Visit each unvisited vertex, recurse into neighbors, and push the vertex onto a stack after all neighbors are processed. Reverse the stack for topological order. [src4]

```python
def dfs_topological_sort(num_vertices, edges):
    """DFS-based topological sort with 3-color cycle detection."""
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)

    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * num_vertices
    order = []

    def dfs(node):
        color[node] = GRAY
        for neighbor in adj[node]:
            if color[neighbor] == GRAY:
                raise ValueError(f"Cycle detected: back edge {node} -> {neighbor}")
            if color[neighbor] == WHITE:
                dfs(neighbor)
        color[node] = BLACK
        order.append(node)

    for v in range(num_vertices):
        if color[v] == WHITE:
            dfs(v)

    order.reverse()
    return order
```

**Verify**: No `ValueError` raised means no cycle; `len(order) == num_vertices`.

## Code Examples

### Python: Course Schedule (LeetCode 210 pattern)

```python
# Input:  numCourses=4, prerequisites=[[1,0],[2,0],[3,1],[3,2]]
# Output: [0, 1, 2, 3] or [0, 2, 1, 3] (any valid ordering)

from collections import deque, defaultdict

def find_course_order(num_courses, prerequisites):
    adj = defaultdict(list)
    in_degree = [0] * num_courses
    for course, prereq in prerequisites:
        adj[prereq].append(course)
        in_degree[course] += 1

    queue = deque(c for c in range(num_courses) if in_degree[c] == 0)
    order = []

    while queue:
        course = queue.popleft()
        order.append(course)
        for next_course in adj[course]:
            in_degree[next_course] -= 1
            if in_degree[next_course] == 0:
                queue.append(next_course)

    return order if len(order) == num_courses else []  # empty = cycle
```

### JavaScript: Build Order / Task Scheduling

> Full script: [javascript-build-order-task-scheduling.js](scripts/javascript-build-order-task-scheduling.js) (25 lines)

```javascript
// Input:  tasks = ["a","b","c","d"], deps = [["a","b"],["a","c"],["b","d"]]
// Output: ["a", "b", "c", "d"] or ["a", "c", "b", "d"]
// deps format: [prerequisite, dependent] -- prerequisite must come before dependent
function buildOrder(tasks, deps) {
  const adj = new Map();
# ... (see full script)
```

### Java: Dependency Resolution with Parallel Level Detection

> Full script: [java-dependency-resolution-with-parallel-level-det.java](scripts/java-dependency-resolution-with-parallel-level-det.java) (34 lines)

```java
// Input:  numNodes=6, edges={{5,2},{5,0},{4,0},{4,1},{2,3},{3,1}}
// Output: levels [[4,5],[0,2],[3],[1]] -- nodes at each level can run in parallel
import java.util.*;
public class ParallelTopSort {
    public static List<List<Integer>> topSortLevels(int n, int[][] edges) {
# ... (see full script)
```

## Anti-Patterns

### Wrong: Applying topological sort without cycle detection

```python
# BAD -- silently produces incorrect partial ordering on cyclic graphs
def naive_topo_sort(n, edges):
    adj = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:
        adj[u].append(v)
        in_degree[v] += 1
    queue = deque(v for v in range(n) if in_degree[v] == 0)
    result = []
    while queue:
        node = queue.popleft()
        result.append(node)
        for nb in adj[node]:
            in_degree[nb] -= 1
            if in_degree[nb] == 0:
                queue.append(nb)
    return result  # May return partial list without warning!
```

### Correct: Always verify sorted count equals vertex count

```python
# GOOD -- detects cycles by checking result length
def safe_topo_sort(n, edges):
    adj = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:
        adj[u].append(v)
        in_degree[v] += 1
    queue = deque(v for v in range(n) if in_degree[v] == 0)
    result = []
    while queue:
        node = queue.popleft()
        result.append(node)
        for nb in adj[node]:
            in_degree[nb] -= 1
            if in_degree[nb] == 0:
                queue.append(nb)
    if len(result) != n:
        raise ValueError("Graph contains a cycle")
    return result
```

### Wrong: Incorrect in-degree computation (counting edges twice)

```python
# BAD -- counting both directions inflates in-degrees
def broken_indegree(n, edges):
    in_degree = [0] * n
    for u, v in edges:
        in_degree[v] += 1
        in_degree[u] += 1  # Wrong! u is source, not destination
    return in_degree
```

### Correct: Only increment in-degree for the destination vertex

```python
# GOOD -- only the destination vertex gains an incoming edge
def correct_indegree(n, edges):
    in_degree = [0] * n
    for u, v in edges:
        in_degree[v] += 1  # Edge u -> v means v has one more incoming edge
    return in_degree
```

### Wrong: DFS without 3-color marking (misses cycles)

```python
# BAD -- simple visited set cannot distinguish back-edges from cross-edges
def broken_dfs_topo(n, adj):
    visited = set()
    order = []
    def dfs(node):
        visited.add(node)
        for nb in adj[node]:
            if nb not in visited:
                dfs(nb)
        order.append(node)
    for v in range(n):
        if v not in visited:
            dfs(v)
    order.reverse()
    return order  # No cycle detection at all!
```

### Correct: Use WHITE/GRAY/BLACK coloring to detect back-edges

```python
# GOOD -- GRAY node in DFS stack means back-edge (cycle)
def correct_dfs_topo(n, adj):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
    order = []
    def dfs(node):
        color[node] = GRAY
        for nb in adj[node]:
            if color[nb] == GRAY:
                raise ValueError("Cycle: back edge found")
            if color[nb] == WHITE:
                dfs(nb)
        color[node] = BLACK
        order.append(node)
    for v in range(n):
        if color[v] == WHITE:
            dfs(v)
    order.reverse()
    return order
```

## Common Pitfalls

- **Not handling disconnected components**: Both Kahn's and DFS must iterate over ALL vertices, not just start from vertex 0. A disconnected DAG still has a valid topological ordering. Fix: iterate `for v in range(V)` in DFS; Kahn's handles this naturally by seeding queue with all zero-indegree vertices. [src2]
- **Confusing edge direction in prerequisites**: In course schedule problems, `[course, prereq]` means prereq -> course (prereq must come first). Reversing the direction produces wrong orderings. Fix: carefully read the edge semantics -- `adj[prereq].append(course)` and `in_degree[course] += 1`. [src5]
- **Stack overflow on large graphs with DFS**: Recursive DFS hits Python's default 1000-recursion limit or similar stack limits. Fix: use iterative DFS with an explicit stack, or use Kahn's algorithm (always iterative). [src4]
- **Assuming unique topological ordering**: A DAG may have many valid orderings. If you need deterministic output (e.g., for testing), sort the initial zero-indegree vertices or use a min-heap instead of a queue. Fix: use `heapq` or `PriorityQueue` to get lexicographically smallest ordering. [src1]
- **Mutating the input graph**: Some implementations modify the adjacency list or in-degree array in place. If the graph is needed later, this causes bugs. Fix: work on copies of the in-degree array; never remove edges from the original adjacency list. [src3]
- **Forgetting that topological sort only applies to directed graphs**: Applying it to undirected graphs is meaningless -- every undirected edge creates a "cycle" between its two endpoints. Fix: verify graph is directed before attempting topological sort. [src1]

## When to Use / When Not to Use

| Use When | Don't Use When | Use Instead |
|---|---|---|
| Resolving build/compilation dependencies (Makefile, Gradle, Bazel) | Graph has cycles | Strongly connected components (Tarjan/Kosaraju) to collapse cycles first |
| Course prerequisite scheduling | Need shortest path in weighted graph | Dijkstra or Bellman-Ford (or DAG relaxation if acyclic) |
| Task scheduling with dependency constraints | Need to find connected components | Union-Find / BFS/DFS connected components |
| Package manager install ordering (npm, pip, apt) | Graph is undirected | BFS/DFS traversal (topological sort is undefined for undirected graphs) |
| Spreadsheet formula evaluation order | Need maximum flow or matching | Ford-Fulkerson or Hopcroft-Karp |
| Determining parallelizable task levels | Need all-pairs shortest paths | Floyd-Warshall |
| Data pipeline / ETL stage ordering | Ordering doesn't need to respect edge direction | Simple BFS/DFS traversal |

## Important Caveats

- Topological sort is a fundamental algorithm dating to Kahn (1962); the algorithm itself is evergreen and will not change, but language-specific implementations may vary in edge cases (e.g., Python recursion limits, Java stream vs. imperative style)
- For extremely large graphs (millions of vertices), consider parallel variants of Kahn's algorithm that process entire levels concurrently; the sequential algorithm is still O(V+E) but wall-clock time can be reduced
- The DFS-based approach and Kahn's algorithm produce different (but both valid) orderings for the same graph; do not assume they will match
- In competitive programming, topological sort is a prerequisite for DAG dynamic programming (e.g., longest path in DAG, number of paths)

## Related Units

- [Graph Algorithms Overview](/software/patterns/graph-algorithms/2026)
- [Union-Find / Disjoint Set](/software/patterns/union-find-disjoint-set/2026)
- [Dynamic Programming Patterns](/software/patterns/dynamic-programming/2026)