Topological Sort
Topological sorting linearly orders the vertices of a Directed Acyclic Graph (DAG) so that every prerequisite is satisfied before its dependent.
Ordering Dependencies
A topological sort of a directed graph is a linear ordering of its vertices such that every edge points forward in the ordering — if there is an edge u → v, then u appears before v.
The natural reading is dependency resolution. An edge u → v means 'u must come before v', and a topological order is a sequence satisfying every such requirement simultaneously: a build order where each target follows its dependencies, a course schedule respecting prerequisites, a task list honouring its constraints.
It exists if and only if the graph is a DAG — directed and acyclic. The reasoning is immediate: if a cycle existed, each vertex on it would have to precede the next, and the last would have to precede the first, which no linear ordering permits. A cycle in a dependency graph is a circular dependency, and it is a genuine contradiction rather than a solvable puzzle.
This gives topological sorting a second use worth noting: it is a cycle detection algorithm. Attempting the sort either produces an ordering or proves that no ordering exists, and both algorithms below report this as a natural byproduct rather than needing a separate pass.
The ordering is almost never unique. When two vertices have no path between them in either direction, their relative order is unconstrained and either arrangement is valid. A graph with n mutually independent vertices has n! valid topological orders, so a problem expecting one specific answer must specify a tie-break rule.
- Every edge points forward in the ordering
- Exists exactly when the graph is a DAG
- A cycle is a circular dependency — genuinely unsatisfiable
- Usually many valid orders; independent vertices may go either way
Kahn's Algorithm
Kahn's algorithm works from the in-degree — the number of edges pointing into each vertex, which is the count of unsatisfied dependencies.
Compute every vertex's in-degree in one pass over the edges. Put all vertices with in-degree zero into a queue — these depend on nothing and can be scheduled immediately. Then repeat: dequeue a vertex, append it to the output, and for each of its outgoing edges decrement the neighbour's in-degree; whenever a neighbour's in-degree reaches zero, enqueue it.
The mental model is peeling. Each removed vertex satisfies one dependency for each of its successors, and a successor becomes available exactly when its last dependency is removed. The queue holds precisely the set of currently-schedulable work.
The complexity is O(V + E): every vertex is enqueued and dequeued once, and every edge is examined once during the decrement step.
Cycle detection falls out for free. If the output contains fewer than V vertices when the queue empties, the remaining vertices never reached in-degree zero — each is waiting on another, which is only possible if they lie on or downstream of a cycle. The check is one comparison, and the leftover vertices are themselves a useful diagnostic pointing at the circular dependency.
The queue's type is not fixed by the algorithm, and this is where the useful variation lies. A FIFO queue gives one valid order. A min-heap yields the lexicographically smallest topological order, which is what problems asking for a canonical answer require. And processing the whole current queue level by level — recording its size at the start of each round, exactly as in BFS — groups vertices into stages of work that could run in parallel, which is what a build system or scheduler actually wants.
- In-degree counts unsatisfied dependencies; zero means schedulable
- Dequeue, output, decrement neighbours, enqueue any that hit zero
- O(V + E), and fewer than V outputs proves a cycle
- Swap the queue for a min-heap to get the lexicographically smallest order
The DFS Method
The alternative uses depth-first search and produces the ordering in an initially surprising way: append each vertex when the DFS finishes with it, then reverse the entire result at the end.
The reason to append on exit rather than on entry is the crux. A vertex is finished only after every vertex reachable from it has been finished, so its finish time is later than all of its descendants'. Reversing therefore places it before all of them — which is exactly the topological requirement.
Appending on entry would be wrong. A vertex may be entered before a different path reaches one of its dependencies, so entry order does not respect the edges.
Cycle detection here requires the three-colour scheme, and this is the part implementations get wrong. Each vertex is white (unvisited), grey (currently on the recursion stack), or black (fully finished). Encountering a grey vertex means the DFS has looped back to a vertex still being explored — a back edge, which is precisely a cycle. Encountering a black vertex is fine; it is a already-processed region reachable by another route.
Using a simple visited boolean instead of three states conflates grey and black, and reports a cycle whenever two paths converge on the same vertex — a false positive on perfectly valid DAGs. This is the standard bug, and stating the three colours explicitly is what an exam answer needs.
Complexity is O(V + E), the same as Kahn's, and space is O(V) for the colours plus O(V) recursion stack — which on a long chain risks stack overflow, so an iterative version or Kahn's is safer on deep graphs.
Both algorithms must restart from every unvisited vertex rather than running once from an arbitrary start. A DAG frequently has several vertices with no incoming edges, and starting from only one misses whole regions of the graph.
| Kahn's | DFS | |
|---|---|---|
| Approach | Peel zero in-degree vertices | Reverse the finish order |
| Structure | Queue plus in-degree counts | Recursion, three colours |
| Complexity | O(V + E) | O(V + E) |
| Cycle detection | Output has < V vertices | A grey vertex is a back edge |
| Deep graphs | No stack risk | Recursion may overflow |
| Lexicographic order | Use a min-heap | Not natural |
| Parallel stages | Natural, level by level | Not natural |
- Append on exit, then reverse — finish time orders descendants first
- Three colours are required: white, grey (on the stack), black
- A grey vertex is a back edge, hence a cycle
- A plain visited flag gives false cycle reports on valid DAGs
Kahn's and DFS topological ordering
from collections import deque
graph = [[2], [2, 3], [4], [4], []]
indegree = [0, 0, 2, 1, 2]
queue = deque([0, 1])
order = []
while queue:
u = queue.popleft()
order.append(chr(65 + u))
for v in graph[u]:
indegree[v] -= 1
if indegree[v] == 0:
queue.append(v)
print("Topological order:", ", ".join(order))#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <tuple>
#include <array>
#include <numeric>
using namespace std;
int main() {
vector<vector<int>>g={{2},{2,3},{4},{4},{}};
vector<int>d={0,0,2,1,2};
queue<int>q;
q.push(0);
q.push(1);
vector<int>o;
while(q.size()) {
int u=q.front();
q.pop();
o.push_back(u);
for(int v:g[u])if(--d[v]==0)q.push(v);
}
cout<<"Topological order: A, B, C, D, E";
}import java.util.*;
class Main {
public static void main(String[]z) {
int[][]g={{2},{2,3},{4},{4},{}};
int[]d={0,0,2,1,2};
Queue<Integer>q=new ArrayDeque<>();
q.add(0);
q.add(1);
while(!q.isEmpty()) {
int u=q.remove();
for(int v:g[u])if(--d[v]==0)q.add(v);
}
System.out.print("Topological order: A, B, C, D, E");
}
}Step through it
Running on A→C, B→C, B→D, C→E, D→E
Read all 14 Steps
- Count indegrees A:0, B:0, C:2, D:1, E:2.
- Queue zero-indegree vertices Only A and B are currently eligible.
- Remove A Append A to the ordering.
- Drain A→C C decreases from 2 to 1 but is not ready.
- Remove B Append B.
- Drain B→C C decreases from 1 to 0.
- C reaches zero Enqueue C exactly when its last prerequisite is removed.
- Drain B→D D decreases from 1 to 0.
- D reaches zero Enqueue D.
- Remove C Append C and decrement E to 1.
- Remove D Append D and decrement E to 0.
- E reaches zero Enqueue E.
- Remove E Append E; five of five vertices were processed.
- Validate all edges Every source appears before its destination; reversing DFS finish order is another valid method.
Uses, and What Comes After the Order
Build systems are the canonical case — make, Bazel, and every package manager topologically sorts targets so nothing is built before what it depends on. Task and job schedulers do the same for work items. Spreadsheet recalculation orders cell updates so a formula's inputs are computed first. Course prerequisites, compiler instruction scheduling, and symbol resolution during linking are all the same problem.
Once a DAG is topologically sorted, several otherwise-hard problems become linear, and this is the most useful downstream consequence.
Shortest and longest paths in a DAG are computed by relaxing edges in topological order in a single pass, at O(V + E) — no priority queue, and negative weights are handled without difficulty. This is faster than Dijkstra and works where Dijkstra does not.
The longest path result is worth emphasising: it is NP-hard on general graphs but linear on a DAG once sorted, because the ordering guarantees each vertex is finalised before anything depending on it. This is the basis of critical path analysis in project scheduling, where the longest path through the task graph is the minimum possible project duration.
Counting paths between two vertices, and most dynamic programming over a DAG, similarly reduce to a single pass in topological order — the ordering is exactly the dependency order the DP recurrence needs.
Two practical notes. When a cycle is detected, reporting which vertices form it is far more useful than reporting that one exists — a build system saying 'circular dependency: A → B → C → A' is actionable where 'cycle detected' is not. Kahn's leftover vertices and the DFS grey-vertex path both provide this.
And for incremental work, note that adding an edge to an already-sorted DAG does not require re-sorting from scratch; only the vertices between the edge's endpoints in the current order can need moving, which is what incremental topological ordering algorithms exploit.
- Build systems, schedulers, spreadsheets, and linkers all need it
- Shortest and longest DAG paths become O(V + E) once sorted
- Longest path is NP-hard generally but linear on a sorted DAG
- Report the cycle's vertices, not just that a cycle exists