Topological Sort Template — Kahn's Algorithm and DFS Post-Order, Three Walkthroughs

Topological sort answers a single question: given a set of tasks with dependencies, in what order can I do them so every prerequisite comes first? The graph part is trivial once you name it — the interview subtlety is which of the two canonical algorithms (Kahn's or DFS post-order) to pick, and how each detects cycles for free.

Recognition — when to reach for it

Topological sort is the right tool when all three of these hold:

1. Elements have dependencies — task A must finish before task B, prerequisite → course, byte order alphabet ordering.
2. The dependency graph is a DAG — directed and (hopefully) acyclic. If a cycle exists, topological sort's failure signals the cycle for free.
3. You need a valid linear order consistent with all dependencies. Sometimes any order works; sometimes lexicographically smallest; sometimes just "does one exist?".

The classic problems: LC 207 Course Schedule (does an order exist?), LC 210 Course Schedule II (return an order), LC 269 Alien Dictionary (derive the dependencies from data, then sort), LC 269-family "build system" or "task scheduler" problems.

Mental model — a dependency graph and two ways to drain it

Model the problem as a directed graph. Nodes are tasks; an edge A → B means "A must complete before B". A valid topological order is any linear arrangement where every edge points forward.

Two canonical algorithms drain the graph in that order:

• Kahn's algorithm (BFS). Repeatedly emit a node with zero incoming dependencies, and decrement the in-degree of its successors. If some nodes never reach zero in-degree, there's a cycle among them.
• DFS post-order. Depth-first from each unvisited node; emit a node when you finish processing its subtree. Reverse the emit order for the topological order. Track "currently on the recursion stack" to detect cycles as back-edges.

Both are O(V + E), both detect cycles, both produce a valid order. The choice depends on what you need (any order, lexicographic order, does-one-exist) and which algorithm's shape reads more naturally for the problem.

Kahn's algorithm

from collections import defaultdict, deque

def topological_sort_kahn(n: int, edges: list[tuple[int, int]]) -> list[int]:
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:                 # edge u → v : u before v
        graph[u].append(v)
        in_degree[v] += 1

    queue = deque(i for i in range(n) if in_degree[i] == 0)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)

    if len(order) < n:
        return []                      # cycle — no valid order exists
    return order

Two things worth naming out loud:

• Cycle detection is free. If the queue drains before every node has been emitted, some nodes must be locked in a cycle where in-degree never reaches zero. len(order) < n is the check.
• Any lexicographic tweak is easy. Swap the deque for a heapq if you want the lexicographically smallest topological order — heappop returns the smallest zero-in-degree node instead of the earliest-enqueued one. O(V log V + E) instead of O(V + E).

DFS post-order

from collections import defaultdict

def topological_sort_dfs(n: int, edges: list[tuple[int, int]]) -> list[int]:
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)

    WHITE, GREY, BLACK = 0, 1, 2
    colour = [WHITE] * n
    order = []
    has_cycle = False

    def dfs(u):
        nonlocal has_cycle
        colour[u] = GREY               # currently on the recursion stack
        for v in graph[u]:
            if colour[v] == GREY:      # back-edge — cycle
                has_cycle = True
            elif colour[v] == WHITE:
                dfs(v)
        colour[u] = BLACK              # done
        order.append(u)                # emit on finish

    for i in range(n):
        if colour[i] == WHITE:
            dfs(i)

    if has_cycle:
        return []
    return order[::-1]                 # reverse post-order

Two things worth naming out loud:

• The three-colour marker (WHITE / GREY / BLACK) is what makes cycle detection work. GREY means "on the current recursion stack"; a GREY neighbour is a back-edge, and back-edges mean cycles. BLACK means "already fully processed, safe to reach". WHITE means "not yet visited".
• Emit on finish, then reverse. Post-order emit gives you a reverse topological order — every emitted node has all its dependents already emitted. Reversing at the end flips this to the natural "prerequisites first" order.

Which one to pick

Both are asymptotically equivalent (O(V + E) time, O(V) space). Kahn's tends to read more naturally for "scheduling" problems (courses, tasks, build system); DFS post-order tends to read more naturally when the problem is graph-theoretic (find the cycle, order strongly connected components).

Walkthrough 1 — LeetCode 207, Course Schedule

There are numCourses courses labelled 0..numCourses-1. Some have prerequisites given as [a, b] pairs (must take b before a). Return true iff you can finish all courses.

Recognition. DAG feasibility check ✓. The question is just "does a topological order exist?" — Kahn's is a natural fit because "in-degree reaches zero" reads exactly as "no unmet prerequisites left".

def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    from collections import defaultdict, deque
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:         # b → a
        graph[b].append(a)
        in_degree[a] += 1

    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    finished = 0
    while queue:
        node = queue.popleft()
        finished += 1
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)

    return finished == numCourses

We don't even need to build the order list — a running counter is enough. Cycle detection is finished < numCourses.

Walkthrough 2 — LeetCode 210, Course Schedule II

Same setup, but return a valid course order (any works).

