Topological Sort

The Intuition

A topological sort is a linear ordering of the vertices of a directed acyclic graph (DAG) such that for every edge u -> v, u appears before v in the order. The ordering exists if and only if the graph has no cycles. Two algorithms produce it:

Kahn's algorithm (BFS). Compute the in-degree of every vertex (number of incoming edges). Initialize a queue with all vertices that have in-degree 0; these have no prerequisites and can be emitted immediately. Pop a vertex, append it to the output, then decrement the in-degree of each of its neighbors. Whenever a neighbor's in-degree drops to 0, push it onto the queue. Repeat until the queue is empty.

If the output contains all V vertices, it is a valid topological order. If fewer, the remaining vertices form one or more cycles, and no topological order exists. This cycle detection is built into the algorithm at no extra cost, which makes Kahn's a popular choice for course-prerequisite problems (LC 207, 210).

DFS-based topological sort. Run DFS from every unvisited vertex. When a vertex finishes (all its out-neighbors have returned), push it onto a result stack. After every vertex has finished, pop the stack to produce the topological order. The reasoning: the last vertex to finish has no path leading further, so it should appear last; the first to finish has the most prerequisites finalized after it.

DFS-based requires separate cycle detection (3-color DFS) if the input is not guaranteed to be a DAG. Kahn's detects cycles for free.

Lexicographically smallest topological order. Replace Kahn's queue with a min-heap. Each pop returns the smallest available zero-in-degree vertex. Used in problems that ask for a specific ordering when multiple are valid (LC 1203 sort items by groups, LC 269 alien dictionary).

When to use

Course scheduling, build system dependencies, task ordering, compilation order, or any problem with prerequisites/dependencies that form a DAG.

When NOT to use

Graph has cycles (no valid ordering exists)
Undirected graph (topological sort is for DAGs only)
Need shortest path (use BFS/Dijkstra)

Pattern Recognition

Problem involves course prerequisites or prerequisite chainsProblem asks for a valid build order of componentsProblem describes task dependencies that must be resolved in order

Edge Cases

Cycle exists so no valid topological order is possible
Single node with no dependencies
Disconnected DAG with multiple independent subgraphs

Practice Problems

MediumCourse Schedule

MediumCourse Schedule II

HardAlien Dictionary

Key Points

•Only works on Directed Acyclic Graphs (DAGs)
•Kahn's algorithm uses in-degree counting + BFS
•DFS approach records nodes in reverse post-order
•If result size < number of nodes, a cycle exists
•Multiple valid orderings may exist

Code Template

from collections import deque

def topological_sort_kahn(graph, n):
    """Kahn's algorithm (BFS-based topological sort)."""
    in_degree = [0] * n
    for u in range(n):
        for v in graph[u]:
            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(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(order) != n:
        return []  # cycle detected
    return order

def topological_sort_dfs(graph, n):
    """DFS-based topological sort (reverse post-order)."""
    visited = [False] * n
    stack = []

    def dfs(u):
        visited[u] = True
        for v in graph[u]:
            if not visited[v]:
                dfs(v)
        stack.append(u)

    for i in range(n):
        if not visited[i]:
            dfs(i)

    return stack[::-1]

func topologicalSortKahn(graph [][]int, n int) []int {
    // Kahn's algorithm (BFS-based topological sort).
    inDegree := make([]int, n)
    for u := 0; u < n; u++ {
        for _, v := range graph[u] {
            inDegree[v]++
        }
    }

    queue := []int{}
    for i := 0; i < n; i++ {
        if inDegree[i] == 0 {
            queue = append(queue, i)
        }
    }

    order := []int{}
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        order = append(order, node)
        for _, neighbor := range graph[node] {
            inDegree[neighbor]--
            if inDegree[neighbor] == 0 {
                queue = append(queue, neighbor)
            }
        }
    }

    if len(order) != n {
        return nil // cycle detected
    }
    return order
}

public List<Integer> topologicalSortKahn(
    List<List<Integer>> graph, int n) {
    // Kahn's algorithm (BFS-based topological sort).
    int[] inDegree = new int[n];
    for (int u = 0; u < n; u++) {
        for (int v : graph.get(u)) {
            inDegree[v]++;
        }
    }

    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) queue.offer(i);
    }

    List<Integer> order = new ArrayList<>();
    while (!queue.isEmpty()) {
        int node = queue.poll();
        order.add(node);
        for (int neighbor : graph.get(node)) {
            if (--inDegree[neighbor] == 0) {
                queue.offer(neighbor);
            }
        }
    }

    if (order.size() != n) return List.of(); // cycle
    return order;
}

Common Mistakes

Applying to graphs with cycles (no valid ordering exists)
Forgetting to detect cycles via result size check
Not initializing in-degree array for all nodes

Related Patterns

CrackingWalnuts

GraphsTemplate 5 of 10

GraphIntermediateO(V + E) time, O(V) space