What is topological sort? Kahn's algorithm and DFS explained

In this article

1. Before you start
2. Why interviewers ask this
3. Topological sort from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

Why interviewers ask this

A candidate who cannot turn a story about dependencies into a graph stalls on course schedules, build steps, task schedules and package installs, which all reduce to a topological sort; package managers do dependency resolution with a topological sort. This is one of the graph patterns in the coding interviews guide; an interviewer uses it to see whether you can make that translation.

A weak answer sorts the items by a guess and misses the loop in "A needs B, B needs A". A strong answer names the graph, picks an algorithm, says what happens on a cycle, and states the running time. The question also separates candidates who memorised one template from those who can explain why it works, because a natural follow-up is "what if the input has a cycle?".

Topological sort from first principles

Topological order

A topological order of a directed graph is a list of all its nodes in which, for every edge from node u to node v, u appears before v, so that every prerequisite comes before the task that depends on it.

Directed acyclic graph

A directed acyclic graph (DAG) is a directed graph with no cycle, meaning no path of edges that leads from a node back to itself; a graph has a topological order if and only if it is a DAG (Sedgewick and Wayne, Algorithms, 4th ed., section 4.2).

In-degree

The in-degree of a node is the number of edges that point into it, which for a task is the number of prerequisites that have not yet been completed.

Kahn's algorithm

Kahn's algorithm is a method that builds a topological order by repeatedly removing a node whose in-degree is zero and lowering the in-degree of its neighbours, until no such node remains.

In plain words

Getting dressed is a topological sort. Socks come before shoes. Trousers come before a belt. Socks and trousers have no order between them, so you may pick either. At each point you choose any item whose requirements are done. The analogy breaks in one place: a person never meets "shoes before socks and socks before shoes", while a program must detect that case. Stated precisely, a topological sort repeatedly lists a node with no unfinished prerequisites, and it stalls exactly when a cycle remains.

The example below uses six build tasks. Task A installs tools and B reads the configuration; C compiles and needs both; D runs tests and E packages, and both need C; F deploys and needs D and E. An edge goes from a prerequisite to the task that depends on it, so there are six edges: A to C, B to C, C to D, C to E, D to F and E to F.

Step 1: Draw each edge from prerequisite to dependent

The first step turns the problem statement into a graph. The input is a list of "X must come before Y" facts; the output is one directed edge from X to Y for each fact, stored as an adjacency list, which maps every node to the nodes it points to (in Python, a defaultdict of lists is a common way to build it). Direction matters: an edge from A to C says A comes first.

Reversing the edges produces the reverse order, a frequent source of off-by-direction bugs when a problem is written as "C depends on A". The same algorithm on reversed edges answers "delete storages only when they have no children", a question reported by candidates: a node is removed once everything below it is gone. What you now know: the problem is a graph, and every later step reads only this structure.

Step 2: Count the in-degree of every node

The second step counts, for each node, how many edges point into it. The input is the adjacency list; the output is one integer per node. In the example the in-degrees are A 0, B 0, C 2, D 1, E 1 and F 2. A count of zero means "no unfinished prerequisite", so that node can be listed now. One pass over all edges computes every count, so this step takes time proportional to the number of edges. Write the counts in a table beside the graph; the later steps only edit this table. What you now know: the counts are a ready-made record of what is still blocked.

Step 3: Put every node with in-degree zero into a queue

The third step seeds a queue with all nodes whose count is zero. The input is the table of counts; the output is a queue, here A then B. A queue is a first-in, first-out list, so nodes leave in the order they were added. Any container would produce a valid order, and a stack (a last-in, first-out list) gives a different but equally valid one. If the queue is empty at the start, every node has a prerequisite, so the graph must contain a cycle. Say this out loud, because it is the quickest cycle case to spot. What you now know: the queue always holds the tasks that can run right now.

Step 4: Remove a node and lower its neighbours' counts

The fourth step is the loop. Take a node from the front of the queue and append it to the output; then for each node it points to, subtract one from that node's count, and if a count reaches zero, add that node to the queue.

Removing A lowers C from 2 to 1; removing B lowers C to 0 and queues C; removing C queues D and E; removing D lowers F to 1 and removing E queues F. The output is A, B, C, D, E, F. Every node enters the queue once and every edge is used once, so the loop takes time proportional to the nodes plus the edges, written O(V + E), where V is the number of nodes (vertices) and E the number of edges. What you now know: each node is listed only after all of its prerequisites.

Step 5: Compare the output length with the node count

