Topological Sort Interview Guide: Kahn's & DFS + Cycle Detection

Topological Sort: The Interview Guide (Kahn's + DFS, with Cycle Detection)

Topological sort orders the vertices of a directed acyclic graph (DAG) so that every edge u → v points from earlier to later in the ordering. In interviews it shows up whenever a problem is really asking "in what order can I do these tasks given their dependencies?" — course schedules, build systems, package installs, recipe steps. If you can recognize that framing and implement either Kahn's algorithm or a DFS post-order, you can clear the entire family of questions.

This guide covers the mental model, both standard algorithms with runnable Python, how to detect the cycle that makes a valid ordering impossible, the variations interviewers actually ask, and the mistakes that quietly fail half the test cases.

What a topological order actually is

Given a directed graph, a topological ordering is a linear sequence of all vertices such that for every directed edge u → v, u comes before v. Two facts follow immediately and are worth saying out loud in an interview:

• A topological order exists if and only if the graph is a DAG (directed and acyclic). A cycle means two tasks each depend on the other, so no valid order exists.
• The ordering is not unique. Any vertex with no remaining incoming edges can go next, so most DAGs have many valid answers. Interviewers usually accept any valid order unless they ask for a specific tie-break (e.g. lexicographically smallest).

For the DAG above, A, B, C, D, E, F and B, A, C, E, D, F are both valid — but C can never appear before both A and B.

When to reach for it (pattern recognition)

You are almost certainly looking at a topological sort if the prompt contains any of these signals:

• "ordering," "sequence," or "schedule" of items that have prerequisites or dependencies.
• A relation phrased as "X must come before Y," "Y depends on X," or "to build Y you first need X."
• A question of feasibility: "is it possible to finish all courses / build all targets?" — that is cycle detection on a dependency graph.

The first move is always the same: model the input as a graph. Items become vertices; each "X before Y" becomes a directed edge X → Y. Once it's a graph, the algorithm is mechanical.

Algorithm 1 — Kahn's algorithm (BFS on in-degrees)

Kahn's algorithm is the one most people reach for because it doubles as cycle detection and is easy to reason about. The idea: repeatedly take a vertex with in-degree 0 (no unmet prerequisites), append it to the result, and "remove" it by decrementing its neighbors' in-degrees.

from collections import deque

def topo_sort_kahn(num_nodes, edges):
    """edges: list of (u, v) meaning u must come before v.
    Returns a valid ordering, or None if the graph has a cycle."""
    adj = [[] for _ in range(num_nodes)]
    indeg = [0] * num_nodes
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1

    queue = deque(n for n in range(num_nodes) if indeg[n] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)

    return order if len(order) == num_nodes else None  # None => cycle

The len(order) == num_nodes check at the end is the cycle test: if a cycle exists, the vertices inside it never reach in-degree 0, so they never enter the queue and the result is short. Returning None (or []) is the idiomatic way to report "infeasible."

Lexicographically smallest order: swap the deque for a heapq min-heap. Pushing/popping the smallest available vertex each step gives the smallest valid order in O((V + E) log V).

Algorithm 2 — DFS post-order (reverse finishing times)

The DFS approach is elegant and a good one to mention as an alternative. Run DFS; when a vertex finishes (all its descendants are processed), push it onto a stack. The reversed stack is a topological order.

def topo_sort_dfs(num_nodes, edges):
    adj = [[] for _ in range(num_nodes)]
    for u, v in edges:
        adj[u].append(v)

    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * num_nodes
    order = []
    has_cycle = False

    def dfs(u):
        nonlocal has_cycle
        color[u] = GRAY                 # on the current recursion path
        for v in adj[u]:
            if color[v] == GRAY:        # back-edge => cycle
                has_cycle = True
                return
            if color[v] == WHITE:
                dfs(v)
        color[u] = BLACK
        order.append(u)                 # post-order

    for n in range(num_nodes):
        if color[n] == WHITE:
            dfs(n)
        if has_cycle:
            return None

    return order[::-1]                  # reverse finishing order

The three-color scheme is the key detail: a GRAY neighbor means you've looped back onto a vertex still on the current path — a back edge, which proves a cycle. A plain visited boolean cannot tell a cross edge from a back edge, so it silently misses cycles. For deep graphs, convert this to an explicit stack to avoid hitting Python's recursion limit.

Cycle detection is the other half of the question

Many "topological sort" interview questions are really cycle-detection questions wearing a costume. "Can you finish all courses?" → run Kahn's and check whether the order covers every node. "Find one valid build order, or report it's impossible" → same algorithm, return the order or the failure signal. Always handle the cycle case explicitly; an answer that assumes a valid order always exists will fail the adversarial test case the interviewer has ready.

Complexity

Both algorithms run in O(V + E) time and O(V + E) space (adjacency list plus the queue/stack and bookkeeping arrays). That's optimal — you must look at every vertex and edge at least once. State this confidently; it's a common follow-up.

Variations interviewers actually ask

• Course Schedule / prerequisites — feasibility (can all be taken?) and "return one valid order."
• Alien Dictionary — derive char → char edges from adjacent words, then topologically sort the alphabet. The trick is building the graph correctly (and catching the invalid-prefix edge case).
• Build / package order — given a target and its dependencies, produce an install order.
• Parallel scheduling / "minimum semesters" — Kahn's processed layer-by-layer; the number of layers is the longest dependency chain (critical path).
• String / token input — you parse the dependency pairs out of text first, then sort.

You can practice these on real, interviewer-sourced versions: Return a topological ordering of a graph, Implement topological sort from string input, and Implement topological sort and tree-boundary traversal.

Common mistakes that fail test cases

• Forgetting the cycle check. Returning a partial order as if it were complete is the single most common bug. Always compare the result length to the vertex count (Kahn's) or color-check (DFS).
• Building in-degrees from the wrong direction. If "X before Y" is edge X → Y, then Y gains in-degree — not X. Reversing this produces a valid-looking but wrong order.
• Using a boolean visited for DFS cycle detection. You need the three states (unvisited / on-path / done) to distinguish a back edge from an already-finished branch.
• Disconnected graphs. Seed the queue with all in-degree-0 vertices and start DFS from every unvisited vertex, or you'll drop whole components.
• Recursion depth. A chain of 10⁵ nodes blows the default recursion limit; use Kahn's or an iterative DFS.

FAQ

When should I use Kahn's algorithm vs DFS? They're equivalent in complexity. Prefer Kahn's when you also need cycle detection or layer-by-layer ("minimum time/semesters") processing, since both fall out naturally. DFS is slightly less code if a cycle is guaranteed not to exist.

How do I detect a cycle during a topological sort? With Kahn's, a cycle exists when the produced order contains fewer vertices than the graph. With DFS, a cycle exists when you encounter a GRAY (on-the-current-path) vertex — a back edge.

Is the topological order unique? Usually not. Any vertex with no unmet dependencies can come next, so most DAGs have many valid orders. If the problem wants a deterministic answer, it will specify a tie-break such as lexicographically smallest (use a min-heap with Kahn's).

What's the time complexity of topological sort? O(V + E) for both Kahn's and DFS, since each vertex and edge is processed once.

Can you topologically sort a graph with cycles? No. A topological order exists only for a DAG. If the graph has a cycle, the correct response is to report that no valid ordering exists.