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

Topological Sort Interview Guide: Kahn's Algorithm, DFS & 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 both algorithms with runnable Python, an iteration-by-iteration trace of Kahn's algorithm on a real interview graph, the min-heap variant that produces the lexicographically smallest ordering, cycle detection via leftover nodes, and a decision guide for picking Kahn's or DFS under interview pressure.

Key Takeaways

• Kahn's algorithm repeatedly removes in-degree-0 vertices. If the output contains fewer than V vertices, the leftovers sit on or downstream of a cycle — that single length check is your cycle detector.
• For the lexicographically smallest topological ordering, swap Kahn's queue for a min-heap. DFS does not guarantee the smallest order, even if you visit neighbors in sorted order.
• Both algorithms run in O(V + E). The min-heap variant costs O((V + E) log V).
• When the graph is revealed lazily (an API hands you dependencies on demand), DFS post-order is the natural fit because Kahn's needs every edge up front to compute in-degrees.
• Edge direction is where most solutions die: "X before Y" is the edge X → Y, and it is Y whose in-degree goes up.

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 — covered below).

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 comes up short. Returning None (or []) is the idiomatic way to report "infeasible."

Kahn's algorithm, one iteration at a time

Asked at Amazon — Find a valid dependency order You get n tasks labeled 0 to n-1 and dependency pairs where [a, b] means task b has to finish before task a can start. Produce any ordering of all tasks that respects every pair, and return an empty list when the dependencies form a cycle. The interviewer expects a complexity discussion at the end.

Take that question's example: n = 4, dependencies [[1,0],[2,0],[3,1],[3,2]]. Translating "b before a" into edges gives 0→1, 0→2, 1→3, 2→3 — a diamond. Initial in-degrees: node 0 has 0, nodes 1 and 2 have 1 each, node 3 has 2. Only node 0 is free, so the queue starts as [0].

Here is every iteration, with the in-degree table evolving:

Four nodes popped, four nodes in the graph, so the ordering [0, 1, 2, 3] is valid and complete. Notice iteration 1: popping node 0 dropped two in-degrees to zero at once, and both nodes entered the queue. That moment — more than one vertex free at the same time — is exactly why topological orders are not unique. A FIFO queue happens to emit 1 before 2 here; a stack would emit 2 first and produce [0, 2, 1, 3], which is equally valid.

If you narrate this table out loud while coding, you have also answered the follow-ups before they're asked: the queue only ever holds "currently free" tasks, and each edge is looked at exactly once, when its source is popped.

The lexicographically smallest ordering: Kahn's with a min-heap

When several vertices are free at once, something has to break the tie. If the problem says "return the lexicographically smallest topological ordering," break it by always taking the smallest available vertex — which means replacing the queue in Kahn's algorithm with a min-heap:

import heapq

def topo_sort_smallest(num_nodes, edges):
    adj = [[] for _ in range(num_nodes)]
    indeg = [0] * num_nodes
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1

    heap = [n for n in range(num_nodes) if indeg[n] == 0]
    heapq.heapify(heap)
    order = []
    while heap:
        u = heapq.heappop(heap)   # smallest currently-free vertex
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                heapq.heappush(heap, v)
    return order if len(order) == num_nodes else None

The greedy choice is safe because at every step, any free vertex can legally go next; picking the smallest one can never block a smaller vertex later, since removing a vertex only frees others. Complexity rises to O((V + E) log V) for the heap operations. If heapq's API is rusty, the idioms are collected in Python heapq for coding interviews, and when to reach for a heap at all is a pattern worth having ready.

Why not DFS? A DFS post-order does not guarantee the lexicographically smallest result, even if you visit vertices and neighbors in sorted order. Tiny counterexample: three nodes {0, 1, 2} with the single edge 1 → 0. The smallest valid ordering is [1, 0, 2]. But DFS started in increasing label order finishes 0 first (it has no outgoing edges), then 1, then 2, giving post-order [0, 1, 2] and reversed order [2, 1, 0] — valid, but not smallest. The reversal at the end is what breaks the greedy intuition: choices made early in the DFS end up late in the output. The fix is not a cleverer visit order; it is switching to min-heap Kahn's.

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)
                if has_cycle:
                    return          # unwind immediately
        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.

When only DFS works: the graph you have to discover

Asked at Uber — Return a Package Build Order Instead of an edge list, you get an API call that returns the direct dependencies of one package at a time. Given a target package, return a build order covering the target and everything it transitively depends on, with every dependency built before the packages that need it. You have to discover the relevant subgraph yourself through API calls.

This variant quietly rules out vanilla Kahn's algorithm: computing in-degrees requires the entire edge set up front, and here the graph is only revealed as you query it. (You could run a discovery traversal first to collect the edges and then apply Kahn's — but that's two passes where one will do.) DFS handles it naturally — recurse into each dependency as the API reveals it, and emit a package once all of its dependencies are done:

def build_order(target, get_dependencies):
    order, state = [], {}              # state: 1 = in progress, 2 = done
    def dfs(pkg):
        state[pkg] = 1
        for dep in get_dependencies(pkg):
            if state.get(dep) == 1:
                raise ValueError("dependency cycle")
            if dep not in state:
                dfs(dep)
        state[pkg] = 2
        order.append(pkg)              # post-order: deps already emitted
    dfs(target)
    return order

