Topological Sort: Algorithms and Applications

A topological sort of a directed acyclic graph (DAG) is a linear ordering of its vertices such that for every directed edge u -> v, vertex u comes before v in the ordering. It is only possible when the graph has no cycles.

Topological sort appears everywhere: build systems (Make, Bazel), package managers (pip, npm), course prerequisites, task scheduling, and compiler dependency resolution.

Why it matters

Consider a university course catalog. You cannot take “Machine Learning” before “Linear Algebra” and “Probability.” A topological sort of the prerequisite graph gives you a valid order to take all courses.

If you add a circular dependency (ML requires Stats, Stats requires ML), no valid ordering exists. Detecting this cycle is equally important.

Kahn’s algorithm (BFS-based)

Kahn’s algorithm uses the concept of in-degree (number of incoming edges). The idea: nodes with in-degree 0 have no dependencies and can be processed first.

from collections import deque, defaultdict

def topological_sort_kahn(num_nodes, edges):
    """
    Kahn's Algorithm (BFS-based topological sort).
    Time: O(V + E)
    Space: O(V + E)

    Returns topological order or empty list if cycle exists.
    """
    graph = defaultdict(list)
    in_degree = [0] * num_nodes

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

    # Start with all nodes that have no prerequisites
    queue = deque()
    for node in range(num_nodes):
        if in_degree[node] == 0:
            queue.append(node)

    order = []
    while queue:
        node = queue.popleft()
        order.append(node)

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

    # If we processed all nodes, no cycle exists
    if len(order) == num_nodes:
        return order
    else:
        return []  # Cycle detected


# Example: 6 courses with prerequisites
edges = [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)]
result = topological_sort_kahn(6, edges)
print(f"Topological order: {result}")
# One valid output: [4, 5, 2, 0, 3, 1]

How it works step by step

1. Compute in-degree for every node.
2. Add all nodes with in-degree 0 to a queue.
3. Dequeue a node, add it to the result.
4. For each neighbor, decrement its in-degree. If it becomes 0, enqueue it.
5. If the result contains all nodes, the sort is valid. Otherwise, a cycle exists.

DFS-based topological sort

The DFS approach uses reverse post-order: when DFS finishes processing a node (all descendants explored), push it onto a stack. The stack gives the topological order.

def topological_sort_dfs(num_nodes, edges):
    """
    DFS-based topological sort using reverse post-order.
    Time: O(V + E)
    Space: O(V + E)
    """
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)

    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * num_nodes
    order = []
    has_cycle = False

    def dfs(node):
        nonlocal has_cycle
        if has_cycle:
            return

        color[node] = GRAY  # Currently being processed

        for neighbor in graph[node]:
            if color[neighbor] == GRAY:
                has_cycle = True  # Back edge = cycle
                return
            if color[neighbor] == WHITE:
                dfs(neighbor)

        color[node] = BLACK  # Fully processed
        order.append(node)

    for node in range(num_nodes):
        if color[node] == WHITE:
            dfs(node)

    if has_cycle:
        return []

    order.reverse()
    return order


edges = [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)]
result = topological_sort_dfs(6, edges)
print(f"DFS topological order: {result}")

The three colors explained

• WHITE: Node has not been visited yet.
• GRAY: Node is currently being processed (on the recursion stack). If we encounter a GRAY node, we have found a back edge, which means a cycle.
• BLACK: Node and all its descendants are fully processed.

Cycle detection

Both algorithms naturally detect cycles:

• Kahn’s: If the final order has fewer nodes than the total, a cycle exists (some nodes never reached in-degree 0).
• DFS: If we visit a GRAY node during DFS, that is a back edge indicating a cycle.

def has_cycle(num_nodes, edges):
    """
    Check if directed graph has a cycle using Kahn's algorithm.
    Time: O(V + E)
    """
    graph = defaultdict(list)
    in_degree = [0] * num_nodes

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

    queue = deque(node for node in range(num_nodes) if in_degree[node] == 0)
    visited_count = 0

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

    return visited_count != num_nodes


# No cycle
print(has_cycle(4, [(0, 1), (1, 2), (2, 3)]))  # False

# Has cycle: 0 -> 1 -> 2 -> 0
print(has_cycle(3, [(0, 1), (1, 2), (2, 0)]))  # True

