Topological Sort

Topological sort works because a directed acyclic graph (DAG) has at least one node with in-degree zero at every stage of peeling — repeatedly stripping off a source (a node with no unprocessed prerequisites) and recording it produces a linear order where every edge u -> v has u appearing before v; this is only possible when the graph has no cycles, since a cycle would leave every node in it permanently waiting on another.

Recognize the pattern

• The problem talks about dependencies, prerequisites, or ordering: "build A before B", "course X requires course Y", "task must run after task Z".
• Relationships form a directed graph, and cycles would make the task impossible — e.g. "course schedule", "build system", "package manager dependency resolution", "compilation order".
• You need any one valid linear order, not shortest path or minimum cost — the question is feasibility and sequencing, not weight.
• Phrases like "can all tasks be completed", "is there a valid order", "detect a deadlock/cycle" are strong tells.

Brute force vs. the real algorithm

Naive baseline: repeatedly scan all V nodes, find any node whose prerequisites are already placed, place it, remove it, and restart the scan from the top. Each full scan costs O(V + E) (check every node's incoming edges), and you repeat the scan V times → O(V · (V + E)) total. It works but rediscovers the same in-degree information from scratch every round.

Kahn's algorithm (BFS-flavored, in-degree counting) and the DFS finish-time algorithm both keep running state so every node and edge is examined a constant number of times overall, dropping the cost to linear.

Kahn's algorithm (BFS on in-degrees)

1. Compute in-degree[v] for every node (count of incoming edges).
2. Push all nodes with in-degree 0 into a queue — these have no unmet prerequisite.
3. Pop a node u, append it to the result order.
4. For each edge u→v, decrement in-degree[v]. If it hits 0, push v.
5. Repeat until the queue is empty. If the result has fewer than V nodes, a cycle exists among the leftover nodes — no valid order.

import java.util.*;

public class TopoKahn {
    // returns topological order, or empty list if a cycle exists
    public static List<Integer> topoSort(int n, List<List<Integer>> adj) {
        int[] indeg = new int[n];
        for (int u = 0; u < n; u++)
            for (int v : adj.get(u)) indeg[v]++;

        Deque<Integer> queue = new ArrayDeque<>();
        for (int v = 0; v < n; v++)
            if (indeg[v] == 0) queue.add(v);

        List<Integer> order = new ArrayList<>();
        while (!queue.isEmpty()) {
            int u = queue.poll();
            order.add(u);
            for (int v : adj.get(u)) {
                if (--indeg[v] == 0) queue.add(v);
            }
        }
        if (order.size() != n) return new ArrayList<>(); // cycle detected
        return order;
    }
}

DFS finish-time algorithm

Run DFS from every unvisited node. When a node has no more unexplored outgoing edges (it "finishes"), push it onto a stack. Because a node only finishes after all nodes reachable from it have already finished, reversing the finish order (or popping the stack) yields a valid topological order. Cycle detection needs a third color: a node currently on the recursion stack (gray) reached again means a back-edge → cycle.

import java.util.*;

public class TopoDFS {
    private static final int WHITE = 0, GRAY = 1, BLACK = 2;

    public static List<Integer> topoSort(int n, List<List<Integer>> adj) {
        int[] color = new int[n];
        Deque<Integer> finishStack = new ArrayDeque<>();
        for (int v = 0; v < n; v++) {
            if (color[v] == WHITE) {
                if (dfs(v, adj, color, finishStack)) {
                    return new ArrayList<>(); // cycle detected
                }
            }
        }
        List<Integer> order = new ArrayList<>();
        while (!finishStack.isEmpty()) order.add(finishStack.pop());
        return order;
    }

    // returns true if a cycle is detected
    private static boolean dfs(int u, List<List<Integer>> adj, int[] color, Deque<Integer> finishStack) {
        color[u] = GRAY;
        for (int v : adj.get(u)) {
            if (color[v] == GRAY) return true; // back-edge -> cycle
            if (color[v] == WHITE) {
                if (dfs(v, adj, color, finishStack)) return true;
            }
        }
        color[u] = BLACK;
        finishStack.push(u); // record finish time
        return false;
    }
}

Why the thread safety matters: In real production backend code, topological sorting (e.g., resolving dependencies in a request handler) is executed concurrently across multiple threads. Using static/shared mutable state like `hasCycle` causes data races that silently corrupt results or report false cycles. By passing the state through local variables and returning status directly from recursive frames, the code becomes completely thread-safe.

Recursion Safety in Production: Stack vs. Heap

While the recursive DFS implementation above is mathematically elegant and simple to write, it carries a severe operational risk: Call Stack Exhaustion. Recursive functions allocate a stack frame on the OS call stack (which defaults to a tight limit, e.g., 1MB in Java). If the dependency graph is highly linear or skewed with a depth exceeding roughly 10,000 nodes, running recursive DFS will crash the application thread with a StackOverflowError.

To write production-safe code, we must migrate the call stack frames to the heap by using an explicit stack collection (e.g., Deque). This allows the traversal to scale up to the limits of available system RAM (gigabytes) rather than the call stack limit (megabytes).

import java.util.*;

public class TopoDFSIterative {
    private static final int WHITE = 0, GRAY = 1, BLACK = 2;

    public static List<Integer> topoSort(int n, List<List<Integer>> adj) {
        int[] color = new int[n];
        Deque<Integer> finishStack = new ArrayDeque<>();
        
        for (int start = 0; start < n; start++) {
            if (color[start] != WHITE) continue;
            
            Deque<Integer> stack = new ArrayDeque<>();
            stack.push(start);
            
            while (!stack.isEmpty()) {
                int u = stack.pop();
                if (color[u] == WHITE) {
                    color[u] = GRAY;
                    stack.push(u); // push back to color black when all neighbors finish
                    for (int v : adj.get(u)) {
                        if (color[v] == GRAY) return new ArrayList<>(); // cycle detected
                        if (color[v] == WHITE) {
                            stack.push(v);
                        }
                    }
                } else if (color[u] == GRAY) {
                    color[u] = BLACK;
                    finishStack.push(u);
                }
            }
        }
        
        List<Integer> order = new ArrayList<>();
        while (!finishStack.isEmpty()) {
            order.add(finishStack.pop());
        }
        return order;
    }
}

Complexity, derived from first principles

Kahn's algorithm: building in-degrees scans every edge once → O(E). Each node is pushed to the queue exactly once (when its in-degree first hits 0) and popped exactly once → O(V) queue operations. Each edge is examined exactly once when its source is popped (to decrement the target's in-degree) → O(E). Total time O(V + E). Space: in-degree array O(V), queue holds at most V nodes O(V), result list O(V) → O(V) auxiliary space (plus the O(V+E) adjacency list itself).

