Topological Sort: Ordering a DAG So Every Prerequisite Comes First

It’s 7:58, you’re late, and you grab your shoes off the rack — then stop, because your socks aren’t on yet. You put the shoes back, pull on the socks, and only then the shoes. You didn’t think about it. Some things just have to come before other things, and your hands sorted the whole outfit into a workable order before your coffee had cooled.

That quiet re-ordering has a name. It’s topological sort — the algorithm that takes a pile of "this before that" rules and lays everything out in a single line where every rule still holds. It’s what a build tool runs before it compiles a line, what a course catalog runs to check your degree plan, what a spreadsheet runs before it recalculates a cell. By the end of this article you and I will have built it two different ways, and gone deep on the one fact that gives it teeth: if the rules ever loop back on themselves, no valid order exists — and topological sort is the thing that notices.

Let’s start nowhere near a computer

Forget graphs for a moment. Go back to getting dressed, and write the rules down as arrows: draw A → B to mean "put on A before B."

Socks before shoes. Underwear before trousers. Trousers before belt. Your shirt? No arrow at all — you can pull it on whenever. Lay those arrows out and you get a little map of constraints, not a fixed sequence. There are many ways to dress that obey it.

Here’s the whole idea in three moves, and every method below is just a different way to carry them out:

• An arrow is a "must come before." It doesn’t say immediately before — just somewhere earlier in the line. Socks have to precede shoes, but a shirt can slip in between them.
• A valid order is any line-up where every arrow still points forward. Read the order left to right; you should never have to walk backward along an arrow. There’s usually more than one such line, and they’re all equally correct.
• A node with no incoming arrows can safely go first. Nothing is required before it, so putting it on now can’t violate anything. Underwear, socks, and shirt all qualify — pick any of them to start.

That last move is the engine. Put on a garment that has nothing waiting before it; now cross it off, which may leave another garment with nothing before it; repeat until you’re dressed. And notice the failure mode hiding in plain sight: if you ever wrote down "left shoe before right shoe" and "right shoe before left shoe," you could never start — every garment would be waiting on another. Hold onto that. It’s the deep idea we build to.

Where you already meet it

Once you see "lay out the dependencies in a workable order," it’s running under half the tools you touch:

• Build systems and package managers. mvn package, npm install, make — each module depends on others, and the tool must compile a dependency before whatever needs it.
• Course prerequisites. You can’t take Algorithms before Data Structures; a degree audit is one big topological sort over the catalog.
• Spreadsheets. Change one cell and the app recomputes every formula that depends on it — in an order where inputs are ready before the cells that read them.
• Task schedulers and CI pipelines. "Run tests after build, deploy after tests" is a dependency graph, and the runner topologically sorts the stages.

The build system is worth a closer look, because it shows the algorithm doing two jobs at once with a single pass. A project’s modules form a directed graph: "app depends on core" is a one-way arrow. Before it builds anything, the tool has to produce an order — core before app, always — and enforce a veto: if app depends on core which somehow depends back on app, there’s no valid order at all, and the build must stop and shout "circular dependency." One topological sort answers both. It hands back a build order when one exists, and refuses — provably — when one can’t.

What it actually looks like

Let’s pin down the graph we’ll use for the rest of the build. Six courses, numbered 0 through 5, with an arrow u → v meaning "take u before v."

Course 0 (say, an intro class) has no prerequisites, so it sits at the far left. Courses 1 and 2 each need 0. Course 3 needs both 1 and 2; course 4 needs 1; and 5 needs both 3 and 4. Read the order below the graph — 0, 1, 2, 4, 3, 5 — and check it against every arrow: each one points from an earlier slot to a later slot. Not a single arrow runs backward. That’s what "valid" means, and it’s the only thing we’re trying to produce.

Let’s build Kahn’s algorithm, step by step

The first method reads straight off the analogy: repeatedly grab a node with nothing waiting before it. It’s called Kahn’s algorithm, and it has a distinctly breadth-first flavour — a queue of "ready" nodes that drains in waves, exactly like the ripples in breadth-first search. We’ll assemble the full class at the end; for now, one piece at a time.

Step 1 — count each node’s prerequisites

