What you'll learn

  1. Quick answer
  2. The problem
  3. Kahn's algorithm
  4. Cycle detection comes free
  5. The DFS alternative
  6. Where it is actually used
  7. FAQ

Quick Answer

A topological sort orders the nodes of a directed graph so every edge points forward. Kahn's algorithm repeatedly takes nodes with no remaining prerequisites. If it cannot place every node, the graph contains a cycle.

The problem

You want to study machine learning. It requires maths. Data structures requires Python. Machine learning also requires data structures. In what order do you take them?

The dependencies form a directed graph, and you need an ordering where every prerequisite comes before the thing needing it. That is a topological sort.

Two things are worth noting at the outset. There is usually more than one valid answer — any order respecting the constraints is correct. And sometimes there is no answer at all, which is the case the algorithm must handle rather than loop forever on.

Kahn's algorithm

Count how many prerequisites each node has — its in-degree. Anything with zero can be done immediately. Do it, remove it, and decrement its dependants. Repeat.

from collections import deque, defaultdict

def topo(nodes, edges):
    g = defaultdict(list)
    indeg = {n: 0 for n in nodes}
    for u, v in edges:
        g[u].append(v)
        indeg[v] += 1

    q = deque([n for n in nodes if indeg[n] == 0])
    out = []
    while q:
        u = q.popleft()
        out.append(u)
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)

    return out if len(out) == len(nodes) else None
topo(['maths','dsa','ml','python'],
     [('maths','ml'), ('python','dsa'), ('dsa','ml')])
# ['maths', 'python', 'dsa', 'ml']

Maths and Python both start with no prerequisites, so either could come first. ML comes last because it waits for both maths and DSA.

Cycle detection comes free

The final line is the part worth understanding:

return out if len(out) == len(nodes) else None
topo(['a','b'], [('a','b'), ('b','a')])
# None

If A requires B and B requires A, neither ever reaches in-degree zero. The queue empties with nodes left unplaced, and the output is shorter than the input.

So the algorithm does not need a separate cycle check — failing to place every node is the cycle detection. This is why topological sort is the standard answer to "detect a cycle in a directed graph", and why build tools report circular dependency errors: they ran this and it came up short.

A graph that can be topologically sorted is called a DAG — a directed acyclic graph. That term appears constantly in build systems, data pipelines and scheduling.

The DFS alternative

There is a second approach worth knowing. Run depth-first search, and after fully exploring a node's descendants, push it onto a stack. Reversing the stack gives a topological order.

The intuition is that a node is only finished once everything it depends on has been finished, so finishing order reversed is dependency order.

Cycle detection in the DFS version needs explicit work: track nodes currently on the recursion stack, and encountering one again means a cycle. That is more fiddly than Kahn's length check, which is why Kahn's is usually the easier one to write correctly under interview pressure.

Kahn's also has a practical advantage: nodes with in-degree zero at the same moment can be processed in parallel, which is exactly how build systems decide what to compile simultaneously.

Where it is actually used

  • Build systems. Compiling files in dependency order, and detecting circular imports.
  • Package managers. Installing dependencies before dependants. A circular dependency error is a failed topological sort.
  • Task and job schedulers. Data pipeline tools describe work as a DAG explicitly for this reason.
  • Spreadsheet recalculation. Cells depend on other cells, and a circular reference warning is the same detection.
  • Course planning — the textbook example, and a real one.

In interviews it appears as course schedule problems, build order, or alien dictionary ordering. The signal is any wording about prerequisites, dependencies or ordering constraints.

For undirected connectivity questions, union-find is the tool instead — topological sort needs direction to be meaningful.

Frequently Asked Questions

Is there only one correct topological order? Usually not. Any ordering that respects every dependency is valid, and graphs with independent branches have many. Interview answers are normally checked for validity rather than for an exact sequence.
How does topological sort detect cycles? Nodes in a cycle never reach in-degree zero, so they are never queued. If the output contains fewer nodes than the input, a cycle exists.
What is a DAG? A directed acyclic graph — directed edges with no cycles. Exactly the graphs that can be topologically sorted, which is why build systems and data pipelines describe work that way.
Kahn's algorithm or DFS? Kahn's is usually easier to write correctly because cycle detection is a simple length comparison. It also naturally identifies work that can proceed in parallel, which DFS does not.
What is the time complexity? O(V + E) — every node is queued once and every edge is examined once when decrementing in-degrees.