A deploy playbook lists four jobs in YAML: start the worker, migrate the schema, write config, start the API. The runner executes the file top to bottom. The worker boots, opens a client, and dies because the API is not listening and the schema is still last week’s. Nobody “chose a slow graph algorithm.” They treated a partial order — migrate before API, config before API, API before worker — as if the list were already a legal sequence.
Topological sort emits a vertex only after every predecessor has been emitted. Two procedures compute that linear extension of a DAG: Kahn (indegree plus a queue of ready vertices) and DFS on a DAG (record finish times, then reverse). Leftover vertices — you cannot emit n names — mean a cycle, not a reason to invent a third sort.
This post is those two procedures. Families and the catalog live on the Algorithms Roadmap. The layout is a directed graph; adjacency list vs matrix lives on Graphs. It is not a build-tool tutorial, not 3-color cycle detection, and not a reason to hand-roll Maven.
The DAG is the invariant
An edge u → v means u before v: do the migrate before the API, compile the library before the service. Vertices plus those precedence edges are a directed acyclic graph. A topological order is any list that respects every edge. If two jobs do not constrain each other, either may come first. There can be many legal orders; the algorithm owes you one, not uniqueness.
The representation is already chosen. Neighbor iteration on an adjacency list is the hot path; this post reads neighbors(u) and does not re-pick list vs matrix.
An undirected friendship graph has no “before.” Topological sort is a directed job. A cycle — api → worker → migrate → api — has no linear extension. The procedure must fail closed, not invent an order.
Note: “Sort” here is not comparison sort. You are not ranking keys. You are lining up a partial order. Collections.sort on job names is alphabetical, which is how the worker started first.
Kahn: indegree, then a queue of zeros
Count incoming edges. A vertex with indegree 0 has no unfinished predecessor — it is legal to run now. Keep those ready vertices in a queue (ArrayDeque). Emit the front, decrement each successor’s indegree, and enqueue anyone who just hit zero. Repeat until the queue is empty.
jobs and precedence (u → v means u before v):
config → api
migrate → api
migrate → worker
api → worker
indegree: config 0, migrate 0, api 2, worker 2
ready: config, migrateAny zero is a legal next. The queue among ties is one valid extension, not the only one.
emit config api indeg 1 ready: migrate
emit migrate api indeg 0, worker 1 enqueue api ready: api
emit api worker indeg 0 enqueue worker ready: worker
emit worker done
order: config, migrate, api, workerFour vertices, four emits. Every edge points left-to-right in the list. Swap the first two zeros and migrate, config, api, worker is equally legal.
If the YAML had also said worker → migrate, migrate’s indegree starts at 1 and never hits 0. You emit config, the queue drains, and order.size() is not n. Leftover vertices are a cycle — the proof and the color/parent walk live in Cycle Detection, not here. Kahn’s contract is: emit n names or refuse.
Note: Do not scan the whole vertex set for the next zero on every step. That is O(n²) on a graph you already paid O(n + m) to index. The queue is the ready set; decrement-and-enqueue is the whole update.
DFS on a DAG: reverse finish times
The other linear extension uses the walk, not a ready queue. DFS from each unvisited vertex: recurse on outgoing neighbors, then record that you finished u. When every vertex has a finish time, reverse that list. A vertex finishes only after its descendants; reversing puts predecessors first.
Same four jobs. Start at config:
dfs(config)
dfs(api)
dfs(worker) worker has no unseen successors → finish worker
finish api
finish config
dfs(migrate) api and worker already seen → finish migrate
finish order: worker, api, config, migrate
reversed: migrate, config, api, workerAlso a valid topological order. Different start vertex, different list, same edges respected.
This sketch assumes a DAG. Mark-seen-on-entry and skip: on a cycle the recursion returns, and you may emit a wrong order instead of failing. The state that proves a back edge (“I met u while I was still on the stack”) is cycle detection. Kahn’s leftover count is the check you can ship without that walk. Use DFS topo when the graph is already a DAG, or after you have split / rejected cycles.
Note: Recursion depth is the longest path. A chain of 10,000 jobs can blow the stack; an explicit stack is the same DFS, owned by the DFS post. Topological sort does not need a new walk.
Java sketch
Kahn first. Build indegree from the adjacency list, seed ArrayDeque with zeros, emit and decrement. Vertices that appear only as targets still need an indegree slot.
static List<String> kahn(Map<String, List<String>> adj) {
Map<String, Integer> indeg = new HashMap<>();
for (String u : adj.keySet()) {
indeg.putIfAbsent(u, 0);
for (String v : adj.get(u)) {
indeg.putIfAbsent(v, 0);
indeg.merge(v, 1, Integer::sum);
}
}
ArrayDeque<String> ready = new ArrayDeque<>();
for (var e : indeg.entrySet()) {
if (e.getValue() == 0) {
ready.add(e.getKey());
}
}
List<String> order = new ArrayList<>();
while (!ready.isEmpty()) {
String u = ready.removeFirst();
order.add(u);
for (String v : adj.getOrDefault(u, List.of())) {
if (indeg.merge(v, -1, Integer::sum) == 0) {
ready.add(v);
}
}
}
if (order.size() != indeg.size()) {
throw new IllegalStateException("cycle: leftover vertices");
}
return order;
}HashMap iteration order among the initial zeros is not a stability promise. If the product needs a deterministic tie-break, sort the seed (name, id, file order) before the first enqueue. The algorithm stays Kahn.
DFS reverse finish, DAG only:
static List<String> topoDfs(Map<String, List<String>> adj) {
Set<String> verts = new LinkedHashSet<>(adj.keySet());
for (List<String> ns : adj.values()) {
verts.addAll(ns);
}
Set<String> seen = new HashSet<>();
List<String> finish = new ArrayList<>();
for (String u : verts) {
dfsFinish(u, adj, seen, finish);
}
Collections.reverse(finish);
return finish;
}
static void dfsFinish(String u, Map<String, List<String>> adj,
Set<String> seen, List<String> finish) {
if (!seen.add(u)) {
return;
}
for (String v : adj.getOrDefault(u, List.of())) {
dfsFinish(v, adj, seen, finish);
}
finish.add(u);
}Do not call topoDfs on a graph that might contain a cycle and then trust the list. Prefer Kahn when you must fail closed. Prefer DFS when you already have a walk and the DAG invariant is the caller’s job.
Complexity
Let n be vertices, m directed edges. Glossary for Big-O lives on the Algorithms Roadmap.
| Kahn time | O(n + m) — each vertex enqueued once, each edge decrements once |
| DFS time | O(n + m) — each vertex and edge in the walk once |
| Extra space | Indegree map + ready queue, or seen + finish list (+ recursion depth) |
| Output | One linear extension, not a unique sort |
If you re-scan all remaining vertices for indegree 0 after every emit, you paid quadratic for a queue you already imported. If the graph is a dense matrix, neighbor iteration is a row scan; the procedure is unchanged, the layout bill is the Graphs post.
When not to hand-roll this
Skip a custom topological sort when:
- The tool already orders the DAG. Maven/Gradle modules, Airflow
depends_on, Terraform references, a CIneeds:graph. Re-implementing the scheduler inside the app is the wrong system boundary. - There is no precedence. A FIFO of incoming tickets is a queue. Alphabetical
List.sortis not a hidden topo. - You need a path, not an order. Unweighted shortest path is BFS. Non-negative weights are Dijkstra. Topological order among all vertices is a different question.
- The graph is undirected, or cyclic on purpose. Mutual edges are not “two jobs.” Strongly connected pieces collapse to a DAG in a later post; this one does not Union-Find a cycle away.
Do not emit a partial list and call it done when order.size() < n. That leftover is the cycle. Detect it; do not start the worker and hope.
Also skip it when a single total order already exists: one pipeline stage, one thread, one blocking call after another with no fan-in. A two-node “migrate then API” is a list. Four nodes with a diamond is a DAG.
JDK: a queue of zeros, not a TopologicalSort class
There is no java.util.TopologicalSort. The library pieces are:
- Ready set:
ArrayDequeas a queue - Indegree:
HashMap(or anint[]if vertices are0 … n-1) - DFS finish list: recursion or the explicit stack from DFS
- Fail closed:
order.size() == n, else a cycle
Prefer the orchestrator’s depends_on when the jobs already live there. Reach for the sketch when the DAG is yours — codegen order, package install, a test that must run after fixtures — and the runtime will not order it for you.
Do not use PriorityQueue unless the product asked for a priority among ready jobs. Kahn’s ready set is FIFO among zeros; a heap changes which legal extension you get, and it is not required for correctness. Do not Union-Find vertices; that layout answers “same component,” not “before.”
Cheat sheet
Job: linear order of a DAG (u → v means u before v)
Invariant: emit u only after every predecessor of u
Kahn: indegree[]; queue of zeros; emit, decrement, enqueue new zeros
DFS: walk; record finish; reverse the finish list (DAG only)
Cycle: cannot emit n vertices (Kahn leftovers) → cycle detection post
Time: O(n + m); extra space the ready/seen structures, not n²
Not unique: any zero-indegree vertex is a legal next
JDK: ArrayDeque + HashMap; no TopologicalSort class
Do not: List.sort names; ignore leftovers; Union-Find; 3-color hereDo:
- Store precedence as a directed adjacency list, then run Kahn or DFS.
- Fail if you cannot emit
nvertices; leftover is a cycle. - Use
ArrayDequefor Kahn’s ready zeros, notArrayList.remove(0).
Don’t:
- Run the YAML list as if it were already a topo.
- Treat DFS reverse-finish as a cycle prover — that walk is the next post.
- Hand-roll Maven, Airflow, or Terraform’s graph.
- Call this a sort of keys; it is a linear extension of a partial order.
Wrap-up
Topological sort is the procedure that turns “this before that” into a run list. Kahn keeps indegree and a queue of zeros. DFS on a DAG records finish times and reverses them. Either emits a vertex only after its predecessors. If you cannot emit n names, the graph is not a DAG — stop, and take the cycle to the detection post. The JDK gives you ArrayDeque and a map, not a scheduler. Hand-roll it when the DAG is the assignment. Otherwise let the tool that already owns depends_on order the work.