"Has nothing waiting before it" means "has no incoming arrows." So the one number we need per node is its in-degree: how many arrows point at it. Walk the edge list once and tally.

int[] inDegree = new int[n];
for (int[] e : edges) {
    inDegree[e[1]]++;          // edge u → v: v has one more prerequisite
}

Look at the "start" column: node 0 has in-degree 0, everything else is 1 or 2. That single zero is where the whole thing begins — it’s the only course you can take on day one. The rule: in-degree is a live count of unmet prerequisites, and it will drop as we remove nodes. Watch the columns fall to zero left to right; each new zero is a node that just became takeable.

Step 2 — seed the ready queue with the zeros

Every node that starts at in-degree 0 can go first, so drop them all into a queue of "ready to place" nodes.

Deque<Integer> ready = new ArrayDeque<>();
for (int v = 0; v < n; v++) {
    if (inDegree[v] == 0) {
        ready.add(v);          // no prerequisites — safe to place now
    }
}

On our course graph that queue starts as just [0]. On a graph with several independent starting points it’d hold all of them at once — and that’s correct, because any of them is a legal first pick.

Step 3 — peel: place a ready node, then free its neighbours

Now drain the queue. Take a ready node, append it to the output, and "remove" it by walking its outgoing arrows and decrementing each target’s in-degree. Any target whose count hits 0 has just lost its last prerequisite — so it’s ready, and joins the back of the queue.

List<Integer> order = new ArrayList<>();
while (!ready.isEmpty()) {
    int u = ready.poll();
    order.add(u);                  // nothing blocks u anymore
    for (int v : adj.get(u)) {
        if (--inDegree[v] == 0) {  // u was v's last remaining prerequisite
            ready.add(v);
        }
    }
}

The rule: a node is placed the instant its in-degree reaches zero, never a moment before. The graph peels in waves — first 0, then the 1, 2 it frees, then the 4, 3 those free, then 5. Each wave is a fresh layer of nodes with no unmet prerequisites, and the queue quietly holds the next wave while it works through the current one.

Step 4 — the bug: forgetting to count what came out

Here’s the trap, and it’s the one interviewers set. The loop above looks complete — it drains the queue and returns order. So ship it, right? Watch what it does on a graph with a cycle.

while (!ready.isEmpty()) {
    int u = ready.poll();
    order.add(u);
    for (int v : adj.get(u)) {
        if (--inDegree[v] == 0) {
            ready.add(v);
        }
    }
}
return order;                       // ← no check: silently returns a PARTIAL order

Feed it three courses in a loop — 0 → 1 → 2 → 0. Every node has in-degree 1, so the ready queue starts empty, the loop never runs, and this code cheerfully returns [] as if that were a valid ordering of three courses. Worse, add a clean node in front of the loop and it returns a partial order — the reachable prefix — with the looped nodes silently dropped. No exception, no error. It looks like an answer and it’s a lie.

The fix is one line: a valid order must contain every node, so compare the output size to n.

if (order.size() < n) {
    return List.of();               // fewer than n came out — a cycle blocked the rest
}
return order;

Why a short output means there was a cycle

That one-line check is doing something genuinely clever, and it deserves a real explanation — not "trust me, count the nodes." It’s the deep idea in Kahn’s algorithm, so let’s slow all the way down.

Look at that graph. Nodes 0 and 1 peel off cleanly, but 2, 3, 4 form a cycle — 2 → 3 → 4 → 2 — and the algorithm emits only 2 of the 5 nodes before the queue runs dry. Why can’t it finish? And why is a short output an ironclad proof of a cycle, not just a hint?

Here’s the claim, in two directions:

Kahn’s algorithm emits all n nodes if and only if the graph is acyclic.

Take the easy direction first. If the graph is a DAG, every node eventually comes out. A DAG always has at least one node with in-degree 0 (if every node had an incoming arrow, you could keep following arrows backward forever through finitely many nodes, which forces a repeat — a cycle — contradiction). So the queue is never empty while nodes remain: place one, and the argument repeats on the smaller graph that’s left, which is still a DAG. The peeling never stalls until everything is out.

