Prerequisites
Exams, courses or tasks requiring earlier results.
Algorithms · Directed graphs
Topological sort
If an edge u→v means “u must come before v”, a topological ordering places every vertex in a sequence that respects every dependency.
From a graph to a valid sequence
Definition. Given a directed graph G = (V, E), a topological ordering is a permutation of the vertices such that, for every edge (u, v) ∈ E, u appears before v.
A→C→D→F
The order describes constraints, not necessarily a unique timeline. If A and B are unrelated by any path, they can often swap places without invalidating the result.
Build system
Build a dependency before the module that imports it.
Scheduling
Find a feasible order; durations require further techniques.
It exists if and only if the graph is a DAG
A DAG is a directed acyclic graph. If A→B→C→A is a cycle, each vertex would have to precede itself, an impossible constraint. Conversely, every DAG contains at least one vertex with in-degree zero.
Uniqueness. The ordering is unique only if exactly one zero-in-degree vertex is available at every step. Multiple choices reveal multiple valid orderings.
Kahn’s algorithm: remove sources
- Compute every vertex’s in-degree.
- Enqueue all vertices whose in-degree is 0.
- Remove a vertex u, append it to the ordering, and “delete” its outgoing edges by decreasing its neighbours’ in-degrees.
- Every neighbour reaching degree 0 joins the queue. If vertices remain at the end, the residual edges contain a cycle.
Lab: build the order
Advance one operation at a time: node badges show residual in-degree, while dashed edges have already been removed.
Syntax: A>C, B>C, F · 2 to 10 vertices.
Examples
Queue · in-degree 0
Produced order
Residual in-degrees
Diagnosis
—
- Ordered vertices
- 0
- Removed edges
- 0
- Available choices
- 0
- Unique order?
- —
Why the algorithm is correct
Safe choice
A zero-in-degree vertex has no predecessor left to place, so it may safely be the next element.
Invariant
The output sequence respects every removed edge, and stored in-degrees exactly match the residual graph.
Certified cycle
If the queue empties while vertices remain, each has a residual predecessor. Following them in a finite set must eventually repeat a vertex, proving a cycle.
Complexity analysis
| Operation | Cost | Reason |
|---|---|---|
| Compute in-degrees | Θ(|V| + |E|) | Initialize vertices and scan all edges once. |
| Queue and removals | Θ(|V| + |E|) | Each vertex is enqueued once; each edge causes one decrement. |
| Total time | Θ(|V| + |E|) | With adjacency lists. |
| Auxiliary space | Θ(|V|) | In-degrees, queue and output; the graph itself takes Θ(|V| + |E|). |
DFS alternative and applications
DFS can colour vertices white, grey and black: an edge to a grey vertex reveals a cycle; if none exists, reverse finishing order is topological. It has the same Θ(|V| + |E|) cost, while Kahn makes available prerequisites and parallelism more explicit.
It is not a complete scheduler. Topological sorting respects precedence, but does not optimize duration, resources or the number of parallel tasks.
Common mistakes and exercises
- Applying it to an undirected graph or failing to check that the output contains every vertex.
- Assuming a DAG always has one order: try the “Many orders” preset.
- Recomputing every in-degree from scratch at each step, needlessly increasing the cost.
Before running the diamond, list every valid ordering.
Add F>B to the initial dependencies: when does Kahn detect the cycle?
How would you change the queue to always obtain the lexicographically smallest order?