Skip to content

Topological Sort

Problem

Given a DAG represented as an adjacency list, return a valid topological ordering of its vertices. If the graph has a cycle, return an empty list.

Approach

  1. Kahn's algorithm (BFS): Track in-degrees; repeatedly dequeue nodes with in-degree 0 and decrement neighbors' in-degrees.
  2. DFS-based: Post-order DFS; reverse the finish order.

Algorithm Flow

flowchart TD
    A["Build adjacency list<br/>Compute in-degree for each node"] --> B["Enqueue all nodes<br/>with in-degree 0"]
    B --> C{"Queue empty?"}
    C -- Yes --> D{"len(order) == V?"}
    D -- Yes --> E["Return order<br/>(valid topological sort)"]
    D -- No --> F["Return [] — cycle detected"]
    C -- No --> G["Dequeue node u<br/>Append u to order"]
    G --> H["For each neighbor v of u:<br/>in-degree[v] -= 1"]
    H --> I{"in-degree[v] == 0?"}
    I -- Yes --> J["Enqueue v"]
    I -- No --> K["Continue"]
    J --> C
    K --> C

    style A fill:#7c3aed,color:#fff
    style E fill:#059669,color:#fff
    style F fill:#dc2626,color:#fff

When to Use

Dependency resolution — "build order", "task scheduling with prereqs", "compile order". Any DAG where you need a valid linear ordering. Also: package managers, makefile targets, course planning.

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

Implementation

topological_sort

Topological ordering of a directed acyclic graph (DAG).

Problem

Given a DAG represented as an adjacency list, return a valid topological ordering of its vertices. If the graph has a cycle, return an empty list.

Approach
  1. Kahn's algorithm (BFS): Track in-degrees; repeatedly dequeue nodes with in-degree 0 and decrement neighbors' in-degrees.
  2. DFS-based: Post-order DFS; reverse the finish order.
When to use

Dependency resolution — "build order", "task scheduling with prereqs", "compile order". Any DAG where you need a valid linear ordering. Also: package managers, makefile targets, course planning.

Complexity

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

topological_sort_dfs 

topological_sort_dfs(
    num_nodes: int, edges: list[tuple[int, int]]
) -> list[int]

Return a topological ordering using DFS post-order reversal.

Returns [] if a cycle exists.

topological_sort_dfs(4, [(0, 1), (0, 2), (1, 3), (2, 3)]) [0, 2, 1, 3]

Source code in src/algo/graphs/topological_sort.py 
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
def topological_sort_dfs(
    num_nodes: int,
    edges: list[tuple[int, int]],
) -> list[int]:
    """Return a topological ordering using DFS post-order reversal.

    Returns [] if a cycle exists.

    >>> topological_sort_dfs(4, [(0, 1), (0, 2), (1, 3), (2, 3)])
    [0, 2, 1, 3]
    """
    adj: list[list[int]] = [[] for _ in range(num_nodes)]
    for u, v in edges:
        adj[u].append(v)

    # 0 = unvisited, 1 = in-progress, 2 = done
    state = [0] * num_nodes
    order: list[int] = []
    has_cycle = False

    def dfs(node: int) -> None:
        nonlocal has_cycle
        if has_cycle:
            return
        state[node] = 1
        for neighbor in adj[node]:
            if state[neighbor] == 1:
                has_cycle = True
                return
            if state[neighbor] == 0:
                dfs(neighbor)
        state[node] = 2
        order.append(node)

    for i in range(num_nodes):
        if state[i] == 0:
            dfs(i)

    if has_cycle:
        return []
    order.reverse()
    return order

topological_sort_kahn 

topological_sort_kahn(
    num_nodes: int, edges: list[tuple[int, int]]
) -> list[int]

Return a topological ordering using Kahn's algorithm.

edges is a list of (u, v) meaning u -> v. Returns [] if a cycle exists.

topological_sort_kahn(4, [(0, 1), (0, 2), (1, 3), (2, 3)]) [0, 1, 2, 3]

Source code in src/algo/graphs/topological_sort.py 
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
def topological_sort_kahn(
    num_nodes: int,
    edges: list[tuple[int, int]],
) -> list[int]:
    """Return a topological ordering using Kahn's algorithm.

    *edges* is a list of (u, v) meaning u -> v.
    Returns [] if a cycle exists.

    >>> topological_sort_kahn(4, [(0, 1), (0, 2), (1, 3), (2, 3)])
    [0, 1, 2, 3]
    """
    adj: list[list[int]] = [[] for _ in range(num_nodes)]
    in_degree = [0] * num_nodes

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

    queue: deque[int] = deque(i for i in range(num_nodes) if in_degree[i] == 0)
    order: list[int] = []

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

    if len(order) != num_nodes:
        return []
    return order
tests/graphs/test_topological_sort.py
"""Tests for topological sort algorithms."""

from algo.graphs.topological_sort import topological_sort_dfs, topological_sort_kahn


def _is_valid_topo_order(
    num_nodes: int,
    edges: list[tuple[int, int]],
    order: list[int],
) -> bool:
    """Check that *order* is a valid topological ordering."""
    if len(order) != num_nodes:
        return False
    pos = {node: i for i, node in enumerate(order)}
    return all(pos[u] < pos[v] for u, v in edges)