Now the direction that matters — if a node never comes out, the graph has a cycle. A node is emitted exactly when its in-degree hits 0. So suppose some nodes are never emitted; call that leftover set S. Every node in S still has in-degree > 0, meaning it still has an incoming arrow — and that arrow’s source must also be in S, because any node outside S was already emitted and had its outgoing arrows decremented away. So every node in S has a predecessor inside S. Start anywhere in S and walk backward along those arrows: you can always take another step, but S is finite, so you must eventually revisit a node. A walk that returns to where it’s been is a cycle. The leftover nodes aren’t stuck by accident; they’re knotted into a loop that starves each other of ever reaching in-degree 0.

And that’s why the check is so cheap and so strong. You don’t run a separate cycle detector — the count you already have is one. If order.size() == n, the graph was a DAG and you hold a valid order; if it’s less, the missing nodes are exactly the ones trapped in cycles.

The tiniest version is three courses that each require another. No node has in-degree 0, so the ready queue is empty from the first instant, and the algorithm emits nothing — the same "shoes before socks, socks before shoes" knot from the analogy, now caught automatically.

The other way: DFS and reverse post-order

There’s a second route to the same destination, and it falls out of depth-first search almost for free. Instead of peeling from the front, you dive to the back.

The trick lives in when DFS records a node. Recall that DFS can stamp a node on the way in (pre-order) or on the way out — the instant it’s finished, after every node it points to is already done (post-order). That "finished" moment is the gold. A node finishes only after all of its dependents finish, so if you list nodes in the order they finish and then reverse it, every arrow ends up pointing forward.

private static boolean visit(List<List<Integer>> adj, int u, int[] colour, List<Integer> finished) {
    colour[u] = GREY;                  // u joins the current path
    for (int v : adj.get(u)) {
        if (colour[v] == GREY) {
            return false;              // an edge back to the current path = a cycle
        }
        if (colour[v] == WHITE && !visit(adj, v, colour, finished)) {
            return false;
        }
    }
    colour[u] = BLACK;                 // every descendant is done
    finished.add(u);                   // record on the way OUT (post-order)
    return true;
}

Run this on our course graph and the finish order comes out 5, 3, 4, 1, 2, 0 — the leaves finish first, node 0 finishes dead last because it can’t be done until everything below it is. Reverse that and you get 0, 2, 1, 4, 3, 5: a valid topological order, and a different one from Kahn’s, which is perfectly allowed.

Why finishing last means going first

This is the fact that makes the reversal work, and it’s worth one careful paragraph. Take any arrow u → v. When DFS is processing u, it looks at v. Two things can happen. Either v is untouched (white), so DFS dives into it and fully finishes v before it returns and finishes u — so v finishes first. Or v is already finished (black) from an earlier branch — again v finished before u. There is no third case in a DAG. So for every arrow u → v, v finishes before u. Reverse the finish order and that flips: u now comes before v. Every arrow points forward, which is the definition of a topological order. The reversal isn’t a trick — it’s the direct consequence of "a node isn’t done until its dependents are."

The one case we skipped is the third one Kahn’s also had to handle: what if v is grey — still on the current path, an ancestor we haven’t finished? That’s an arrow pointing back into the chain we’re standing on, which is a cycle, and no order exists. That’s the colour[v] == GREY check above. If you want the full three-colour story of why grey is the whole game — and why a directed graph needs three states where an undirected one needs only a parent-skip — it’s unpacked in the depth-first search article; here we just borrow the result.

Kahn’s vs DFS vs brute force

Both real methods run in linear time and both catch cycles; they differ in feel and in the extras they hand you. Let V be the nodes and E the edges.

The two linear methods are duals. Kahn’s builds the order forward by asking "who’s ready now?"; DFS builds it backward by asking "who finishes last?". Kahn’s avoids recursion (no stack-overflow risk on a million-deep chain) and naturally yields the lexicographically smallest order if you swap its queue for a min-heap. DFS is a two-line addition if you’re already walking the graph for something else. Both are O(V + E), and both refuse cyclic input — pick on ergonomics, not asymptotics.

Why O(V + E)? In Kahn’s, each node is enqueued and dequeued exactly once, and each edge is walked exactly once — when its source is placed and it decrements the target:

