Topological Sort: Kahn's Algorithm, DFS and Worked Problems

A topological sort orders the nodes of a directed graph so that every edge u → v puts u before v; it exists only when the graph has no cycle (a DAG). Reach for it when a problem talks about prerequisites, dependencies, build order or "X must happen before Y," or asks whether such an order is even possible.

There are two standard ways to do it, and interviewers accept either: Kahn's algorithm (BFS that repeatedly removes nodes with no incoming edges) and DFS (reverse post-order with cycle detection). Both run in O(V + E). This guide gives you both templates in Python, three worked LeetCode problems and a practice list. Every snippet below was run against test cases before we published it.

When to use topological sort

• Prerequisites or dependencies. Courses, build steps, package installs, recipes that need other recipes.
• "Is it possible to finish?" That is cycle detection in a directed graph, and topological sort answers it as a side effect.
• "Return a valid order." Any order that respects every edge is accepted; many problems say so explicitly.
• Order hidden in examples. Alien Dictionary gives sorted words; comparing neighbors produces "letter a comes before letter b" edges.
• Longest or earliest-finish path in a DAG. Processing nodes in topological order lets you run a simple DP over the graph (Parallel Courses III below).

If the graph is undirected, or you need shortest paths by edge count, you want BFS instead; the graph algorithms guide covers BFS, DFS and Course Schedule (LeetCode 207), and BFS vs DFS explains when to use each.

Kahn's algorithm vs DFS topological sort

If you only learn one, learn Kahn's. It has no recursion-depth risk, its cycle check is one comparison, and it extends naturally to "minimum number of semesters" and earliest-finish problems.

Topological sort template: Kahn's algorithm in Python

from collections import deque