Application 1: course schedule

LeetCode 207 and 210: given numCourses and a list of prerequisite pairs, determine if you can finish all courses, and if so, return a valid order.

def can_finish(numCourses, prerequisites):
    """
    LeetCode 207: Can you finish all courses?
    """
    graph = defaultdict(list)
    in_degree = [0] * numCourses

    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1

    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    count = 0

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

    return count == numCourses


def find_order(numCourses, prerequisites):
    """
    LeetCode 210: Return a valid course order, or [] if impossible.
    """
    graph = defaultdict(list)
    in_degree = [0] * numCourses

    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1

    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    order = []

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

    return order if len(order) == numCourses else []


# Example
prereqs = [[1, 0], [2, 0], [3, 1], [3, 2]]
print(can_finish(4, prereqs))       # True
print(find_order(4, prereqs))       # [0, 1, 2, 3] or [0, 2, 1, 3]

# Impossible case
prereqs_cycle = [[1, 0], [0, 1]]
print(can_finish(2, prereqs_cycle))  # False

Application 2: build system dependencies

A build system must compile files in dependency order. If file A imports file B, then B must be compiled before A.

def build_order(files, dependencies):
    """
    Given files and their dependencies, return a valid build order.

    files: list of file names
    dependencies: list of (file, depends_on) tuples
    """
    file_to_idx = {f: i for i, f in enumerate(files)}
    n = len(files)
    graph = defaultdict(list)
    in_degree = [0] * n

    for file, depends_on in dependencies:
        u = file_to_idx[depends_on]
        v = file_to_idx[file]
        graph[u].append(v)
        in_degree[v] += 1

    queue = deque(i for i in range(n) if in_degree[i] == 0)
    order = []

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

    if len(order) != n:
        raise ValueError("Circular dependency detected!")

    return order


files = ["app.py", "models.py", "utils.py", "config.py", "views.py"]
deps = [
    ("models.py", "utils.py"),
    ("config.py", "utils.py"),
    ("views.py", "models.py"),
    ("app.py", "views.py"),
    ("app.py", "config.py"),
]
print(build_order(files, deps))
# ['utils.py', 'models.py', 'config.py', 'views.py', 'app.py']

Application 3: longest path in a DAG

Unlike general graphs (where longest path is NP-hard), you can find the longest path in a DAG in O(V + E) using topological sort.

def longest_path_dag(num_nodes, edges):
    """
    Find the longest path in a weighted DAG.
    Time: O(V + E)
    Space: O(V + E)
    """
    graph = defaultdict(list)
    in_degree = [0] * num_nodes

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

    # Topological sort
    queue = deque(i for i in range(num_nodes) if in_degree[i] == 0)
    topo_order = []
    while queue:
        node = queue.popleft()
        topo_order.append(node)
        for neighbor, _ in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # Find longest distances
    dist = [float('-inf')] * num_nodes

    # Initialize source nodes
    for node in topo_order:
        if dist[node] == float('-inf'):
            dist[node] = 0

    for node in topo_order:
        if dist[node] != float('-inf'):
            for neighbor, weight in graph[node]:
                if dist[node] + weight > dist[neighbor]:
                    dist[neighbor] = dist[node] + weight

    return max(dist)


# Example: weighted DAG
edges = [(0, 1, 5), (0, 2, 3), (1, 3, 6), (1, 2, 2),
         (2, 4, 4), (2, 5, 2), (3, 5, 1), (4, 5, 1)]
print(f"Longest path length: {longest_path_dag(6, edges)}")
# Longest path: 0 -> 1 -> 3 -> 5 = 5 + 6 + 1 = 12

Application 4: alien dictionary

Given a sorted list of words in an alien language, determine the order of characters.

def alien_order(words):
    """
    Derive character ordering from sorted alien dictionary.
    Time: O(total characters across all words)
    """
    # Build graph
    graph = defaultdict(set)
    in_degree = {c: 0 for word in words for c in word}

    for i in range(len(words) - 1):
        w1, w2 = words[i], words[i + 1]
        min_len = min(len(w1), len(w2))

        # Check for invalid case: prefix comes after longer word
        if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
            return ""  # Invalid ordering

        for j in range(min_len):
            if w1[j] != w2[j]:
                if w2[j] not in graph[w1[j]]:
                    graph[w1[j]].add(w2[j])
                    in_degree[w2[j]] += 1
                break  # Only first difference matters

    # Kahn's algorithm
    queue = deque(c for c in in_degree if in_degree[c] == 0)
    result = []

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

    if len(result) != len(in_degree):
        return ""  # Cycle detected

    return "".join(result)