That sum of out-degrees is exactly E on a directed graph — every arrow has one tail — so the work is proportional to the size of the graph itself. You can’t do better; you have to look at every prerequisite at least once.

The complete implementation

Everything above, assembled — Kahn’s algorithm with its cycle check, and the DFS post-order version, sharing one adjacency-list builder:

package dev.fiveyear.toposort;
 
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
 
public final class TopologicalSort {
 
    private TopologicalSort() {}
 
    /** Kahn's algorithm: a topological order of the n-node DAG, or an empty list if it has a cycle. O(V + E). */
    public static List<Integer> kahn(int n, int[][] edges) {
        List<List<Integer>> adj = buildDirected(n, edges);
        int[] inDegree = new int[n];
        for (int[] e : edges) {
            inDegree[e[1]]++;              // one more prerequisite pointing at e[1]
        }
        Deque<Integer> ready = new ArrayDeque<>();
        for (int v = 0; v < n; v++) {
            if (inDegree[v] == 0) {
                ready.add(v);              // no prerequisites left — safe to place now
            }
        }
        List<Integer> order = new ArrayList<>();
        while (!ready.isEmpty()) {
            int u = ready.poll();
            order.add(u);                  // nothing blocks u anymore
            for (int v : adj.get(u)) {
                if (--inDegree[v] == 0) {  // u was v's last remaining prerequisite
                    ready.add(v);
                }
            }
        }
        if (order.size() < n) {
            return List.of();              // some nodes never hit in-degree 0 — a cycle blocked them
        }
        return order;
    }
 
    private static final int WHITE = 0;   // never touched
    private static final int GREY = 1;    // on the current DFS path
    private static final int BLACK = 2;   // finished, off the path
 
    /** DFS post-order reversed: the same job, cycle-safe. Empty list on a cycle. O(V + E). */
    public static List<Integer> dfs(int n, int[][] edges) {
        List<List<Integer>> adj = buildDirected(n, edges);
        int[] colour = new int[n];
        List<Integer> finished = new ArrayList<>();
        for (int s = 0; s < n; s++) {
            if (colour[s] == WHITE && !visit(adj, s, colour, finished)) {
                return List.of();          // stepped onto a grey ancestor — a cycle
            }
        }
        List<Integer> order = new ArrayList<>();
        for (int i = finished.size() - 1; i >= 0; i--) {
            order.add(finished.get(i));    // reverse the finish order
        }
        return order;
    }
 
    /** False if a cycle is found under u; otherwise records u in post-order once its subtree is done. */
    private static boolean visit(List<List<Integer>> adj, int u, int[] colour, List<Integer> finished) {
        colour[u] = GREY;                  // u joins the current path
        for (int v : adj.get(u)) {
            if (colour[v] == GREY) {
                return false;              // an edge back to the current path = a cycle
            }
            if (colour[v] == WHITE && !visit(adj, v, colour, finished)) {
                return false;
            }
        }
        colour[u] = BLACK;                 // all of u's descendants are done
        finished.add(u);                   // record on the way OUT (post-order)
        return true;
    }
 
    private static List<List<Integer>> buildDirected(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);       // edge u → v means "u must come before v"
        }
        return adj;
    }
}

And here it is producing exactly the outputs the comments claim, on the six-course graph we drew:

int n = 6;
// edge u → v means "take u before v"
int[][] courses = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 3}, {3, 5}, {4, 5}};
 
TopologicalSort.kahn(n, courses);   // [0, 1, 2, 4, 3, 5]
TopologicalSort.dfs(n, courses);    // [0, 2, 1, 4, 3, 5]  — a different but equally valid order
 
int[][] cyclic = {{0, 1}, {1, 2}, {2, 0}};
TopologicalSort.kahn(3, cyclic);    // []  — only 0 of 3 came out; a cycle blocked the rest
TopologicalSort.dfs(3, cyclic);     // []  — DFS stepped onto a grey ancestor
 
int[][] chain = {{0, 1}, {1, 2}};
TopologicalSort.kahn(3, chain);     // [0, 1, 2]  — a straight line orders itself

