Topological Sort

What is this?

When you get dressed, socks go on before shoes and shirt before jacket — some things simply must come before others. Topological sort takes a pile of tasks with "do this first" rules and lines them all up so that every rule is respected: nothing appears before something it depends on. The trick is wonderfully simple — keep grabbing whatever has no unfinished prerequisites left, do it, and watch what that frees up next.

💡 Fun fact: every time you run a build tool like Make, install software with a package manager, or schedule data jobs in a pipeline like Airflow, a topological sort is running under the hood to figure out the correct order — and a "circular dependency" error is just the tool telling you it found a loop that no valid order can untangle.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: when things depend on other things, lay them out in a single line so that every arrow points forward — each item appears only after everything it needs. That line is a topological order, it exists exactly when the dependency graph has no cycle, and you can build it in one linear pass by repeatedly emitting whatever currently depends on nothing.

1. What topological sort really means

A topological order of a directed graph is a linear arrangement of its vertices such that for every edge u → v, u comes before v. Read the edge as a dependency — "u must happen before v" — and a topo order is simply a valid schedule.

Two facts do all the work:

• Only DAGs have one. If there's a directed cycle x → … → x, then x would have to come before itself — impossible. Acyclic ⟺ a topological order exists. So topo-sorting is a cycle detector.
• It's usually not unique. Vertices with no dependency between them (b and c above) can appear in either relative order. "Return any valid order" is the norm; a specific one (e.g. lexicographically smallest) is a deliberate variant.

⚠️ The recurring trap is edge direction. "To do A you need B" is the dependency edge B → A, not A → B. Flip it and you get a confident, perfectly-sorted, completely wrong answer.

2. Where you'll actually meet this

A topological sort is the engine behind an enormous amount of real infrastructure:

• Build systems & package managers. make, Bazel, Gradle, npm/pip/cargo resolve a dependency graph into a build/install order — and emit a "circular dependency" error, which is just a detected cycle.
• Distributed systems — orchestration & startup. Kubernetes init-containers, systemd After=/Requires=, and microservice boot ordering all topo-sort a service dependency graph (DB before API before gateway).
• CI/CD & data pipelines. The "DAG" in Airflow, Dagster, dbt, and Spark stage graphs is literally this: stages run in topological order, and the system rejects cyclic definitions.
• Spreadsheets & reactive systems. Cell/formula recalculation and reactive-UI update propagation walk a dependency graph in topo order; a circular reference is a cycle.
• Compilers & schedulers. Symbol/module resolution, class-initialization order, and instruction scheduling are topological sorts; critical-path and shortest-path-in-DAG algorithms run on top of a topo order.

Whenever the problem is "order these so dependencies come first," or "is this set of constraints even satisfiable," this is the tool.

3. The topo-sort toolkit

Two standard algorithms, both O(V + E), plus two variations worth knowing:

1. Kahn's algorithm (BFS on indegrees). Compute each vertex's indegree (number of incoming edges = unmet dependencies). Seed a queue with all indegree-0 vertices, then repeatedly pop one, emit it, and decrement each neighbor's indegree — any that reach 0 join the queue. Iterative, no recursion, and the cycle test is free (next point).
2. DFS post-order + reverse. Depth-first search; append each vertex after its descendants are done (post-order), then reverse. A vertex re-encountered while still on the recursion stack ("gray") is a back-edge ⇒ cycle. Elegant but watch recursion depth and remember the final reverse.
3. Cycle ⟺ no valid order. With Kahn's, if you emit fewer than V vertices, the leftovers are trapped in a cycle ⇒ "impossible." This single count is how dependency-resolution problems report failure.
4. Lexicographically-smallest variant. Need the canonical order, not just any? Replace Kahn's plain queue with a min-heap so you always emit the smallest available vertex. Cost becomes O(V log V + E).

The mental anchor: indegree 0 means "no remaining prerequisites," which means "safe to place next."

4. A 30-second worked example (Kahn's by hand)

Graph a→b, a→c, b→d, c→d, c→e (the DAG from §1). Track indegrees and sweep:

One queue, one indegree array, every node and edge touched once — and "5 of 5 emitted" certifies there was no cycle. That emit-the-ready-node, relax-its-edges, count-at-the-end loop is the whole chapter.

5. Problems in this chapter

▶ Course Schedule II

Given courses and prerequisite pairs [a, b] ("b before a"), return a full order to finish all courses, or [] if a cycle makes it impossible. The textbook dependency resolver: build the graph, run Kahn's, and let the emitted count flag cycles.
Pattern: topological sort / indegree BFS. Target: O(V + E), O(V + E).

▶ Alien Dictionary

Given words sorted under an unknown alphabet, recover the letter order. The twist is graph construction: each adjacent word pair's first differing character is one edge; then topo-sort the letters. Two failures return "" — a cycle (contradictory rules) and the sneaky prefix violation (a longer word sorted before its own prefix).
Pattern: derive edges from comparisons, then topological sort. Target: O(C + V + E), O(V + E).

6. Common pitfalls 🚫

• Backwards edges. "X needs Y" is Y → X. The single most common bug — produces a clean but invalid order.
• Forgetting the cycle check. No len(order) == V test (Kahn's) or no gray/on-stack detection (DFS) means cyclic input silently returns a partial, wrong answer instead of "impossible."
• Dropping disconnected / unconstrained nodes. Vertices with no edges still belong in the output. Seed indegree for every vertex, not just those that appear in an edge.
• DFS slip-ups. Forgetting to reverse the post-order, or confusing "visited" (black) with "on the current stack" (gray) so cycles go undetected.
• Alien Dictionary specifics. Adding edges from characters after the first mismatch (invents false constraints), or missing the prefix-before-itself violation (which is not a cycle).

7. Key takeaways

1. Topological sort = a schedule for a DAG. Every edge points forward in the output; it exists iff the graph is acyclic.
2. Indegree 0 = ready. Kahn's algorithm makes "no remaining prerequisites" explicit and emits ready nodes in O(V + E), iteratively.
3. Topo-sorting is cycle detection. Emitting fewer than V nodes (or hitting a back-edge in DFS) means "impossible" — that's how these problems report failure.
4. Get the edge direction right, include every node. Dependencies point to the dependent; disconnected and unconstrained nodes still appear exactly once.
5. The hard part is often modeling, not sorting. Course Schedule II hands you the graph; Alien Dictionary makes you derive it from comparisons. Once the edges exist, the same O(V + E) machinery finishes the job — which is exactly why interviewers reach for this family.