Mediumtopological sortDAGKahn's algorithmgraphscycle detectiondependencies

Step 13 of 16 in DSAIntermediateRead first: Graph Traversal: BFS and DFS

Topological Sort

Topological sort orders a DAG so every edge points forward. Kahn's algorithm and the DFS method, both O(V+E), with run output, cycle detection and a 1,000-graph property check.

Chakrapani Gajji

AI, ML, Data Science, Data Analytics, Big Data, Python

Published 13 Oct 2026 · Updated 23 Oct 2026

Short answer

A topological sort orders the nodes of a directed acyclic graph so every edge points from an earlier node to a later one; it exists exactly when the graph has no cycle. Kahn's algorithm repeatedly removes nodes with in-degree zero, and the DFS method reverses finishing order. Interviewers expect both to run in O(V + E) and to detect cycles.

A topological sort arranges the nodes of a directed acyclic graph in a line so every edge points from an earlier node to a later one. It runs in O(V + E) using either Kahn's in-degree method or a reversed DFS finishing order, and the same code tells you when no valid order exists because of a cycle.

Key facts

A topological order of a directed graph exists if and only if the graph has no cycle, that is, when it is a DAG.
Kahn's algorithm queues nodes with in-degree zero and detects a cycle when its output holds fewer nodes than the graph.
The DFS method for topological sort reverses the finishing order and detects a cycle when an edge reaches a gray node still on the recursion stack.
Both Kahn's algorithm and the DFS method for topological sort run in O(V + E) time with O(V) extra space.
Topological order is usually not unique: the diamond graph A to B, A to C, B to D, C to D has exactly two valid orders, A B C D and A C B D.
Replacing the queue in Kahn's algorithm with a min-heap gives the lexicographically smallest topological order.

Topological sorting, Wikipedia Topological Sorting, cp-algorithms graphlib, Python standard library

01The problem: tasks with prerequisites

A topological order lists every node of a directed acyclic graph so that each edge points forward, which is exactly an order that respects all prerequisites.

Take a degree plan. Intro comes before Data Structures, Data Structures before Algorithms and DBMS, Intro before OS, OS before Networks, and the Capstone needs Algorithms, DBMS and Networks. You want one sequence in which you could actually take the courses.

Model courses as nodes and "A must come before B" as a directed edge A to B. A topological order is a sequence of all nodes where every edge goes from an earlier position to a later one. It exists if and only if the graph has no cycle. If the Capstone were also a prerequisite of Data Structures, no valid order would exist, and detecting that is half of the job.

The order is usually not unique. In the small diamond A to B, A to C, B to D, C to D, exactly two orders work: A B C D and A C B D. I checked this by brute force over all 24 permutations and got those two.

02Kahn's algorithm: peel off nodes with no prerequisites

Kahn's algorithm repeatedly removes a node with in-degree zero and lowers the in-degree of its neighbours, and it finds a cycle if nodes remain at the end.

Count each node's in-degree, the number of unmet prerequisites. Put every node with in-degree 0 in a queue. Pop one, append it to the answer, and decrement the in-degree of everything it points to. Any neighbour that reaches 0 joins the queue. If the answer ends up shorter than the node count, the leftover nodes sit on or behind a cycle.

from collections import deque, defaultdict

def kahn(courses, prereqs):
    out = defaultdict(list)
    indeg = {c: 0 for c in courses}
    for a, b in prereqs:          # a must come before b
        out[a].append(b)
        indeg[b] += 1
    q = deque(c for c in courses if indeg[c] == 0)
    order = []
    while q:
        c = q.popleft()
        order.append(c)
        for nxt in out[c]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)
    if len(order) != len(courses):
        stuck = [c for c in courses if indeg[c] > 0]
        raise ValueError(f"cycle among: {stuck}")
    return order

On the degree plan above, run on Python 3.13, it prints ['Intro', 'DS', 'OS', 'Algo', 'DBMS', 'Networks', 'Capstone']. Adding the bad edge Capstone to DS makes it raise cycle among: ['DS', 'Algo', 'DBMS', 'Capstone']. Notice that Networks and OS are not in that list: they were peeled off normally, and only the cycle plus everything stuck behind it is reported.

03The DFS version: reverse finishing order

In a DFS, a node is appended after all its descendants finish, so reversing that finishing list gives a topological order; meeting a gray node means a cycle.

The second classic method needs no in-degree table. Run a depth-first search from every unvisited node. Append a node to a list only after all of its outgoing neighbours are fully explored. Reverse the list at the end.

Why it works: when node u finishes, everything reachable from u has already finished and sits earlier in the list. After reversing, u comes before all of them, which is what every edge from u asks for.

