Topological Sorting

DSA, Database System & Operating System — Sorting, Searching, and Graphs, NEC licence examination syllabus (Nepal Engineering Council).

Topological Sorting: ordering tasks that depend on each other

Every build system, every task scheduler with dependencies, solves exactly this problem.

Topological sort only works on a DAG (Directed Acyclic Graph — no cycles) — it produces an ordering of vertices such that for every directed edge u→v, u appears BEFORE v in the ordering. Real example: "compile file B before file A" dependencies in a build system.

🔄 Two Approaches

DFS-basedRun DFS, and add each vertex to the front of the result list the moment DFS finishes exploring all its descendants.

BFS-based (Kahn's algorithm)Repeatedly remove vertices that currently have zero incoming edges, adding them to the result, and reducing their neighbours' incoming-edge counts.

💡 One-liner: "Why must the graph be acyclic for topological sorting to work?" → A cycle would create a contradiction — vertex A must come before B, B before C, but C before A too, which is logically impossible to satisfy.

Kahn's algorithm, traced

Take a dependency graph: A→C, B→C, C→D, C→E, D→F, E→F.

Step 1 — count incoming edges for each vertex: A: 0 B: 0 C: 2 D: 1 E: 1 F: 2 Step 2 — repeatedly take a vertex with in-degree 0: queue [A, B] take A → C drops to 1 order: A queue [B] take B → C drops to 0, enqueue C order: A B queue [C] take C → D and E drop to 0 order: A B C queue [D, E] take D → F drops to 1 order: A B C D queue [E] take E → F drops to 0, enqueue F order: A B C D E queue [F] take F order: A B C D E F Check: every edge runs forwards in that order ✓

In-degree zero means "nothing is waiting on this" — every prerequisite is already done, so the task can run now. Removing a vertex means finishing that task, which is why its dependents' counts drop.

How a cycle announces itself

The algorithm does more than fail on a cyclic graph — it detects the cycle, which is often the actual point of running it.

🔁 The termination test

All vertices outputThe graph is acyclic and the ordering is valid.

Queue empties earlyEvery remaining vertex still has an incoming edge, so they are waiting on each other — that is a cycle, and the remaining vertices are the ones involved in it.

💡 This is exactly how a build system reports a circular dependency, and how a package manager detects that two packages require each other. The topological sort is run to find the cycle at least as often as to produce an order.

Why the answer is usually not unique

In the trace above, A and B both start with in-degree zero, so B A C D E F is equally valid. Any vertex with no unmet dependencies may go next.

A topological sort is unique only when exactly one vertex has in-degree zero at every step — which means the graph is a single chain. Otherwise several orderings satisfy the constraints, and an exam question asking for "a" topological order will accept any of them.

💡 Both approaches cost O(V + E): each vertex is processed once and each edge examined once. Kahn's is usually easier to trace by hand because the in-degree table makes the state visible, while the DFS version relies on the order in which recursive calls finish.

Syllabus points

Depth-first topological sort
Breadth-first topological sort

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.