Topological Sort — Ordering Dependencies

Topological sort answers one question: given a set of tasks with dependencies, in what order should the tasks be performed? It produces a linear ordering of vertices in a directed graph such that for every directed edge u→v, vertex u appears before vertex v in the ordering.

This only makes sense on a directed acyclic graph (DAG). If the graph has a cycle, no such ordering exists — you’d have a circular dependency where task A requires B, B requires C, and C requires A. Topological sort is therefore simultaneously an ordering algorithm and a cycle detector.

Existence Condition

A topological ordering exists if and only if the graph is a DAG. If the graph contains any cycle, topological sort will fail to produce an ordering that covers all vertices — and this failure is how you detect the cycle.

Algorithm 1: Kahn’s Algorithm (BFS-Based)

Kahn’s algorithm is the more intuitive of the two. The idea: nodes with no incoming edges (in-degree 0) have no prerequisites — they can go first. Process them, remove their edges, and repeat. If at any point there are no zero-in-degree nodes left but unprocessed nodes remain, there’s a cycle.

Step-by-step:

  1. Compute in-degree for every vertex

  2. Enqueue all vertices with in-degree 0

  3. Dequeue a vertex, add to result, decrement in-degree of all its neighbors

  4. Enqueue any neighbor whose in-degree just dropped to 0

  5. Repeat until queue is empty

  6. If result contains all V vertices: valid topological order. If fewer: graph has a cycle.

List<Integer> kahnTopologicalSort(int V, List<List<Integer>> adj) {
    int[] inDegree = new int[V];

    // Step 1: compute in-degree
    for (int u = 0; u < V; u++)
        for (int v : adj.get(u))
            inDegree[v]++;

    // Step 2: enqueue all zero-in-degree nodes
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < V; i++)
        if (inDegree[i] == 0)
            queue.offer(i);

    List<Integer> result = new ArrayList<>();

    // Steps 3-5
    while (!queue.isEmpty()) {
        int node = queue.poll();
        result.add(node);

        for (int neighbor : adj.get(node)) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0)
                queue.offer(neighbor);
        }
    }

    // Step 6: cycle detection
    if (result.size() != V) return new ArrayList<>();  // cycle exists
    return result;
}

Time: O(V + E). Every vertex is enqueued/dequeued once, every edge is processed once. Space: O(V) for in-degree array + queue.

Algorithm 2: DFS-Based Topological Sort

The observation: in DFS, a node finishes (gets its finish time) only after all nodes reachable from it have finished. So the finish order is the reverse topological order — nodes that must come last finish first.

void dfsTopSort(int node, boolean[] visited, Deque<Integer> stack, List<List<Integer>> adj) {
    visited[node] = true;

    for (int neighbor : adj.get(node)) {
        if (!visited[neighbor]) {
            dfsTopSort(neighbor, visited, stack, adj);
        }
    }

    stack.push(node);    // push AFTER all descendants are processed
}

List<Integer> dfsTopologicalSort(int V, List<List<Integer>> adj) {
    boolean[] visited = new boolean[V];
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < V; i++)
        if (!visited[i])
            dfsTopSort(i, visited, stack, adj);

    List<Integer> result = new ArrayList<>();
    while (!stack.isEmpty()) result.add(stack.pop());
    return result;
}

The result is the reverse of the stack: nodes popped first are the ones that must appear first in the topological order.

Note: the DFS-based version doesn’t naturally detect cycles without the three-color scheme. Use Kahn’s when you also need cycle detection (which is most interview problems).

Cycle Detection via Kahn’s

The cycle detection property of Kahn’s is worth emphasizing: if there’s a cycle, no node in the cycle ever reaches in-degree 0 (because each node in the cycle depends on another node in the cycle). So the queue empties before all nodes are processed. result.size() < V is the cycle indicator.

This is used directly in: Course Schedule (LC 207), Course Schedule II (LC 210), Build Dependency Order.

What most people get wrong: building the graph with edges in the wrong direction. If the problem says “course b is a prerequisite of course a” (meaning b must come before a), the directed edge is b→a, not a→b. Getting the edge direction backwards gives you a reversed topological order, which fails silently on small test cases and breaks on larger ones.

The phrasing to watch for:

  • “a depends on b” → edge b→a (b must come before a)

  • “a must be completed before b” → edge a→b

  • “there is a directed edge from u to v” → edge u→v (read the problem literally)

Before coding, write out 2-3 nodes and their constraint explicitly: “node X must appear before node Y, so edge is X→Y.” Verify your graph construction on this example.

Applications

Build systems (Make, Gradle, Maven): source files have compilation dependencies. Topological sort determines build order.

Course prerequisites: a classic — if course A requires course B, B must be taken first. Topological sort gives a valid semester sequence.

Task scheduling: any project with task dependencies can be scheduled in topological order.

Dependency resolution (npm, pip): installing packages in an order that satisfies all dependencies.

Evaluating formulas in a spreadsheet: cell A depends on B, B depends on C. Evaluate in topological order.

Compiler type resolution: if type A uses type B, B must be defined first.

Practice Problems

#

Problem

Difficulty

Core

1

LC 207 — Course Schedule

Medium

Cycle detection via Kahn’s

2

LC 210 — Course Schedule II

Medium

Return topological order

3

LC 269 — Alien Dictionary

Hard

Infer directed graph from word order, topological sort

4

LC 1136 — Parallel Courses

Medium

Topological sort + level timing

Problem 3 (Alien Dictionary) is the hard problem that tests whether you can construct the graph from non-obvious constraints, not just run the algorithm on a given graph. The trick: compare adjacent words in the sorted list character-by-character to infer ordering. The first character where two words differ gives you a directed edge. Build the graph, run topological sort.

For LC 1136 (Parallel Courses): the answer is the number of “levels” in the topological order — courses that can be taken simultaneously form one level. This is Kahn’s algorithm where you track the level number: every batch of nodes dequeued together forms one semester.