# Topological Sort: Kahn’s Algorithm and DFS Approach

Source: https://www.techinterview.org/post/3233460122/topological-sort-kahns-algorithm-and-dfs-approach/
Updated: 2026-04-16 · techinterview.org

Topological sort is the graph algorithm you need for scheduling problems: course prerequisites, build systems, task dependencies, and package managers. It only works on Directed Acyclic Graphs (DAGs) and there are two main approaches — each with different strengths.

## What Is Topological Sort?

Given a DAG, produce a linear ordering of vertices such that for every directed edge (u → v), vertex u comes before v in the ordering.

Example: if course A is a prerequisite for course B, A must come before B in the schedule.

## Approach 1: DFS Post-Order (Depth-First)


```
def topological_sort_dfs(graph: dict) -> list | None:
    """
    DFS-based topological sort.
    A node goes into the result AFTER all its dependencies are processed (post-order).
    Reverse the result to get the topological order.
    Returns None if graph has a cycle (no valid topological order exists).
    Time: O(V + E), Space: O(V)
    """
    visited = set()
    in_stack = set()  # Detect cycles (nodes currently in DFS path)
    result = []

    def dfs(node):
        if node in in_stack:
            return False  # Back edge = cycle
        if node in visited:
            return True   # Already processed

        in_stack.add(node)
        for neighbor in graph.get(node, []):
            if not dfs(neighbor):
                return False
        in_stack.remove(node)
        visited.add(node)
        result.append(node)  # Post-order: append after processing all neighbors
        return True

    for node in graph:
        if node not in visited:
            if not dfs(node):
                return None  # Cycle detected

    return result[::-1]  # Reverse post-order = topological order

# Example: Course prerequisites
graph = {
    'algorithms': ['data structures'],
    'data structures': ['programming basics'],
    'programming basics': [],
    'operating systems': ['programming basics'],
    'compilers': ['algorithms', 'data structures']
}
order = topological_sort_dfs(graph)
print(order)  # ['programming basics', 'data structures', 'algorithms', 'operating systems', 'compilers']
# (exact order among siblings may vary)
```


## Approach 2: Kahn's Algorithm (BFS / Indegree)


```
from collections import deque

def topological_sort_kahn(n: int, edges: list[tuple]) -> list | None:
    """
    Kahn's algorithm: process nodes with indegree=0 first (no dependencies).
    Returns None if a cycle exists (not all nodes get processed).
    Time: O(V + E), Space: O(V)
    """
    graph = [[] for _ in range(n)]
    indegree = [0] * n

    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    # Start with all nodes that have no prerequisites
    queue = deque([i for i in range(n) if indegree[i] == 0])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)

        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    # If result doesn't contain all nodes, there's a cycle
    if len(result) != n:
        return None

    return result

# LeetCode 210: Course Schedule II
def find_order(num_courses: int, prerequisites: list[list[int]]) -> list[int]:
    """Return a valid course ordering, or [] if impossible (cycle)."""
    edges = [(pre, course) for course, pre in prerequisites]
    result = topological_sort_kahn(num_courses, edges)
    return result if result is not None else []
```


## Which Approach to Use?

| Criterion | DFS (Post-order) | Kahn's (BFS) |
| --- | --- | --- |
| Cycle detection | Natural (in_stack set) | Natural (check len(result) == n) |
| Parallelism hint | No | Yes — queue contains all nodes safe to process in parallel |
| Lexicographic order | Hard | Easy — use min-heap instead of deque |
| Multiple valid orderings | Returns one | Both return one; min-heap gives lexicographic smallest |
| Recursion limit concern | Yes (use iterative DFS) | No (always iterative) |

## Minimum Time to Complete All Tasks (Parallel Execution)

Kahn's algorithm reveals which tasks can be done in parallel — the nodes in the queue at any moment are all executable simultaneously:


```
def min_time_parallel(n: int, edges: list[tuple], time: list[int]) -> int:
    """
    Find minimum time to complete all tasks when tasks can run in parallel.
    time[i] = duration of task i.
    Constraint: task v cannot start until task u completes (for each edge u->v).
    """
    graph = [[] for _ in range(n)]
    indegree = [0] * n

    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    # finish_time[i] = earliest time task i can complete
    finish_time = list(time)
    queue = deque([i for i in range(n) if indegree[i] == 0])

    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            # Neighbor can't start until node finishes
            finish_time[neighbor] = max(
                finish_time[neighbor],
                finish_time[node] + time[neighbor]
            )
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    return max(finish_time)
```


## Practice Problems

- LeetCode 207: Course Schedule (just detect cycle)

- LeetCode 210: Course Schedule II (return ordering)

- LeetCode 310: Minimum Height Trees (find topological roots)

- LeetCode 1136: Parallel Courses (minimum semesters)

- LeetCode 329: Longest Increasing Path in a Matrix (topo sort + DP)

## Related Graph Topics
- [Detect a Cycle in a Graph](https://www.techinterview.org/post/3233460120/detect-a-cycle-in-a-graph-directed-and-undirected/) — topological sort requires a DAG; use cycle detection (DFS three-color or Kahn's node count check) to validate before sorting
- [BFS vs DFS: When to Use Each](https://www.techinterview.org/post/3233460119/bfs-vs-dfs-when-to-use-each-with-examples/) — Kahn's algorithm is BFS; DFS post-order is the other approach; same graph traversal primitives, different application