class TestTopologicalSortKahn:
    def test_linear_chain(self) -> None:
        order = topological_sort_kahn(3, [(0, 1), (1, 2)])
        assert order == [0, 1, 2]

    def test_diamond(self) -> None:
        edges = [(0, 1), (0, 2), (1, 3), (2, 3)]
        order = topological_sort_kahn(4, edges)
        assert _is_valid_topo_order(4, edges, order)

    def test_no_edges(self) -> None:
        order = topological_sort_kahn(3, [])
        assert sorted(order) == [0, 1, 2]

    def test_cycle_returns_empty(self) -> None:
        assert topological_sort_kahn(3, [(0, 1), (1, 2), (2, 0)]) == []

    def test_single_node(self) -> None:
        assert topological_sort_kahn(1, []) == [0]


class TestTopologicalSortDFS:
    def test_linear_chain(self) -> None:
        order = topological_sort_dfs(3, [(0, 1), (1, 2)])
        assert _is_valid_topo_order(3, [(0, 1), (1, 2)], order)

    def test_diamond(self) -> None:
        edges = [(0, 1), (0, 2), (1, 3), (2, 3)]
        order = topological_sort_dfs(4, edges)
        assert _is_valid_topo_order(4, edges, order)

    def test_no_edges(self) -> None:
        order = topological_sort_dfs(3, [])
        assert sorted(order) == [0, 1, 2]

    def test_cycle_returns_empty(self) -> None:
        assert topological_sort_dfs(3, [(0, 1), (1, 2), (2, 0)]) == []

    def test_single_node(self) -> None:
        assert topological_sort_dfs(1, []) == [0]

Implement it yourself

Run: just challenge graphs topological_sort

Then implement the functions to make all tests pass. Use just study graphs for watch mode.

Reveal Solution

topological_sort

Topological ordering of a directed acyclic graph (DAG).

Problem

Given a DAG represented as an adjacency list, return a valid topological ordering of its vertices. If the graph has a cycle, return an empty list.

Approach
  1. Kahn's algorithm (BFS): Track in-degrees; repeatedly dequeue nodes with in-degree 0 and decrement neighbors' in-degrees.
  2. DFS-based: Post-order DFS; reverse the finish order.
When to use

Dependency resolution — "build order", "task scheduling with prereqs", "compile order". Any DAG where you need a valid linear ordering. Also: package managers, makefile targets, course planning.

Complexity

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

topological_sort_dfs 

topological_sort_dfs(
    num_nodes: int, edges: list[tuple[int, int]]
) -> list[int]

Return a topological ordering using DFS post-order reversal.

Returns [] if a cycle exists.

topological_sort_dfs(4, [(0, 1), (0, 2), (1, 3), (2, 3)]) [0, 2, 1, 3]

Source code in src/algo/graphs/topological_sort.py 
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
def topological_sort_dfs(
    num_nodes: int,
    edges: list[tuple[int, int]],
) -> list[int]:
    """Return a topological ordering using DFS post-order reversal.

    Returns [] if a cycle exists.

    >>> topological_sort_dfs(4, [(0, 1), (0, 2), (1, 3), (2, 3)])
    [0, 2, 1, 3]
    """
    adj: list[list[int]] = [[] for _ in range(num_nodes)]
    for u, v in edges:
        adj[u].append(v)

    # 0 = unvisited, 1 = in-progress, 2 = done
    state = [0] * num_nodes
    order: list[int] = []
    has_cycle = False

    def dfs(node: int) -> None:
        nonlocal has_cycle
        if has_cycle:
            return
        state[node] = 1
        for neighbor in adj[node]:
            if state[neighbor] == 1:
                has_cycle = True
                return
            if state[neighbor] == 0:
                dfs(neighbor)
        state[node] = 2
        order.append(node)

    for i in range(num_nodes):
        if state[i] == 0:
            dfs(i)

    if has_cycle:
        return []
    order.reverse()
    return order

topological_sort_kahn 

topological_sort_kahn(
    num_nodes: int, edges: list[tuple[int, int]]
) -> list[int]

Return a topological ordering using Kahn's algorithm.

edges is a list of (u, v) meaning u -> v. Returns [] if a cycle exists.

topological_sort_kahn(4, [(0, 1), (0, 2), (1, 3), (2, 3)]) [0, 1, 2, 3]

Source code in src/algo/graphs/topological_sort.py 
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
def topological_sort_kahn(
    num_nodes: int,
    edges: list[tuple[int, int]],
) -> list[int]:
    """Return a topological ordering using Kahn's algorithm.

    *edges* is a list of (u, v) meaning u -> v.
    Returns [] if a cycle exists.

    >>> topological_sort_kahn(4, [(0, 1), (0, 2), (1, 3), (2, 3)])
    [0, 1, 2, 3]
    """
    adj: list[list[int]] = [[] for _ in range(num_nodes)]
    in_degree = [0] * num_nodes

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

    queue: deque[int] = deque(i for i in range(num_nodes) if in_degree[i] == 0)
    order: list[int] = []

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

    if len(order) != num_nodes:
        return []
    return order