Topological Sort

On this page

The Idea
Build It
Know It
Break It
Use It

Quick reference

DFS-based topological sort	O(V + E)
Kahn's algorithm	O(V + E)

The Idea

Getting dressed has rules, but not a full order. Socks come before shoes. Underwear comes before pants. But underwear and socks can go on in either order — nothing forces one before the other. A topological sort is exactly that: an arrangement of items where every dependency comes before the thing depending on it, while anything with no relationship to each other can land in any order, and multiple correct arrangements can exist side by side.

Only one shape of graph can be arranged this way at all: directed, and with no cycle — a DAG, short for 'directed acyclic graph.' Directed, because 'before' only makes sense if edges have a direction — an edge from socks to shoes means socks-before-shoes, not the reverse. Acyclic, because a cycle breaks the whole premise: if A must come before B, B before C, and C before A, there is no starting point — every candidate for 'first' has something behind it demanding to go earlier still. No valid order exists, and that has to be detected, not silently ignored.

This only works on a DAG. Directed graphs generally, and undirected graphs entirely, don't have a meaningful topological order — 'before' requires direction, and a cycle anywhere removes the possibility of a valid arrangement altogether.

Build It

Two ways to the same order

structure Graph (adjacency list, directed):
    adj: map from node -> list of nodes it points TO (its dependents)

structure InDegree:
    inDegree: map from node -> count of edges pointing INTO it
    // a node with inDegree 0 has nothing left it's waiting on

DFS-based — finish a node, then push it; reverse at the end

function topoSortDFS(nodes, adj):
    visited = {}
    stack = []                          // built in FINISH order, not visit order
    function dfs(node):
        if node in visited:
            return
        visited.add(node)
        for neighbor in adj[node]:
            dfs(neighbor)
        stack.push(node)                 // every dependent already pushed — node is done
    for node in nodes:
        dfs(node)
    return reverse(stack)

Direct generalization of Binary Trees' postorder traversal: visit children first, visit yourself last. A node only gets pushed once every node it points to has already finished and been pushed — which means it lands behind all of its dependents on the stack. Reversing at the end puts dependencies first, dependents after, exactly the order the idea needs. Skipping the reverse is the single easiest mistake to make here — the raw stack is backwards.

Kahn's algorithm — BFS-based, using in-degree

function topoSortKahn(nodes, adj):
    inDegree = {node: 0 for node in nodes}
    for node in nodes:
        for neighbor in adj[node]:
            inDegree[neighbor] += 1

    queue = Queue()
    for node in nodes:
        if inDegree[node] == 0:          // nothing left it's waiting on — safe to start
            enqueue(queue, node)

    result = []
    while queue is not empty:
        node = dequeue(queue)
        result.append(node)
        for neighbor in adj[node]:
            inDegree[neighbor] -= 1      // node is done — one less thing neighbor waits on
            if inDegree[neighbor] == 0:
                enqueue(queue, neighbor)

    return result

Same queue pattern as Phase 3 and Graph Fundamentals' BFS, repurposed: instead of tracking 'visited,' it tracks 'how many prerequisites are left,' and a node only joins the queue once that count hits zero. No recursion, no explicit visited set, and — as Break It covers — the length of result at the end is what tells you whether a cycle exists.

Know It

Both approaches are just a structured single pass over the graph — no extra searching, no revisiting. Kahn's builds and drains an in-degree map once; the DFS version runs one DFS over every node once. Neither does more work than a plain traversal already would.

Operation	Time	Space	Why
DFS-based topological sort	O(V + E)	O(V)	Standard DFS traversal cost, plus a stack that holds each node exactly once — no node is pushed twice.
Kahn's algorithm	O(V + E)	O(V)	Building in-degree counts is O(V + E); every node enters and leaves the queue exactly once, and every edge is examined exactly once to decrement a count.

Break It

Running it on a graph that actually has a cycle

the dependency graph isn't really a DAG

The DFS version will still produce some order without crashing — it just won't be valid, because no valid order exists. Kahn's algorithm gives a cleaner signal: if a cycle exists, every node inside that cycle is permanently stuck waiting on another node in the same cycle, so its in-degree never reaches zero and it's never enqueued. result ends up shorter than nodes. Checking len(result) == len(nodes) at the end — not just returning result and trusting it — is what turns 'silently wrong' into 'correctly reports impossible.'

Applying this to an undirected graph

the input graph has no edge direction

'Before' has no meaning without direction — an undirected edge between A and B says they're connected, not that one comes first. In-degree isn't even well-defined on an undirected graph the way Kahn's algorithm needs it. If a problem hands you undirected edges and asks for an ordering, something upstream is wrong with the setup, not the algorithm.

Assuming there's exactly one valid order

comparing your output to someone else's, or to an expected test answer

Socks-then-pants-then-shoes and pants-then-socks-then-shoes are both valid if nothing constrains socks relative to pants directly. Whenever Kahn's queue holds more than one node at once, either could go next and the choice changes the final order without making it wrong. A checker for this kind of problem has to verify the ordering property (every edge points from earlier to later in the result) rather than compare against one fixed expected sequence.

Forgetting the DFS version's final reverse

using the DFS-based approach specifically — Kahn's has no equivalent step to forget

The stack in topoSortDFS() is built in finish order: a node is pushed only after everything it points to has already finished and been pushed. That means dependents end up below their dependencies on the stack, not above — the raw stack reads dependents-first. It looks like a real ordering (it has the right nodes, it just runs backwards), which makes it an easy bug to miss until it's checked against an actual dependency edge.

Use It

Course Schedule

Revisit from Graph Fundamentals — same cycle check, now framed as: can these prerequisites be satisfied at all? A DAG means yes.

Medium

Course Schedule II

Course Schedule, but return the order instead of a yes/no — topoSortKahn() or topoSortDFS() from Build It, verbatim, with the cycle check from Break It guarding an empty-array return.

Medium

Minimum Height Trees

A Kahn's-style layer-by-layer peel, but from the leaves inward instead of from in-degree-0 nodes outward — repeatedly strip every current leaf until 1 or 2 nodes remain.

Medium

Find Eventual Safe States

Reverse every edge, then run Kahn's from the nodes with no outgoing edges in the reversed graph (in-degree 0 there) — a node is 'safe' exactly when it gets reached.

Medium

All Ancestors of a Node in a Directed Acyclic Graph

Process nodes in topological order from Build It; when a node is processed, hand its own ancestor set (plus itself) forward to every node it points to.

Medium

Course Schedule IV

Process nodes in topological order and propagate reachability forward: a node inherits every prerequisite reachable from each of its own direct prerequisites.

Medium

Find All Possible Recipes from Given Supplies

Kahn's algorithm exactly: a recipe's in-degree is its ingredient count, supplies start at in-degree 0, and a recipe 'unlocks' (enqueues) once every ingredient it needs has been produced.

Medium

Minimum Number of Vertices to Reach All Nodes

No traversal needed — the answer is exactly the nodes with in-degree 0, the same set Kahn's algorithm seeds its queue with.

Medium