Same algorithm, now we keep the order list. If the graph has a cycle, return an empty list per the problem convention.

def findOrder(numCourses: int, prerequisites: list[list[int]]) -> list[int]:
    from collections import defaultdict, deque
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1

    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)

    return order if len(order) == numCourses else []

Same 15 lines as LC 207, one extra list.

Walkthrough 3 — LeetCode 269, Alien Dictionary

A list of words is sorted lexicographically by some alien alphabet. Return the alphabet order, or "" if impossible.

Two subtleties:

1. Derive the edges from the input. Compare adjacent words character by character; the first differing character gives one edge (smaller → larger).
2. Handle the invalid prefix case. If word A is a prefix of word B but appears after it (e.g. ["abc", "ab"]), no valid alphabet exists.

Once the graph is built, topological sort — either algorithm — gives the answer.

def alienOrder(words: list[str]) -> str:
    from collections import defaultdict, deque

    graph = defaultdict(set)
    in_degree = {c: 0 for w in words for c in w}

    for a, b in zip(words, words[1:]):
        # Prefix-order violation: longer word first with shorter as prefix
        if len(a) > len(b) and a.startswith(b):
            return ""
        for ca, cb in zip(a, b):
            if ca != cb:
                if cb not in graph[ca]:
                    graph[ca].add(cb)
                    in_degree[cb] += 1
                break

    queue = deque(c for c in in_degree if in_degree[c] == 0)
    order = []
    while queue:
        c = queue.popleft()
        order.append(c)
        for nxt in graph[c]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)

    return "".join(order) if len(order) == len(in_degree) else ""

Notice we use graph[ca].add(cb) guarded by "not in" so we don't double-count edges. Missing that dedup bug turns cycle detection into false positives.

Common bugs

• Not deduplicating edges. Multiple prerequisites entries specifying the same edge inflate in_degree, and a node may never reach zero. Use set or check before decrementing.
• Cycle detection via "did we visit everything?" without initialising in-degrees for nodes without edges. A disconnected node has in-degree 0 and belongs in the initial queue; forgetting to enumerate all nodes drops them from the output.
• Confusing edge direction. For prerequisites, the natural direction is "b before a" → edge b → a. Flipping this reverses the topological order.
• DFS post-order without reversal. Emit-on-finish gives you reverse topological order. Forgetting to [::-1] at the end returns the exact opposite of the intended answer.
• Path compression in three-colour DFS. The GREY marker only makes sense during the recursive descent from a single root; if you use it as "any not-BLACK", you'll miss cycles that span multiple traversal starts.

When topological sort is not the tool

• The graph has a cycle by design. Circular dependencies mean no valid order exists. If cycles are OK and you just want to visit everything, plain BFS or DFS is enough.
• Weighted longest-path problems. Topological sort orders nodes; it doesn't tell you the longest path. Use DAG-DP: topologically sort first, then relax edges in that order. LC 329 Longest Increasing Path in a Matrix does exactly this.
• Small graphs with clear structure. LC 621 Task Scheduler doesn't need topological sort at all; a greedy heap approach is cleaner.
• You need transitive closure, not one order. Warshall's or successive BFS.

How the Algotrek tutor would prompt you here

When a learner opens a topological-sort problem on Algotrek, the tutor doesn't reveal the template. It asks three questions:

1. "Name the nodes and the direction of the edge." Course → prerequisite? Task → dependency? Character → predecessor? Getting the arrow the right way round is where 30% of first attempts fail.
2. "Does a cycle possibility change your answer?" If yes, you need cycle detection built in — both algorithms have it. If no, you can lean on the assumption and save five lines.
3. "Do you need any valid order, the lexicographically smallest, or just a yes/no?" Any → Kahn's or DFS. Smallest → Kahn's with a heap. Yes/no → Kahn's with a counter, no order list needed.

Answer all three and the template picks itself. Try the Course Schedule lesson on Algotrek to see the prompt-then-reveal flow on the friendliest topological-sort problem.

Where to go next

• LC 329, Longest Increasing Path in a Matrix. DAG-DP on the implicit graph "cell → any smaller neighbour". Topological sort by cell value, then linear-time DP.
• LC 802, Find Eventual Safe States. Reverse topological sort on a graph — nodes are "safe" iff every path from them terminates. A twist on cycle detection.
• LC 1857, Largest Colour Value in a Directed Graph. Topological sort + DP per colour. Excellent grade-yourself problem after LC 329.
• Tarjan's or Kosaraju's SCC algorithms. Once you own topological sort, strongly connected components are the natural next graph algorithm.

Cross-reference the BFS vs DFS post — Kahn's is BFS-flavoured, DFS post-order is DFS-flavoured, and picking between them is exactly the same "which invariant do I need?" decision. Cross-reference the union-find post — union-find handles undirected connectivity; topological sort handles directed ordering. Together they cover most graph interview problems below the shortest-path tier.

For the O(V + E) accounting both algorithms share, see the Big-O cheat sheet. For the defaultdict and deque idioms used above, see the Python interview cheat sheet.