vizlearn
Home / Algorithms

Topological Sort

Algorithms & Data StructuresBy Updated

Order tasks so every prerequisite comes before whatever depends on it. Build systems, course planners and package managers all run this — and it is also how they detect a circular dependency.

Controls

compute in-degree of all queue = nodes with in-degree 0 while queue: n = queue.pop() output(n) for m in neighbours(n): indeg[m] -= 1 if indeg[m] == 0: queue.add(m)

Kahn's Algorithm

step 0
Output order

Insight

A node can only be output once every arrow pointing into it has been satisfied — that count is its in-degree.

In-degrees
ready queue–
output0

Complexity

Time O(V+E)
Space O(V)
Needs a DAG yes

Overview

Represent each task as a vertex and draw an edge from a prerequisite to the task that needs it. For example, if A must precede B and A must precede C, both A, B, C and A, C, B are valid orders. A topological ordering is often not unique.

Dependencies as a directed graph

The graph must be a DAG: a directed acyclic graph. If A depends on B while B depends on A, each waits for the other, so no ordering can satisfy both.

Kahn’s algorithm

Kahn’s algorithm tracks each vertex’s in-degree, the number of prerequisites still remaining. Add all zero-in-degree vertices to a queue. Repeatedly remove one, append it to the order, and reduce the in-degree of each dependent vertex. Whenever a count reaches zero, that task is ready to be queued.

Choose Dependency graph in the visualizer and compare Build pipeline or Course prerequisites with Circular dependency. In the cyclic case, some nodes remain after the queue empties. Those nodes belong to or depend on a cycle; the incomplete output signals that no full ordering was found.

Worked example

Suppose the dependencies are A → C, B → C, and C → D. Initially, A and B have in-degree zero. Output A and B in either order; after both edges to C are removed, C becomes ready. Output C, then D. The order preserves every prerequisite edge.

Cost and common mistakes

With adjacency lists, the algorithm takes O(V + E) time and O(V + E) space for the graph and queue. Each vertex is added and removed once, and each edge is processed once.

  • Reversing edge direction: choose a convention and keep it consistent; this article uses prerequisite → dependent.
  • Assuming there is one answer: independent tasks can appear in multiple valid orders.
  • Treating a partial result as complete: fewer output vertices than input vertices means a cycle prevents completion.
  • Confusing the queue order with priority: Kahn’s algorithm can use a priority queue to choose among ready tasks when a deterministic or lexicographically smallest order is needed.

Sources and next steps

Run it in Python

Kahn's algorithm on a small course-prerequisite graph, printing the in-degree table as it drains. The final block adds one edge that closes a cycle, which is how the same code detects that no ordering exists.

topological_sort.pyPython 3
Output
How the code works
  1. indegree = {n: len(deps) for n, deps in prereqs.items()}How many prerequisites each node is still waiting on. The algorithm is nothing but keeping this table correct as nodes are removed.
  2. dependents[d].append(node)The graph reversed. The input says “what does this need”; the loop needs “what is unblocked when this is done”, and building both is cheaper than searching one repeatedly.
  3. ready = deque(... if deg == 0)Everything with no prerequisites can start immediately, and in any order. A graph usually has many valid topological orders, not one.
  4. indegree[dependent] -= 1Decrement, never recompute. Each edge is looked at exactly once across the whole run, which is what makes this O(V + E).
  5. if len(order) != len(prereqs):The cycle test, and it is free. Nodes in a cycle always wait on each other, so their in-degree never reaches zero and they never enter the queue — a short output is the detection.
Change one thing
  • Swap popleft() for pop(). A different, equally valid order comes out — useful proof that the answer is not unique.
  • Use a heapq instead of a deque to get the lexicographically smallest valid order. That is the usual “deterministic build order” requirement.
  • Add a node with a prerequisite on itself. In-degree 1 forever, and it shows up in the stuck list immediately.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.




Predict, then reveal
About to run: switch Dependency graph to Circular dependency. Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
  1. Kahn's algorithm starts from the nodes whose in-degree is:
  2. The program detects a cycle by noticing that:
  3. A directed acyclic graph has:





 Cheat sheet
Topological Sort
Order a directed graph so every edge points forward, and detect when a cycle makes that ordering impossible.
ALGORITHMS · vizlearn.in/dsa/topological_sort.html
More in Algorithms
AlgorithmsDijkstra's AlgorithmAlgorithmsBellman-Ford and Negative WeightsAlgorithmsA* Pathfinding AlgorithmAlgorithmsMinimum Spanning Tree
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact