Topological Sort & Cycle Detection — Data Structures Course

What you'll learn

Some tasks must happen before others — course prerequisites, build steps, spreadsheet formulas. A topological sort orders the vertices of a directed acyclic graph so every edge points forward. If no such order exists, there's a cycle.

By the end you'll be able to:

Define a topological order on a DAG
Run Kahn's algorithm using in-degrees and a queue
Detect a cycle as a by-product

DAGs & ordering

A topological order lists the vertices so that for every edge u → v, u comes before v. It only exists for a DAG (directed acyclic graph) — a cycle would require a vertex to come before itself. There can be several valid orders.

Kahn's algorithm

Track each vertex's in-degree (incoming edges). Vertices with in-degree 0 have no unmet prerequisites, so they can go next. Remove one, decrement its neighbors, and repeat:

Kahn's algorithm (BFS-based topological sort)

Topological sort

in:0

in:2

in:1

in:2

1/14Kahn's algorithm: repeatedly remove a vertex with in-degree 0 — one with no remaining prerequisites. Badges show each in-degree.

Badges = in-degree · yellow = ready (in-degree 0) · blue = removing · green = placed in the order.

Cycle detection

Key idea

If Kahn's algorithm ends with fewer vertices in the output than the graph has, some vertices never reached in-degree 0 — they're trapped in a cycle. So topological sort is a cycle detector for directed graphs. (DFS gives an alternative: a "back edge" to a node still on the recursion stack means a cycle.)

In code

Language

toposort.py

from collections import deque

def topological_sort(graph):          # graph: node -> list of successors
    indeg = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            indeg[v] += 1
    queue = deque(u for u in graph if indeg[u] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)
    if len(order) != len(graph):
        raise ValueError("cycle detected")   # not all removed
    return order

Recap & quick check

Key takeaways

A topological order lists vertices so every edge points forward; it exists only for a DAG.
Kahn's algorithm repeatedly removes an in-degree-0 vertex and decrements its neighbors.
It runs in O(V + E) using a queue of ready vertices.
If not all vertices get output, the graph has a cycle.
Uses: build systems, task scheduling, course prerequisites, formula recalculation.

Quick check

1. A topological sort is only possible on:

2. Kahn's algorithm starts with vertices that have:

3. How does Kahn's algorithm reveal a cycle?

4. Topological sort runs in:

Ordering ignores edge weights. Next we bring weights back and find the cheapest route. Next up: Module 26 — Shortest Paths: Dijkstra & Bellman-Ford.