LiveCodingInterview.com
← Articles

Topological Sort: Kahn's Algorithm and DFS

Topological sort takes a directed graph with no cycles and arranges every node in a line so each edge points forward, from a node toward something later in the order. If node A points to node B, A always lands before B in the result. You reach for it whenever one task depends on another finishing first: course prerequisites that gate later classes, a build system compiling files in dependency order, a package manager installing a library before the package that imports it.

Two algorithms produce a valid topological order, and an interviewer who asks for this pattern usually wants to see that you know both well enough to pick the right one on the spot. Kahn's algorithm works outward from the nodes with nothing pointing at them, using a queue much like a breadth-first search. The depth-first search approach explores each branch all the way down and then reverses the order nodes finish in. Both run in O(V + E) time, where V is the number of nodes and E is the number of edges, and both fail the same way: a cycle means no valid order exists at all, and a solid answer has to detect that case instead of returning nonsense.

This piece covers how each algorithm works with runnable code, how to catch a cycle before you return a broken answer, which approach to reach for when an interviewer hands you the problem cold, and the specific interview questions that come from this exact pattern.

What Is Topological Sort?

Topological sort is an ordering of the nodes in a directed graph such that for every directed edge from node A to node B, A appears before B in the output. It only works on a directed acyclic graph, usually shortened to a DAG, because a cycle would force some node to come both before and after itself, which is a contradiction no ordering can satisfy.

Picture five courses where course 2 requires course 1, course 3 requires both 1 and 2, and course 4 requires only course 3. A topological order lists 1, then 2, then 3, then 4, in exactly that relative sequence, though nothing stops a fifth, unrelated course from sliding in anywhere. Most graphs like this have more than one valid ordering: any sequence that respects every edge counts, so an interviewer checking your output usually verifies it against the edge list rather than comparing it to one memorized answer.

When Does a Graph Even Have a Valid Order?

A directed graph has at least one valid topological order exactly when it contains no cycles. A cycle is a path that leaves a node and eventually loops back to it, and once one exists, every node on that loop depends on a node that depends on it in turn, so no linear arrangement can put all of them in a consistent direction.

This is why the honest answer to a topological sort question always starts with checking for a cycle, not with producing an ordering and hoping the graph was acyclic. A course schedule with course A requiring course B and course B requiring course A back is exactly the kind of malformed input interviewers slip in specifically to see whether you check for it. Our breakdown of BFS and DFS covers the traversal fundamentals both topological sort algorithms build on, if graph terms like in-degree or post-order still feel shaky.

How Does Kahn's Algorithm Work?

Kahn's algorithm builds the order from the outside in, starting with every node that has no incoming edges and repeatedly peeling nodes off once their dependencies are satisfied. Track how many incoming edges point at each node, its in-degree, queue up every node that starts at zero, then repeatedly pop a node off the queue, add it to the result, and decrement the in-degree of everything it points to.

Here is the full trace against a small graph. Say node 0 points to nodes 1 and 2, node 1 points to node 3, and node 2 points to node 3 as well.

  1. Compute in-degrees: node 0 has 0, node 1 has 1, node 2 has 1, node 3 has 2.
  2. Queue every node with in-degree 0. Only node 0 qualifies, so the queue holds [0].
  3. Pop node 0, append it to the result, and decrement the in-degree of nodes 1 and 2. Both drop to 0, so both join the queue: [1, 2].
  4. Pop node 1, append it, decrement node 3's in-degree to 1. Not zero yet, so it stays out of the queue.
  5. Pop node 2, append it, decrement node 3's in-degree to 0. It joins the queue: [3].
  6. Pop node 3, append it. The queue is empty and the result is [0, 1, 2, 3], a valid order.
from collections import deque

def topological_sort_kahn(num_nodes, edges):
    graph = [[] for _ in range(num_nodes)]
    in_degree = [0] * num_nodes

    for src, dst in edges:
        graph[src].append(dst)
        in_degree[dst] += 1

    queue = deque(node for node in range(num_nodes) if in_degree[node] == 0)
    order = []

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

    if len(order) != num_nodes:
        raise ValueError("graph has a cycle, no valid order exists")

    return order