Note the direction flip: here edges point from a package to its dependencies, the reverse of the "u before v" convention used earlier. That is why order needs no reversal — post-order already lists dependencies first. Getting this direction question right, out loud, is worth more than the code itself; it's the same edge-direction trap from a different angle. The state map still gives GRAY/BLACK cycle detection, and memoizing finished packages keeps each API call to once per package.

Topological order as a processing schedule

Asked at Robinhood — Compute trigger counts in a DAG A DAG models trigger dependencies: one entry node fires once, and every time a node fires it fires each outgoing neighbor once. Nodes with several parents accumulate triggers from all of them. Compute how many times each node ends up firing.

Some problems don't ask for the ordering at all — they ask you to compute something along it. A node's trigger count is the sum of its parents' trigger counts, so you must not read a node's count until every parent's count is final. That is precisely what topological order guarantees, and Kahn's algorithm gives it to you with two extra lines:

count = [0] * num_nodes
count[entry] = 1
while queue:
    u = queue.popleft()
    for v in adj[u]:
        count[v] += count[u]     # u is final when popped
        indeg[v] -= 1
        if indeg[v] == 0:
            queue.append(v)

The same skeleton computes longest paths in a DAG ("minimum semesters" is the number of Kahn's layers), earliest start times in scheduling, and path counts. Whenever a value at a node depends only on its predecessors, topological order is the evaluation schedule for the DP.

Cycle detection is the other half of the question

Asked at Uber — Check feasibility of AI course schedule You're given n AI courses and prerequisite pairs, each meaning one course must be finished before another can be taken. The only question: can all n courses be completed? No ordering is requested — the entire problem is deciding whether the prerequisite graph has a cycle.

Many "topological sort" interview questions are really cycle-detection questions wearing a costume. With Kahn's, the mechanism is worth understanding, not just memorizing: a vertex enters the queue only when its in-degree hits zero. Vertices on a cycle wait on each other forever, so none of them ever reaches zero — and neither does anything downstream that depends on the cycle. When the loop ends, the leftover nodes (those never popped) are exactly the vertices on or downstream of a cycle. So len(order) < num_nodes means infeasible, and the leftovers even tell you which tasks are stuck, a nice bonus if the interviewer asks you to report the problem, not just detect it.

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.

Kahn's vs DFS: which one to reach for

Both are O(V + E), so the choice is about what the problem needs beyond a bare ordering:

Default to Kahn's. Switch to DFS when the graph is implicit or you're already doing a DFS for other reasons.

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. The min-heap variant for lexicographically smallest ordering is O((V + E) log V) time. 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; sometimes with the graph hidden behind an API, as in the Uber question above.
• 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.

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. Watch for problems that flip the convention, like the package-build question where edges point at dependencies.
• 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.

Practice these on PracHub

Grouped by the specific skill each one drills:

• Find a valid dependency order (Amazon) — the canonical Kahn's implementation with the cycle → empty-list contract.
• Check feasibility of AI course schedule (Uber) — pure cycle detection; no ordering to return.
• Return a Package Build Order (Uber) — topological sort on an implicit graph discovered through an API; DFS territory.
• Compute trigger counts in a DAG (Robinhood) — DP evaluated in topological order rather than the order itself.
• Return a topological ordering of a graph — the baseline implementation, worth being able to write cold.
• Implement topological sort from string input — parsing the dependency pairs before sorting.
• Implement topological sort and tree-boundary traversal — topological sort under time pressure alongside a second problem.

More graph and ordering problems live in the Coding & Algorithms bank.

FAQ

When should I use Kahn's algorithm vs DFS for topological sort?

They're equivalent in complexity, so choose by the extras. Kahn's gives you cycle detection for free, layer-by-layer processing, and the min-heap tie-break for lexicographically smallest orderings. DFS wins when the graph is implicit — revealed through an API or computed on the fly — because Kahn's needs every edge up front to build the in-degree table. You can rescue Kahn's with a separate discovery pass that collects the edges first, but DFS does discovery and ordering in a single traversal.

How do I get the lexicographically smallest topological ordering?

Use Kahn's algorithm with a min-heap instead of a FIFO queue: at every step, pop the smallest vertex whose in-degree is zero. The greedy choice is safe because removing a free vertex only frees others, never blocks them. Complexity is O((V + E) log V).

Why doesn't DFS guarantee the lexicographically smallest topological order?

Because the output is the reverse of the finishing order, greedy choices made early in the DFS land late in the result. With nodes {0, 1, 2} and the single edge 1 → 0, sorted-order DFS produces [2, 1, 0] while the smallest valid ordering is [1, 0, 2]. No visiting-order tweak fixes this reliably; use min-heap Kahn's instead.

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 — the leftover vertices are exactly those on or downstream of a cycle. With DFS, a cycle exists when you encounter a GRAY (on-the-current-path) vertex, which is a back edge. A graph with a cycle has no topological order at all, so the correct response is to report infeasibility.

Is the topological order unique?

Usually not. Whenever two or more vertices have in-degree zero at the same time, either can go 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.

What's the time complexity of topological sort?

O(V + E) time and space for both Kahn's algorithm and DFS, since each vertex and edge is processed exactly once. That is optimal. The min-heap variant for the smallest ordering adds a log factor: O((V + E) log V).