# Example
words = ["wrt", "wrf", "er", "ett", "rftt"]
print(f"Alien alphabet order: {alien_order(words)}")
# "wertf"

How it works:

1. Compare adjacent words to find character ordering constraints.
2. "wrt" vs "wrf": t comes before f.
3. "wrf" vs "er": w comes before e.
4. "er" vs "ett": r comes before t.
5. "ett" vs "rftt": e comes before r.
6. Build a graph from these constraints and topologically sort it.

Kahn’s vs DFS: when to use which

Feature	Kahn’s (BFS)	DFS
Cycle detection	Check if all nodes processed	Check for back edges (GRAY nodes)
Parallel processing	Natural: nodes at same level can run in parallel	Not natural
Lexicographic order	Use min-heap instead of queue	Harder to control
Implementation	Slightly more code (in-degree array)	Slightly less code
Iterative	Naturally iterative	Naturally recursive

import heapq

def topological_sort_lexicographic(num_nodes, edges):
    """
    Smallest lexicographic topological order using min-heap.
    Time: O(V log V + E)
    """
    graph = defaultdict(list)
    in_degree = [0] * num_nodes

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

    heap = [i for i in range(num_nodes) if in_degree[i] == 0]
    heapq.heapify(heap)

    order = []
    while heap:
        node = heapq.heappop(heap)  # Always pick smallest available
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                heapq.heappush(heap, neighbor)

    return order if len(order) == num_nodes else []


edges = [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)]
print(topological_sort_lexicographic(6, edges))
# [4, 5, 0, 2, 3, 1] - lexicographically smallest valid order

All-topological-sorts (backtracking)

Sometimes you need all valid orderings. This uses backtracking:

def all_topological_sorts(num_nodes, edges):
    """
    Generate all valid topological orderings.
    Warning: can be exponential in number of results!
    """
    graph = defaultdict(list)
    in_degree = [0] * num_nodes

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

    results = []

    def backtrack(order):
        if len(order) == num_nodes:
            results.append(order[:])
            return

        for node in range(num_nodes):
            if in_degree[node] == 0 and node not in order:
                # Choose
                for neighbor in graph[node]:
                    in_degree[neighbor] -= 1

                order.append(node)

                # Explore
                backtrack(order)

                # Un-choose
                order.pop()
                for neighbor in graph[node]:
                    in_degree[neighbor] += 1

    backtrack([])
    return results


edges = [(0, 1), (0, 2), (1, 3), (2, 3)]
for order in all_topological_sorts(4, edges):
    print(order)
# [0, 1, 2, 3]
# [0, 2, 1, 3]

Complexity analysis

Algorithm	Time	Space
Kahn’s (BFS)	O(V + E)	O(V + E)
DFS-based	O(V + E)	O(V + E)
Lexicographic (heap)	O(V log V + E)	O(V + E)
All orderings	O(V! in worst case)	O(V + E)
Cycle detection	O(V + E)	O(V + E)

Practice problems

Problem	Difficulty	Key Idea
Course Schedule (LC 207)	Medium	Cycle detection
Course Schedule II (LC 210)	Medium	Return topological order
Alien Dictionary (LC 269)	Hard	Build graph from word comparisons
Longest Path in DAG	Medium	Topo sort + relaxation
Parallel Courses (LC 1136)	Medium	Kahn’s with level tracking
Minimum Height Trees (LC 310)	Medium	Related to topological peeling
Sequence Reconstruction (LC 444)	Medium	Unique topological order
Sort Items by Groups (LC 1203)	Hard	Two-level topological sort

Key takeaways

1. Topological sort only works on DAGs (directed acyclic graphs).
2. Kahn’s algorithm is intuitive and naturally gives parallel task levels.
3. DFS-based approach uses reverse post-order and detects cycles via back edges.
4. The alien dictionary problem is a classic interview question that reduces to topological sort.
5. Longest path in DAG is solvable in O(V + E), unlike general graphs where it is NP-hard.