Both methods hand back a genuine topological order — walk any arrow in courses and its source lands before its target in both [0, 1, 2, 4, 3, 5] and [0, 2, 1, 4, 3, 5]. And both return an empty list on the cyclic graph, each catching the loop its own way: Kahn’s by counting the survivors, DFS by stepping onto a node still on its path.

The interview corner

Topological sort is a graph-round staple because it’s small to write and hides two subtleties — the cycle check and the direction of the order. Walk in knowing the questions to ask and the ladder they’ll climb.

Ask these before you write a line:

• "Is the graph guaranteed acyclic, or do I need to detect cycles?" This decides whether you can skip the order.size() == n check. In almost every real problem you cannot — "return an ordering or report it’s impossible" is the whole point, and the count is free, so keep it.
• "Which direction do the edges point — prerequisite to dependent, or the reverse?" Getting this backward silently reverses your answer. Say your convention out loud: here, u → v means "u before v," so v accumulates in-degree.
• "Do you want any valid order, or a specific one — lexicographically smallest, or ties broken by priority?" Any order → a plain queue. Smallest → swap Kahn’s ArrayDeque for a PriorityQueue. Naming this shows you know the order isn’t unique.

The follow-up ladder — where a strong candidate keeps climbing:

1. "Return the lexicographically smallest topological order." Kahn’s with a min-heap instead of a FIFO queue: whenever several nodes are ready, always place the smallest id first. Same O(E + V log V) shape, and DFS can’t do this cleanly — it’s Kahn’s home turf.
2. "Report which nodes are in the cycle, not just that one exists." After Kahn’s finishes, every node still at in-degree > 0 is on or downstream of a cycle — that leftover set is your answer, straight from the "why a short output means a cycle" argument.
3. "Find the longest chain of dependencies (the critical path)." Process nodes in topological order and relax dist[v] = max(dist[v], dist[u] + 1). Because you visit u before any v it points to, every dist[u] is final when you use it — this is the DAG shortest/longest-path trick, cousin to Dijkstra but linear.
4. "There are millions of nodes in one deep chain." Prefer Kahn’s — it’s iterative, so it can’t stack-overflow. Recursive DFS on a million-deep graph blows the call stack; you’d need the explicit-stack DFS from the depth-first search article.
5. "Count how many distinct valid orderings exist." That’s counting the linear extensions of a partial order — #P-hard in general, no known polynomial algorithm. Recognising that a natural-sounding follow-up is intractable is itself the strong answer.

Three mistakes that fail the round:

• Returning a partial order on a cyclic graph. Skip the order.size() == n check and you emit a plausible prefix and call it valid. It passes every acyclic test and lies on the first real cycle — always verify completeness.
• Reversing (or not reversing) the DFS result wrong. Post-order lists dependents before prerequisites; a topological order needs the opposite, so you must reverse it. Forget to, and every arrow in your output points backward.
• Confusing the edge direction. If u → v means "u before v," then v gains in-degree and you seed from in-degree zero. Flip the convention in your head and you’ll build the exact reverse of the order you wanted — right shape, wrong direction.

Where to go from here

You now own the core: an arrow is a "must come before," a node with no unmet prerequisites can go next, and you either place all n nodes or you’ve proven a cycle. Two methods, one guarantee — Kahn’s peels from the front counting in-degrees, DFS dives to the back and reverses its finish order. Three natural next stops:

• Shortest and longest paths in a DAG — once you have a topological order, a single linear pass relaxes edges in dependency order, no priority queue needed. It’s the fastest path algorithm there is, and it only works because the graph is acyclic.
• Strongly connected components — when the graph does have cycles and you want to collapse each loop into a super-node (then topologically sort those), that’s Tarjan’s or Kosaraju’s, the natural sequel built on the same DFS finish-order idea.
• The two traversals underneath it all — Kahn’s is breadth-first search wearing in-degrees; the post-order method is depth-first search read backward. Solid on those two and topological sort stops being a separate thing to memorise and becomes an obvious consequence.

Next time your build tool prints "compiling 47 modules" in some order you never chose, you’ll know exactly what happened: it drew the dependency arrows, found the modules with nothing waiting on them, and peeled the graph one ready layer at a time — and if two of your modules had ever depended on each other, it would have caught the loop before a single line compiled.