The last step decides whether the answer is real. If the output holds fewer nodes than the graph, some nodes never reached an in-degree of zero, which happens exactly when they sit on or behind a cycle, and no topological order exists. Return an error or an empty list in that case.

This is the line candidates forget: the loop can finish without raising anything and still hand back a partial list. In the worked example below, adding a single edge from F to C raises C to an in-degree of 3, and removing A and B lowers it only to 1, so the output holds two nodes out of six.¹ What you now know: the length check is the cycle detector.

1 · Draw the edges2 · Count in-degrees3 · Queue the zeros4 · Remove and lower5 · Compare lengthsReplay

Step-by-step description

1. Each edge runs from a prerequisite to its dependent task.
2. In-degree is the number of edges pointing into a node.
3. Nodes with in-degree zero can go first.
4. Take a node out, lower its neighbours' counts by one.
5. Output shorter than the node count means a cycle.

• Draw each edge from the prerequisite to the task that depends on it.
• The in-degree of a node is the number of edges pointing into it.
• Nodes with in-degree zero go into a queue.
• Removing a node lowers the in-degree of each of its neighbours by one.
• If the output holds fewer nodes than the graph, the graph has a cycle.

Worked example

The example graph has six nodes and six edges. Kahn's algorithm outputs A, B, C, D, E, F, and a check of all 720 orderings of the six nodes finds exactly 4 valid topological orders: A and B may swap, and D and E may swap.¹ The depth-first method (explained below) gives B, A, C, E, D, F, which is also valid, and Python's graphlib.TopologicalSorter returns A, B, C, D, E, F for the same input.¹ (Python documentation notes that the order returned can depend on the order in which items were inserted.)

Here is the core of the script that produced those numbers.

from collections import deque