DFS algorithm: each node is visited (colored gray then black) exactly once, and the inner loop over each node's outgoing edges runs once per node → total edge examinations across all calls = O(E), total node visits = O(V). Total time O(V + E). Space: color array O(V), recursion stack up to O(V) in the worst case (a long chain), finish stack O(V) → O(V) auxiliary space.

Both are asymptotically identical; the constant-factor difference is recursion overhead (DFS) vs. explicit queue management (Kahn's).

Traced worked example

Graph (6 build targets 0–5) with edges: 5→2, 5→0, 4→0, 4→1, 2→3, 3→1. Read "5→2" as "5 must build before 2".

Kahn's trace

Initial in-degrees: 0:2, 1:2, 2:1, 3:1, 4:0, 5:0.

Result has all 6 nodes → valid order 4, 5, 2, 0, 3, 1.

DFS trace

Visit nodes in id order 0..5, pushing to a finish-stack on completion.

1. DFS(0): no out-edges → finish 0. Stack: [0]
2. DFS(1): no out-edges → finish 1. Stack: [0,1]
3. DFS(2): visits 3 first (3→1 already black, skip) → finish 3, then finish 2. Stack: [0,1,3,2]
4. DFS(3): already black, skip.
5. DFS(4): edges to 0 (black) and 1 (black), nothing new → finish 4. Stack: [0,1,3,2,4]
6. DFS(5): edges to 2 (black) and 0 (black) → finish 5. Stack: [0,1,3,2,4,5]

Popping the stack gives order 5, 4, 2, 3, 1, 0 — a different but equally valid topological order (both satisfy every edge constraint; topological order is not unique).

Pitfalls

• Cycles silently ignored: if you forget to check order.size() == n (Kahn's) or track the gray/recursion-stack state (DFS), a cyclic graph produces a partial, wrong order instead of an error.
• Stale shared state across calls: a flag like hasCycle that lives outside the function (a static/instance field) must be reset at the start of every call; otherwise one cycle-containing run poisons every subsequent call, even on a valid DAG. Prefer returning the flag as part of the result instead of mutating shared state.
• White/black-only DFS coloring: using just visited/unvisited (2 colors) instead of white/gray/black cannot distinguish "currently being explored above me on the stack" (a real back-edge/cycle) from "already fully explored elsewhere" (a harmless cross-edge in a DAG) — this is the single most common correctness bug in DFS-based topo sort.
• Off-by-one on push timing: in the DFS version, pushing a node to the finish-stack before recursing into its neighbors (instead of after) produces a completely invalid order — the push must happen on finish, not on discovery.
• Disconnected components: a single DFS call or a single BFS seed will miss nodes in other components; you must loop over all nodes and start DFS/seed the queue from every unvisited/in-degree-0 node, not just node 0.
• Non-uniqueness surprises: multiple valid orders usually exist (see the two different results above); don't assume there is one "correct" answer to check against — verify by checking every edge points forward in your output order instead. The order is unique in exactly one case: when the DAG contains a Hamiltonian path (a single chain that already forces the relative position of every pair of nodes) — equivalently, when Kahn's queue never holds more than one node at a time.
• Negative or weighted edges are irrelevant here — topo sort ignores weights entirely; conflating it with shortest-path algorithms (which do care about edge weights/signs) is a category error.

When to use / when not, and trade-offs

Use topological sort when: you have a DAG of dependencies and need any valid linear execution order, or you need to detect whether a cyclic dependency makes the task impossible (circular build dependency, deadlocked course prerequisites, a cyclic import graph).

Do not use it when: edges have weights and you need the cheapest/longest path through the DAG — topo order is a building block for DAG shortest/longest path (process nodes in topo order, relax edges once each), not a replacement for it. Also skip it if the graph is undirected, or if you need all valid orderings (that requires backtracking, not a single linear pass).

Prefer Kahn's when you also want to process nodes level-by-level (e.g. parallel task scheduling: everything in one queue-pop "wave" can run concurrently) or when recursion depth is a concern. Prefer DFS-based when you're already running DFS for other reasons (e.g. computing SCCs via Tarjan/Kosaraju, which uses the same finish-time idea).