Topological Sort

Recognizing the problem

A topological sort orders the nodes of a directed graph so that every edge points forward. It applies whenever the statement describes dependencies:

• Courses with prerequisites
• Build targets that must compile before others
• Recipes where one step must precede another
• Anything phrased as “task A must happen before task B”

The order exists if and only if the graph has no directed cycle. A cycle means the dependencies are contradictory, and detecting that is often the actual question.

Kahn’s algorithm

Count how many prerequisites each node has. Repeatedly take a node with none left, output it, and remove its outgoing edges.

static List<Integer> topoSort(List<List<Integer>> adj, int n) {
    int[] inDegree = new int[n + 1];
    for (int u = 1; u <= n; u++) {
        for (int v : adj.get(u)) {
            inDegree[v]++;
        }
    }

    Deque<Integer> ready = new ArrayDeque<>();
    for (int u = 1; u <= n; u++) {
        if (inDegree[u] == 0) ready.add(u);
    }

    List<Integer> order = new ArrayList<>();
    while (!ready.isEmpty()) {
        int u = ready.poll();
        order.add(u);
        for (int v : adj.get(u)) {
            if (--inDegree[v] == 0) {
                ready.add(v);
            }
        }
    }

    // fewer than n nodes emitted means a cycle blocked the rest
    return order.size() == n ? order : null;
}

The --inDegree[v] == 0 idiom decrements and tests in one step. Each edge is examined exactly once, so the whole algorithm is O(V + E).

Lexicographically smallest order

When several nodes are ready at once, Kahn’s algorithm may output any of them. If the problem demands the alphabetically or numerically smallest valid order, swap the queue for a min-heap.

PriorityQueue<Integer> ready = new PriorityQueue<>();

Everything else is unchanged. The cost becomes O(V log V + E).

Only do this when the problem asks for it — the heap is unnecessary otherwise, and “any valid order” is the more common requirement.

DFS-based ordering

The alternative: depth-first search, appending each node after all of its descendants, then reversing.

static int[] state;                  // 0 = unvisited, 1 = in progress, 2 = done
static List<Integer> post = new ArrayList<>();
static boolean hasCycle = false;

static void dfs(int u, List<List<Integer>> adj) {
    state[u] = 1;
    for (int v : adj.get(u)) {
        if (state[v] == 1) {         // edge back into the current path
            hasCycle = true;
            return;
        }
        if (state[v] == 0) dfs(v, adj);
    }
    state[u] = 2;
    post.add(u);
}

// after running dfs from every unvisited node:
Collections.reverse(post);

The three-state marker is what distinguishes a cycle from a merely revisited node. A node in state 1 is on the current recursion stack, so an edge to it closes a cycle. A node in state 2 is finished, and an edge to it is harmless.

Using a plain boolean[] visited cannot tell those apart and will report cycles that do not exist.

Dynamic programming along the order

This is the reason topological sort matters beyond ordering. Once nodes are in topological order, every node’s dependencies are already computed when you reach it, so a DP over the graph becomes a single pass.

Find the longest path in a directed acyclic graph.

List<Integer> order = topoSort(adj, n);

int[] longest = new int[n + 1];       // longest path ending at each node
int best = 0;

for (int u : order) {
    for (int v : adj.get(u)) {
        if (longest[u] + 1 > longest[v]) {
            longest[v] = longest[u] + 1;
        }
    }
    best = Math.max(best, longest[u]);
}

Longest path is NP-hard on a general graph but linear on a DAG, precisely because the topological order removes any circular dependency.

The same shape counts paths, finds minimum costs, or propagates any value forward:

// number of distinct paths from node 1 to node n, modulo a prime
long[] ways = new long[n + 1];
ways[1] = 1;
for (int u : order) {
    for (int v : adj.get(u)) {
        ways[v] = (ways[v] + ways[u]) % MOD;
    }
}

Problems that reduce to a topological sort

Related