The queue can hold more than one node at a time whenever multiple dependencies clear at once, and the order you pop them in is one of potentially several correct answers. Building the in-degree array and the adjacency list both take O(V + E), and the main loop visits every node once and every edge once, so the whole algorithm runs in O(V + E) time and O(V) space for the queue and in-degree array. That's the same Big O vocabulary interviewers expect in any complexity discussion, not something specific to graph problems.

How Does the DFS Approach Work?

The depth-first search approach to topological sort explores each branch of the graph as deep as it goes before backtracking, then reverses the order nodes finished in. A node finishes once every node it points to has already finished, which means the last node to finish overall has nothing left depending on it, and belongs at the very end of a forward order, or the very front once you reverse the finish order.

Run a standard DFS from every unvisited node, and each time a node's recursive call returns, push it onto a stack. Once every node has been visited, popping the stack from top to bottom gives a valid topological order.

def topological_sort_dfs(num_nodes, edges):
    graph = [[] for _ in range(num_nodes)]
    for src, dst in edges:
        graph[src].append(dst)

    visited = [False] * num_nodes
    on_stack = [False] * num_nodes
    finish_stack = []

    def visit(node):
        visited[node] = True
        on_stack[node] = True
        for neighbor in graph[node]:
            if on_stack[neighbor]:
                raise ValueError("graph has a cycle, no valid order exists")
            if not visited[neighbor]:
                visit(neighbor)
        on_stack[node] = False
        finish_stack.append(node)

    for node in range(num_nodes):
        if not visited[node]:
            visit(node)

    return finish_stack[::-1]

The on_stack array tracks which nodes are part of the current recursion path, and finding a neighbor still on that path is exactly what a cycle looks like from inside a DFS, which is why this version detects one for free instead of needing a second pass. Every node gets visited once and every edge gets examined once, so this also runs in O(V + E) time, with O(V) space for the recursion stack, the visited and on_stack arrays, and the output.

Kahn's Algorithm or DFS: Which Should You Use in an Interview?

Reach for Kahn's algorithm when the problem already talks in terms of dependencies or prerequisites and when you want cycle detection that reads cleanly, since counting how many nodes made it into the result versus the total node count is a one-line check. Reach for the DFS approach when the graph is already being explored with DFS elsewhere in your solution, or when the input is naturally recursive, like a file system or a nested build target, since you avoid maintaining a separate in-degree array.

Neither approach is faster than the other in big-O terms, so an interviewer who asks which one you would use is really asking whether you understand the tradeoff rather than testing for a single correct answer. Kahn's algorithm tends to read more clearly to someone unfamiliar with the code, because the queue mirrors a real-world process: work through everything that is ready, and let finishing an item clear the way for what depends on it. The DFS approach tends to be shorter to write from scratch when recursion is already fresh in your head, and it catches a cycle mid-traversal instead of needing a length check at the end.

A reasonable default is to lead with Kahn's algorithm when asked to solve topological sort cold, since it is easier to narrate step by step at a whiteboard or in a shared editor, and to mention the DFS approach as the alternative if the interviewer asks for a second way to solve it. That second-approach question comes up often enough that walking in with both ready is worth the extra practice.

How Do You Detect a Cycle During Topological Sort?

You detect a cycle by checking whether every node made it into the output, in Kahn's algorithm, or by tracking which nodes are still on the current recursion path, in the DFS approach. Both checks come directly out of the algorithm you already wrote rather than needing a separate pass over the graph.

In Kahn's algorithm, a node only leaves the queue once its in-degree hits zero, and a node stuck inside a cycle never reaches zero, because at least one of its dependencies is also stuck in the same cycle waiting on it. That means the result list ends up shorter than the total node count whenever a cycle exists anywhere in the graph, even a cycle that doesn't touch every node. The check is a single comparison after the main loop finishes, shown as a length check in the code above.

In the DFS approach, a cycle shows up the moment the traversal revisits a node that is still on_stack, meaning still an active ancestor in the current recursion path rather than a node that finished and returned already. A node visited earlier but already popped off the stack is fine to see again, since that just means two different paths converge on it, which is normal in a DAG and not a cycle at all. Confusing visited with currently on the stack is the most common bug in a from-scratch DFS topological sort, and it's worth saying out loud during an interview that you're tracking the two separately on purpose.

