Topological Sort (Kahn's Algorithm and DFS)

Intuition

A topological order lists the vertices of a directed graph so that every edge u -> v has u before v: prerequisites before courses, libraries before the code that links them. Such an order exists exactly when the graph is a DAG (directed acyclic graph). If there is a cycle, every vertex on it would have to come before itself.

Two classic ways to build one:

• Kahn's algorithm (BFS flavor). A vertex with in-degree 0 has no unmet prerequisites, so it can go first. Output it, delete its outgoing edges (decrement the in-degree of its targets), and repeat. If you get stuck before outputting all n vertices, every remaining vertex still has an incoming edge from another remaining vertex, so the remainder contains a cycle.
• DFS (finishing order). In a DFS, a vertex finishes only after everything reachable from it has finished. Reversing the finishing order therefore puts every vertex before its descendants.

Every DAG has at least one source (in-degree 0) and one sink (out-degree 0). Once you have an order, any "best path" question becomes a one-pass DP: process vertices in topological order and push values along out-edges. That gives longest paths, shortest paths (even with negative weights) and path counts in O(n + m).

When to use it in interviews / OAs

• Prerequisites, dependencies, build or install order, task scheduling: "can all courses be finished?", "return a valid order".
• Deriving an order from comparisons: alien dictionary, sequence reconstruction.
• "Minimum number of semesters / rounds" with unlimited parallelism: count the layers of Kahn's algorithm.
• Earliest finish time when tasks have durations (critical path): DP in topological order.
• Longest path or number of paths in a DAG, including implicit DAGs such as "longest increasing path in a matrix" (edges go from smaller to larger cells).

Template

Kahn's algorithm

from collections import deque
import heapq


def topo_kahn(n: int, edges: list[tuple[int, int]]) -> list[int] | None:
    # an edge (u, v) means u must come before v; returns None if there is a cycle
    adj: list[list[int]] = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
    q = deque(v for v in range(n) if indeg[v] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else None

DFS, reverse finishing order

Gray marks vertices on the current path, so an edge into a gray vertex is a cycle.

def topo_dfs(n: int, adj: list[list[int]]) -> list[int] | None:
    color = [0] * n  # 0 = unvisited, 1 = on the current path, 2 = finished
    finished = []
    for s in range(n):
        if color[s]:
            continue
        color[s] = 1
        stack = [(s, iter(adj[s]))]
        while stack:
            u, it = stack[-1]
            for v in it:
                if color[v] == 1:
                    return None  # back edge: cycle
                if color[v] == 0:
                    color[v] = 1
                    stack.append((v, iter(adj[v])))
                    break
            else:
                color[u] = 2
                finished.append(u)  # u finishes after everything it points to
                stack.pop()
    return finished[::-1]

Lexicographically smallest order

Replace the queue with a min-heap: among all vertices that are currently free, always take the smallest.

def topo_smallest(n: int, edges: list[tuple[int, int]]) -> list[int] | None:
    adj: list[list[int]] = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
    heap = [v for v in range(n) if indeg[v] == 0]
    heapq.heapify(heap)
    order = []
    while heap:
        u = heapq.heappop(heap)
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                heapq.heappush(heap, v)
    return order if len(order) == n else None

DP over a DAG: earliest finish time

Tasks have durations, edges are prerequisites, any number of tasks can run in parallel. A task starts when its last prerequisite ends, which is a longest-path computation done in Kahn order.

def min_finish_time(n: int, prereq: list[tuple[int, int]], time: list[int]) -> int:
    adj: list[list[int]] = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in prereq:
        adj[u].append(v)
        indeg[v] += 1
    start = [0] * n  # earliest start of each task
    q = deque(v for v in range(n) if indeg[v] == 0)
    total = 0
    while q:
        u = q.popleft()
        done = start[u] + time[u]
        total = max(total, done)
        for v in adj[u]:
            start[v] = max(start[v], done)
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return total

Deriving the graph: alien dictionary

Compare each pair of adjacent words; the first differing letter gives one edge. A longer word placed before its own prefix makes the input invalid.

def alien_order(words: list[str]) -> str:
    letters = {ch for w in words for ch in w}
    adj: dict[str, set[str]] = {ch: set() for ch in letters}
    indeg = {ch: 0 for ch in letters}
    for a, b in zip(words, words[1:]):
        for x, y in zip(a, b):
            if x != y:
                if y not in adj[x]:  # do not count a repeated edge twice
                    adj[x].add(y)
                    indeg[y] += 1
                break
        else:
            if len(a) > len(b):  # "abc" listed before "ab"
                return ""
    q = deque(sorted(ch for ch in letters if indeg[ch] == 0))
    out = []
    while q:
        x = q.popleft()
        out.append(x)
        for y in sorted(adj[x]):
            indeg[y] -= 1
            if indeg[y] == 0:
                q.append(y)
    return "".join(out) if len(out) == len(letters) else ""

Complexity

Kahn's algorithm and the DFS version are both O(n + m) time and O(n + m) space for the adjacency list. The heap version costs O(m + n log n). DAG DP adds only O(n + m).

Common pitfalls

• Edge direction. "To take course a you must first take b" is the edge b -> a. Flipping it still produces an order, just the reverse one, which is wrong.
• Skipping the cycle check. Kahn's algorithm silently returns a short list when there is a cycle; compare its length with n.
• Preorder instead of reversed postorder in the DFS version. Preorder is not a topological order: with edges a -> b and c -> a, starting at a gives the preorder a, b, c, yet c must precede a.
• A plain visited set in DFS cannot tell a cycle from a revisit; keep the "on the current path" state.
• Double-counting in-degrees when the same constraint appears twice but the adjacency is a set (alien dictionary).
• Assuming the order is unique. Many orders are usually valid; if a specific one is expected (smallest, unique), say how you pick.

Interview variations

• Course schedule I / II. Feasibility = no cycle; output = Kahn order.
• Parallel courses. Minimum semesters with unlimited parallelism = number of Kahn layers (process the queue level by level); with durations it is the earliest-finish DP above.
• Sequence reconstruction / unique order. The topological order is unique iff the queue never holds more than one vertex at a time.
• Critical path. Compute earliest start forward and latest start backward in topological order; tasks with equal values have zero slack and form the critical path.
• Implicit DAGs. Longest increasing path in a matrix, longest string chain, recipes from supplies: build edges from the rule, then Kahn or memoized DFS.
• Two-level ordering. "Sort items by groups respecting dependencies": topologically sort the groups, then the items inside each group.