def topo_sort_kahn(n, edges):          # edge (u, v) means u must come before v
    graph = [[] for _ in range(n)]
    indegree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1
    queue = deque(i for i in range(n) if indegree[i] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:     # all prerequisites done
                queue.append(nxt)
    return order if len(order) == n else []   # shorter means a cycle

Every node enters the queue once and every edge is relaxed once, so this is O(V + E). Nodes on a cycle never reach in-degree 0, which is why a short output proves a cycle exists.

Worked problems

1. Course Schedule II (LeetCode 210, Medium) with DFS

Problem: prerequisites[i] = [a, b] means you must take course b before course a. Return any valid order, or an empty list if it is impossible. See Course Schedule II.

Idea: the pair is [a, b] but the edge is b → a. Getting that direction wrong is the most common bug here. This version uses the DFS approach so you have both templates: color each node white (unvisited), gray (on the current path) or black (finished). Meeting a gray node means a cycle.

import sys

def find_order(num_courses, prerequisites):
    sys.setrecursionlimit(max(1000, 2 * num_courses + 10))
    graph = [[] for _ in range(num_courses)]
    for a, b in prerequisites:
        graph[b].append(a)                 # take b before a
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * num_courses
    order = []

    def dfs(node):
        color[node] = GRAY                 # on the current path
        for nxt in graph[node]:
            if color[nxt] == GRAY:         # back edge: a cycle
                return False
            if color[nxt] == WHITE and not dfs(nxt):
                return False
        color[node] = BLACK
        order.append(node)                 # post-order: after all dependents
        return True

    for course in range(num_courses):
        if color[course] == WHITE and not dfs(course):
            return []
    return order[::-1]                     # reverse post-order

Time: O(V + E). Space: O(V + E) for the graph plus recursion depth up to V. The constraints allow 2,000 courses, so a single chain would pass Python's default recursion limit of 1,000; that is why the limit is raised. In an interview, mention it, or switch to Kahn's.

2. Find All Possible Recipes from Given Supplies (LeetCode 2115, Medium)

Problem: each recipe needs a list of ingredients, and an ingredient can itself be a recipe. You have unlimited supplies of some base items. Return every recipe you can make.

Idea: Kahn's algorithm on strings. A recipe's in-degree is the number of ingredients it still needs. Start the queue with the supplies; each time an item becomes available, lower the count of every recipe that uses it. Recipes stuck in a cycle, or that need an item nobody has, never reach zero.

from collections import defaultdict, deque

def find_all_recipes(recipes, ingredients, supplies):
    users = defaultdict(list)          # ingredient -> recipes that need it
    missing = {}
    for recipe, needs in zip(recipes, ingredients):
        missing[recipe] = len(needs)
        for item in needs:
            users[item].append(recipe)
    queue = deque(supplies)            # items we already have
    made = []
    while queue:
        item = queue.popleft()
        for recipe in users[item]:
            missing[recipe] -= 1
            if missing[recipe] == 0:   # every ingredient is available
                made.append(recipe)
                queue.append(recipe)   # it can now feed other recipes
    return made

Time: O(R + I + S), where I is the total number of ingredient entries. Space: O(R + I + S). No explicit node numbering is needed; a dictionary is the graph.

3. Parallel Courses III (LeetCode 2050, Hard)

Problem: courses 1..n each take time[i - 1] months, any number can run at once, and [prev, next] means prev must finish first. The graph is guaranteed to be a DAG. Return the minimum months to finish everything.

Idea: a course's earliest finish is its own time plus the latest finish among its prerequisites. Kahn's order guarantees every prerequisite is final before a course is popped, so a one-line DP update on each edge solves it. The answer is the longest weighted path in the DAG.

from collections import deque

def minimum_time(n, relations, time):
    graph = [[] for _ in range(n + 1)]
    indegree = [0] * (n + 1)
    for prev, nxt in relations:
        graph[prev].append(nxt)
        indegree[nxt] += 1
    finish = [0] * (n + 1)             # earliest finish month per course
    queue = deque()
    for course in range(1, n + 1):
        if indegree[course] == 0:
            finish[course] = time[course - 1]
            queue.append(course)
    while queue:
        course = queue.popleft()
        for nxt in graph[course]:
            finish[nxt] = max(finish[nxt], finish[course] + time[nxt - 1])
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
    return max(finish)

Time: O(n + E). Space: O(n + E). The same "DP in topological order" shape solves longest path in a DAG, critical-path scheduling and Longest Increasing Path in a Matrix (LeetCode 329).

Topological sort complexity table

To see what O(V + E) means next to O(V²) on a dense graph, try the Big-O complexity visualizer.

Common bugs and edge cases

• Reversed edges. Decide what "u before v" means in the input and write it as a comment before you code. Course Schedule's [a, b] is b → a.
• Two-color DFS. A plain visited set cannot tell "on my current path" (a cycle) from "finished earlier" (fine). You need three states.
• Forgetting isolated nodes. Nodes with no edges still belong in the order. Seed the queue from every node, not just nodes that appear in the edge list.
• Not checking the output length. Kahn's returns a partial order when there is a cycle. Compare len(order) to n.
• Duplicate edges (Alien Dictionary can produce them). If you add an edge twice, increment the in-degree twice too, or deduplicate with a set.
• Recursion depth in Python on long chains. Raise the limit or use Kahn's.

Practice list: 8 topological sort problems

Difficulty labels are LeetCode's own, checked as of October 2026.

Related patterns: union-find detects cycles in undirected graphs, Dijkstra's algorithm handles weighted shortest paths, and 15 LeetCode patterns for interviews shows where topological sort fits overall. Keep the coding interview cheat sheet open while you practice.

How to practice topological sort

Solve Course Schedule II twice, once with Kahn's and once with DFS, without looking at the templates. Then explain out loud how each version detects a cycle and why both are O(V + E). That explanation is what interviewers listen for.

CoPilot Interview's Mock Interview can run a coding round from your résumé and the job description and score each spoken answer out of 10, with what to fix and a model answer. The browser AI mock interview needs no install and includes coding and system design tracks.

FAQ

What is topological sort?

Topological sort is an ordering of the nodes in a directed acyclic graph so that for every edge u to v, u comes before v. It is used for scheduling with prerequisites, build order and dependency resolution. A graph with a cycle has no topological order.

What is the difference between Kahn's algorithm and DFS topological sort?

Kahn's algorithm is BFS-based: it repeatedly removes nodes with in-degree 0 and detects a cycle when fewer than V nodes come out. The DFS version adds each node after all its descendants finish and reverses that order, detecting a cycle when it reaches a node still on the current path. Both are O(V + E).

What is the time complexity of topological sort?

O(V + E) time and O(V + E) space for both Kahn's algorithm and the DFS version, because each node and each edge is processed once. Using a min-heap instead of a queue to get the lexicographically smallest order adds a log V factor.

How does topological sort detect a cycle?

In Kahn's algorithm, nodes on a cycle never reach in-degree 0, so the output has fewer than V nodes. In DFS, you color nodes white, gray and black; finding an edge to a gray node, which is still on the current recursion path, means a cycle.

Is a topological order unique?

Not usually. Any order that respects every edge is valid, which is why problems like Course Schedule II accept any correct answer. The order is unique only when every consecutive pair in it is joined by an edge, so the order forms a single path through the graph.

Which LeetCode problems use topological sort?

Course Schedule (207), Course Schedule II (210), Course Schedule IV (1462), Find All Possible Recipes from Given Supplies (2115), Parallel Courses III (2050), Minimum Height Trees (310), Longest Increasing Path in a Matrix (329) and Alien Dictionary (269, LeetCode Premium).