What Are the Most Common Topological Sort Interview Questions?

The most common version by far is course schedule: given a number of courses and a list of prerequisite pairs, determine whether it's possible to finish every course, which is really just asking whether the prerequisite graph has a cycle. A close follow-up, course schedule II, asks for one valid order to actually take the courses in, which means returning the full topological sort instead of a yes-or-no answer.

Alien dictionary is a heavier variant: given a list of words from a fictional language sorted by that language's own alphabet, work out the order of the letters themselves. You build a graph where an edge points from one letter to another based on the first place two adjacent words differ, then run a topological sort over the letters rather than over the words. It's a good test of whether you can spot topological sort hiding inside a problem that never mentions graphs at all.

Build order or task scheduling problems phrase the same core idea in a systems context: given a list of build targets or tasks and which ones depend on which, produce an order that never builds or runs something before what it needs. That version shows up again, dressed up as a distributed job scheduler, in system design interviews. Parallel course scheduling extends course schedule by asking for the minimum number of semesters needed if you can take any number of courses at once, so long as their prerequisites are already done, which is really the length of the longest path through the same dependency graph.

How Do You Recognize a Topological Sort Problem in an Interview?

Recognize a topological sort problem by two signals showing up together: a directed relationship between items, phrased as depends on, requires, must come before, or points to, and a request for a valid order or a yes-or-no answer about whether one exists, since neither signal alone is enough. Plenty of directed-graph problems never ask for an ordering, and plenty of ordering problems, like sorting a plain array, have nothing to do with a graph.

The giveaway phrase to listen for is a prerequisite relationship stated as pairs: course B requires course A, task X must run before task Y, package P depends on package Q. The moment you hear a list of pairs like that, sketch a directed graph from item to item and ask yourself whether the problem wants an order, a cycle check, or both. If it also asks for the minimum time or minimum number of rounds to finish everything, that's usually the length of the longest path through the same graph rather than a separate technique, so you don't need to reach for anything new.

Say the plan out loud before you write anything: build an adjacency list and in-degree count from the pairs, pick Kahn's algorithm or DFS based on which one you can narrate more clearly under pressure, and mention up front that you'll check for a cycle rather than assume the input is clean. Recognizing this pattern before you start coding, the same way you'd spot a sliding window or a two-pointer setup, buys back the minutes you'd otherwise lose testing the wrong approach on a graph problem in front of someone watching.

Frequently Asked Questions

What is topological sort used for?

Topological sort orders items so every dependency comes before whatever depends on it. Real systems use it for compiling code in the right order, resolving package installs, scheduling courses around prerequisites, and sequencing build targets or CI pipeline steps.

Can a graph with a cycle have a topological sort?

No, because a cycle means at least one node depends, directly or indirectly, on itself, and no linear order can place a node both before and after itself. Both Kahn's algorithm and the DFS approach can detect this case instead of returning an invalid order.

What is the time complexity of topological sort?

Both Kahn's algorithm and the DFS approach run in O(V + E) time, where V is the number of nodes and E is the number of edges, since each visits every node once and examines every edge once. Space complexity is O(V) for both.

Is topological sort the same as BFS or DFS?

Kahn's algorithm is built on the same queue-driven pattern as BFS, and the second approach is a direct application of DFS with a reversed finish order, but neither is exactly a plain BFS or DFS. Topological sort adds the in-degree bookkeeping or the finish-order reversal on top of the underlying traversal.

Does topological sort give a unique answer?

Usually not, because any ordering that respects every directed edge counts as valid, so most graphs have several correct answers. Only a graph shaped like a single chain, where every node has exactly one predecessor and one successor, produces a unique order.

What is the difference between course schedule and course schedule II?

Course schedule asks whether it's possible to finish every course at all, which is really a cycle check on the prerequisite graph. Course schedule II asks for one valid order to take the courses in, so it returns the full topological sort instead of a yes-or-no answer.