def topological_order(nodes, edges):
    adj = {n: [] for n in nodes}
    indegree = {n: 0 for n in nodes}
    for before, after in edges:
        adj[before].append(after)
        indegree[after] += 1
    queue = deque(n for n in nodes if indegree[n] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in adj[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
    return order if len(order) == len(nodes) else None  # None means a cycle

Text description of the diagram

• Starting in-degrees are A 0, B 0, C 2, D 1, E 1, F 2.
• After adding the edge from F to C, C starts at in-degree 3 and falls only to 1 after A and B, so Kahn's algorithm outputs only A and B.

Trade-offs and edge cases

Kahn's algorithm and depth-first search (DFS) solve the same problem. DFS visits every unvisited node, appends each node to a list when it finishes, and reverses the list; the Topological Sorting article on cp-algorithms.com (April 2025) describes the same procedure as sorting by descending exit time. The depth-first version runs in time proportional to the number of nodes plus edges (Sedgewick and Wayne), and Kahn's loop meets the same bound by the argument in Step 4. Kahn's version needs no recursion and detects a cycle from the output length; the DFS version needs a separate three-state check, explained next, and its recursion can be deep on a long chain.

How the DFS version works

Depth-first search (DFS) explores a graph by following one edge as far as it goes before backing up. From a node, move to an unvisited neighbour and repeat until a node has none, then step back and try the previous node's next neighbour. It is usually written as recursion, a function that calls itself for each neighbour. Each call waits on the call stack, the program's pile of unfinished function calls, and a call finishes when all its neighbours are done. The moment a node finishes is its exit time.

The topological trick is to write each node down as soon as it finishes, so a node is listed only after everything it points to is listed. That list is called postorder. Reverse it and every edge points forward. On the six-task graph, the search starts at A, goes to C, then D, then F. F has no neighbours, so it finishes first, then D; the search backs up to C, visits E (F is already done), and E, C and A finish in that order; last, B is started and finishes. The finish order is F, D, E, C, A, B; reversed, it is B, A, C, E, D, F, which is a valid order.¹

The cycle check, covered in full in detecting a cycle in a directed graph, needs three states per node: unvisited, in progress (its call has started but not finished) and done. If the search reaches a node that is in progress, it has followed edges back to a node still being explored, which means a cycle, and no order exists. Reaching a done node is harmless. The unvisited and done states alone cannot tell these two cases apart, which is why the DFS version needs the extra state while Kahn's version gets the answer from the length.

Text description of the diagram

• Both methods run in time proportional to V plus E.
• Kahn's algorithm detects a cycle when the output is shorter than the node count.
• The depth-first method reverses the postorder.

A practical limit of the recursive method is that a very long chain of dependencies can exhaust the call stack in languages with a small recursion limit, and the queue version avoids this. Three edge cases come up in follow-ups.

The three cases are as follows. First, a graph with a cycle has no order at all, so say what you return. Second, the order is rarely unique: the example has four, so if the problem needs a specific one, such as the alphabetically smallest, replace the queue with a priority queue, or heap (a structure that always hands back the smallest item; see K closest points to origin for heaps). Third, isolated nodes have in-degree zero and are queued at once, and separate components need no special handling; a graph with no edges returns its nodes in input order.

Choosing between the two is mostly a matter of what you must also report. If the problem asks "can it be done at all", Kahn's algorithm answers it directly with the length check. If the problem asks for a depth-first property as well, such as strongly connected components (groups of nodes that can all reach one another) or the finishing times of a traversal, the DFS version reuses work you already do.

A graph with a cycle is not useless: the nodes left over after Kahn's loop stops are exactly the ones that lie on a cycle or depend on one, and reporting them is often the most helpful error message, for example "these tasks are on, or wait behind, a cycle".

How to answer it in an interview

Say it in this order: graph, algorithm, cycle behaviour, running time. If you have time left, mention the DFS alternative. Python also ships this as graphlib.TopologicalSorter, a common topic in Python interview questions.

Common mistakes

1. Forgetting the cycle check. (wrong) "The loop ends, so I return the output." (right) "I return the output only if its length equals the node count."
2. Drawing the edges backwards. (wrong) An edge from "C needs A" drawn from C to A. (right) An edge runs from the prerequisite to the dependent, from A to C.
3. Calling the order unique. (wrong) "The topological order is A, B, C, D, E, F." (right) "One valid order is A, B, C, D, E, F; this graph has four."
4. Ignoring isolated nodes. (wrong) Building the node list only from edge endpoints. (right) Start from the full node list so nodes with no edges still appear.
5. Stating the wrong running time. (wrong) "It is quadratic because of the loop inside the loop." (right) "Each node and each edge is handled once, so it is proportional to nodes plus edges."

Follow-up questions

Given dependencies, how do you return a sorted list of all delayed flight IDs?

Model each flight as a node and each "this flight must leave before that one" dependency as an edge. Then run a breadth-first search from the flights that are delayed at the start, which visits them, then everything they point to, marking each node once. Every flight reached is a knock-on delay, so the starting flights plus the reached flights are the full answer. Return them sorted by ID, or in topological order of the whole graph for dependency order, and say that a cycle means no consistent order exists.

How does the alien dictionary problem use topological sort?

Each pair of neighbouring words in the sorted list gives at most one edge: the first position where the two words differ says that the letter in the first word comes before the letter in the second. In the classic example of five words, wrt, wrf, er, ett and rftt, the edges are t before f, w before e, r before t and e before r, and the topological order is w, e, r, t, f.¹ If a word is followed by its own proper prefix, such as abc then ab, no valid alphabet exists.

Is a topological order unique?

Not always. The order is unique if and only if the graph contains a directed path through every node, so that each consecutive pair in the order is joined by an edge. That path need not be the whole graph: A to B, B to C and A to C has exactly one valid order, A, B, C, although the edge from A to C is not part of a single chain of three. The interview test is that Kahn's queue never holds more than one node at a time.

What if the graph is huge and does not fit in memory?

Do not scan the whole edge file once per removed node, which costs about V times E reads; group the edge file by source node so that removing a node reads only its own block and the total stays proportional to E. Alternatively go level by level, where one sequential scan lowers the counts of the whole current level together, at about the number of levels times E. If even the in-degree table does not fit, partition it by node ID across files or machines, or use a distributed graph engine.

What changes if tasks can run in parallel?

Instead of removing one node at a time, remove every node with in-degree zero together as one "level", run them in parallel, then lower the counts for all their neighbours. The number of levels equals the number of tasks on the longest dependency chain: 4 here, the chain A, C, D, F; the levels are {A, B}, {C}, {D, E}, {F}. Each level can run as parallel processing. Python's TopologicalSorter supports this with its get_ready and done methods, and build systems and job schedulers use this level-by-level form.

Sources

1. graphlib: Functionality to operate with graph-like structures — Python Software Foundation (Python 3 documentation; read 2026-10-24, page has no publication date), 24 Oct 2026
2. Algorithms, 4th edition, section 4.2 Directed Graphs — Princeton University (Sedgewick and Wayne), 14 Jan 2020
3. Topological Sorting — CP-Algorithms, 22 Apr 2025