Cycle detection uses three colours. White means unvisited, gray means on the current recursion path, black means finished. An edge to a gray node is a back edge, and a back edge is a cycle.

def dfs_topo(courses, prereqs):
    out = defaultdict(list)
    for a, b in prereqs:
        out[a].append(b)
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {c: WHITE for c in courses}
    post = []
    def visit(u):
        color[u] = GRAY
        for v in out[u]:
            if color[v] == GRAY:
                raise ValueError(f"cycle through {u} -> {v}")
            if color[v] == WHITE:
                visit(v)
        color[u] = BLACK
        post.append(u)
    for c in courses:
        if color[c] == WHITE:
            visit(c)
    return post[::-1]

On the same plan it returns ['Intro', 'OS', 'Networks', 'DS', 'DBMS', 'Algo', 'Capstone'], a different but equally valid order. With the bad edge it raises cycle through Capstone -> DS. Both functions are the same graph with two valid answers, which is the point: do not write tests that compare against one exact order.

04Complexity and how I checked correctness

Both algorithms run in O(V + E) time and O(V) extra space, because each node and each edge is handled a constant number of times.

Kahn's version touches each node once when it is queued and each edge once when it is relaxed, so the cost is O(V + E). The DFS version visits each node once and scans each adjacency list once, also O(V + E). Extra memory is O(V) for the in-degree table or colour map, the queue or recursion stack, and the output.

To check the code rather than trust it, I generated 1,000 random DAGs (2 to 30 nodes, built by shuffling the nodes and adding forward edges with probability 0.15), ran both functions, and asserted that every edge goes forward in the result and that every node appears once. All 1,000 passed. That test checks the property, not a fixed answer, and it is the right way to test any topological sort.

One practical limit: the recursive DFS hits Python's default recursion limit of 1,000 frames on a dependency chain that long. For deep graphs use Kahn's algorithm or an explicit stack.

05Where topological sort is used

Build systems, package managers, spreadsheet recalculation and job schedulers all order work with it, and the same cycle check rejects circular dependencies.

Build tools such as make order compilation so a file is built after the files it includes. Package managers resolve install order. A spreadsheet recalculates cells in an order where every formula runs after the cells it reads, and a circular reference is the cycle error you see. Workflow schedulers such as Airflow describe jobs as a DAG and run a task once its upstream tasks finish.

Python ships this in the standard library as graphlib.TopologicalSorter, which raises CycleError on a cycle and also supports running independent nodes in parallel through prepare(), get_ready() and done(). In an interview you write it by hand. In a project you would usually call the library.

A useful variation: process Kahn's queue in levels (all current zero in-degree nodes at once). The number of levels is the length of the longest dependency chain, and nodes within one level can run in parallel.

06Mistakes and variations

Common slips are forgetting isolated nodes, comparing against one hard-coded order, and assuming a unique answer; lexicographically smallest order needs a heap instead of a queue.

Isolated nodes with no edges must still be in the node list you iterate, otherwise they vanish from the output. Build in-degrees from the full node set, not just from edge endpoints.

If the question asks for the lexicographically smallest valid order, swap the queue in Kahn's algorithm for a min-heap. The queue gives any valid order, the heap gives the smallest one at every choice.

If the question asks how many valid orders exist, there is no simple formula in general. Counting linear extensions of a DAG is a hard problem (it is #P-complete as far as I know), so interview versions use tiny inputs or ask only whether one exists.

Finally, topological order only exists for directed graphs. An undirected edge has no direction to respect.

07Common interview questions

Expect questions on existence, the two algorithms, cycle detection, complexity, uniqueness and real uses; answer each with the in-degree or finishing-order argument.

Q: When does a topological order exist?
A: Exactly when the directed graph has no cycle, that is, when it is a DAG.

Q: How does Kahn's algorithm detect a cycle?
A: If the output holds fewer nodes than the graph, some nodes never reached in-degree zero, so a cycle exists.

Q: How does the DFS approach detect a cycle?
A: An edge to a node that is still on the recursion stack (gray) is a back edge, which closes a cycle.

Q: What is the time and space complexity?
A: O(V + E) time and O(V) extra space for both.

Q: Is the order unique?
A: Only if the graph has a Hamiltonian path through the DAG, meaning every consecutive pair is joined by an edge. Otherwise several orders are valid.

Q: How do you get the smallest order lexicographically?
A: Use a min-heap instead of a queue for the zero in-degree nodes.

Up next · step 14 of 16

Dijkstra's Shortest Path

Dijkstra finds cheapest paths from one source in graphs with non-negative weights, in O((V+E) log V) with a heap. Run output, a negative-edge failure and timings on graphs up to 400k nodes.

Previous: Backtracking: Search by Trying and Undoing