Topological Sort in Python: Course Schedule (Kahn & DFS)

Topological sort is the graph technique behind every problem that says “do X before Y”: course prerequisites, build systems, task schedulers and package installers. If you have ever tried LeetCode’s Course Schedule and wondered why the solution talks about indegrees and cycles instead of just looping over courses, this guide is for you. You will learn what topological sort in Python really does, how to solve Course Schedule (207) and Course Schedule II (210) with both Kahn’s algorithm and DFS, and how to extend the same idea to harder variations such as minimum semesters, the smallest valid order and the Alien Dictionary.

Every code block below was run and checked against small examples, plus a randomised test that compared both approaches on thousands of random graphs. The explanations come first and the code second, so you understand why each line exists.

Quick answer

• A topological sort orders the nodes of a directed acyclic graph (DAG) so that every edge points from an earlier node to a later node.
• If the graph contains a cycle, no valid order exists.
• Kahn’s algorithm (BFS with indegrees) repeatedly removes nodes with no remaining prerequisites. If you cannot remove all nodes, there is a cycle.
• DFS marks nodes as unvisited, visiting or done. Meeting a node that is still visiting means a cycle.
• Both run in O(V + E) time and O(V + E) space.

What is topological sort?

A directed graph has nodes and one-way edges. In a prerequisite problem, each course is a node and each prerequisite is an edge from the course you must take first to the course that depends on it. A topological order is a list of all nodes in which every edge goes forward: if course A is a prerequisite of course B, then A appears before B.

Take five courses numbered 0 to 4. Course 1 and course 2 both need course 0. Course 3 needs both 1 and 2. Course 4 needs course 3. The order 0, 1, 2, 3, 4 works. So does 0, 2, 1, 3, 4, because courses 1 and 2 do not depend on each other. That is an important point: a topological order is usually not unique, so a correct solution may legitimately differ from the sample output.

A topological order exists only for a directed acyclic graph. If course 0 needs course 1 and course 1 needs course 0, you can never start either one. Detecting that situation is half of every Course Schedule problem, and it is why “can I finish all courses?” and “does this graph have a cycle?” are the same question.

How to spot a topological sort problem

Look for these signals in the problem statement:

• Tasks, courses, jobs or modules with dependencies or prerequisites.
• A question asking whether everything can be completed or whether a valid ordering exists.
• Words such as “before”, “after”, “precedence” or “depends on”.
• A request for the minimum number of rounds when independent tasks can run in parallel.
• Rules between pairs of items that you must merge into one global order, as in the Alien Dictionary.

If you see these, model the items as nodes, the rules as directed edges, and think about indegrees. If you are still building comfort with graph traversal, review our guide to tree and graph traversals with DFS and BFS first, because topological sort is built on exactly those two traversals.

Build the graph correctly

The single most common bug in Course Schedule solutions is getting the edge direction wrong. LeetCode gives each prerequisite as a pair [a, b], which means to take course a you must first take course b. The dependency flows from b to a, so the edge is b -> a.

We store the graph as an adjacency list, where graph[b] holds every course that becomes available after b. We also count the indegree of each node, which is the number of prerequisites still unfinished. A node with indegree 0 has nothing blocking it.

from collections import defaultdict, deque

graph = defaultdict(list)
indegree = [0] * num_courses
for course, prereq in prerequisites:
    graph[prereq].append(course)   # edge: prereq -> course
    indegree[course] += 1

If you want a refresher on why deque is the right queue in Python, see the Python cheat sheet for coding interviews, which also lists the cost of each built-in.

Approach 1: Kahn’s algorithm (BFS)

Kahn’s algorithm works like a student who takes every course that is currently available. Start with all courses that have indegree 0. Take one, then imagine it is finished: every course that depended on it now has one fewer unfinished prerequisite, so reduce its indegree by one. Whenever a course reaches indegree 0, it becomes available and joins the queue. Repeat until the queue is empty.

Here is the full trace for our five-course example with edges [[1,0],[2,0],[3,1],[3,2],[4,3]]. The starting indegrees are [0, 1, 1, 2, 1].

All five courses left the queue, so the order is valid and no cycle exists. Now see what happens with a cycle: courses 0, 1 and 2 where [[1,0],[2,1],[0,2]]. Every course has indegree 1, so the queue starts empty. Nothing can be taken, and zero of three courses are processed. That mismatch is exactly how Kahn’s algorithm detects a cycle: if the number of processed nodes is smaller than the number of nodes, some nodes were stuck in or behind a cycle.

Course Schedule (LeetCode 207)

The problem: given numCourses and a list of prerequisite pairs, return True if you can finish all courses. We only need to know whether a valid order exists, so we count how many courses we manage to take.

from collections import defaultdict, deque


def can_finish(num_courses, prerequisites):
    graph = defaultdict(list)
    indegree = [0] * num_courses
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        indegree[course] += 1

    queue = deque(c for c in range(num_courses) if indegree[c] == 0)
    taken = 0
    while queue:
        node = queue.popleft()
        taken += 1
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
    return taken == num_courses


print(can_finish(2, [[1, 0]]))          # True
print(can_finish(2, [[1, 0], [0, 1]]))  # False
print(can_finish(1, [[0, 0]]))          # False (a course cannot require itself)

The outputs are True, False and False. Notice that a self-loop such as [0, 0] is handled for free, because course 0 can never reach indegree 0.

Course Schedule II (LeetCode 210)

Course Schedule II asks for an actual valid order, or an empty list when none exists. Kahn’s algorithm already produces one: the order in which nodes leave the queue is a valid topological order. We only need to record each node as we pop it.

def find_order(num_courses, prerequisites):
    graph = defaultdict(list)
    indegree = [0] * num_courses
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        indegree[course] += 1

    queue = deque(c for c in range(num_courses) if indegree[c] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
    return order if len(order) == num_courses else []


print(find_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]]))  # [0, 1, 2, 3]
print(find_order(2, [[1, 0], [0, 1]]))                  # []

The first call prints [0, 1, 2, 3] and the second prints []. Courses 1 and 2 are interchangeable, so [0, 2, 1, 3] would be equally correct. Interviewers usually accept any valid order, but if you are unsure, ask. The line len(order) == num_courses is the same cycle check as before, written differently.

Approach 2: DFS with three states

The DFS method is a different way of seeing the same structure. A course can only be placed in the order after everything that depends on it has been placed, so we place nodes in post-order and reverse the result at the end.

To detect cycles we give each node one of three states:

• Unvisited (0): we have not touched it yet.
• Visiting (1): it is on the current DFS path. We have entered it but not finished all of its descendants.
• Done (2): it and everything reachable from it is finished.

If, while exploring from a node, we meet a neighbour whose state is visiting, we have walked back onto our own path, which means a cycle. Meeting a done node is harmless, because that part of the graph is already settled.

def find_order_dfs(num_courses, prerequisites):
    graph = [[] for _ in range(num_courses)]
    for course, prereq in prerequisites:
        graph[prereq].append(course)

    UNVISITED, VISITING, DONE = 0, 1, 2
    state = [UNVISITED] * num_courses
    post = []

    def dfs(node):
        state[node] = VISITING
        for nxt in graph[node]:
            if state[nxt] == VISITING:
                return False          # back edge: cycle
            if state[nxt] == UNVISITED and not dfs(nxt):
                return False
        state[node] = DONE
        post.append(node)
        return True

    for course in range(num_courses):
        if state[course] == UNVISITED and not dfs(course):
            return []
    return post[::-1]


print(find_order_dfs(4, [[1, 0], [2, 0], [3, 1], [3, 2]]))  # [0, 2, 1, 3]
print(find_order_dfs(2, [[1, 0], [0, 1]]))                  # []

On the same four-course input, DFS prints [0, 2, 1, 3] while Kahn’s algorithm printed [0, 1, 2, 3]. Both are valid. This is a good example of why you should verify an order by checking every prerequisite pair rather than comparing it to a sample answer.

There is one practical trap. LeetCode’s constraints allow up to 2000 courses, and a single chain of 2000 courses makes the recursion 2000 calls deep. When I ran this exact function on such a chain with Python’s default recursion limit of 1000, it raised a RecursionError, while Kahn’s algorithm handled the same input without trouble. In an interview you can either raise the limit with sys.setrecursionlimit or, more safely, prefer Kahn’s algorithm.

Kahn’s algorithm vs DFS

My suggestion for interviews is to memorise Kahn’s algorithm first. It has no recursion limit problem, the cycle check is one comparison, and it extends naturally to level-by-level and priority-based versions. Learn the DFS version as a second tool, especially if you are comfortable with the traversal ideas from our backtracking guide, where states and path tracking also matter.

Time and space complexity

Let V be the number of courses and E the number of prerequisite pairs.

• Time: O(V + E). Building the graph touches every edge once. Each node enters the queue at most once, and each edge is examined once when its source node is processed.
• Space: O(V + E). The adjacency list stores every edge, and the indegree array, queue and result list store at most V items each.

If you want to practise stating complexity out loud, our Big O notation guide walks through how to count loops and hidden costs. For the graph in a Course Schedule problem, saying “linear in courses plus prerequisites” is precise and complete.

Variations: semesters, smallest order and Alien Dictionary

Once Kahn’s algorithm feels natural, a whole family of problems becomes small edits to the same template.

Minimum number of semesters (parallel courses)

Suppose you can take any number of available courses in one semester, and you want the minimum number of semesters. Instead of popping one node at a time, process the whole current level together. Each level of Kahn’s algorithm is one semester. If you cannot take every course, return -1.

def minimum_semesters(n, relations):
    # courses are labelled 1..n, relations are [prev, next]
    graph = defaultdict(list)
    indegree = [0] * (n + 1)
    for prev, nxt in relations:
        graph[prev].append(nxt)
        indegree[nxt] += 1

    current = [c for c in range(1, n + 1) if indegree[c] == 0]
    semesters = 0
    done = 0
    while current:
        semesters += 1
        next_level = []
        for node in current:
            done += 1
            for nxt in graph[node]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    next_level.append(nxt)
        current = next_level
    return semesters if done == n else -1


print(minimum_semesters(3, [[1, 3], [2, 3]]))           # 2
print(minimum_semesters(3, [[1, 2], [2, 3], [3, 1]]))   # -1

The first call returns 2 because courses 1 and 2 can be taken together in semester one and course 3 follows in semester two. The second returns -1 because of the cycle. The number of levels equals the length of the longest dependency chain.

Lexicographically smallest valid order

If the problem asks for the smallest order, replace the plain queue with a min-heap so that, among all available nodes, you always take the smallest label. The heap guide explains heapq in detail. The runtime becomes O(V log V + E) because every push and pop costs a logarithm.

import heapq


def smallest_order(n, edges):
    graph = defaultdict(list)
    indegree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    heap = [c for c in range(n) if indegree[c] == 0]
    heapq.heapify(heap)
    order = []
    while heap:
        node = heapq.heappop(heap)
        order.append(node)
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                heapq.heappush(heap, nxt)
    return order if len(order) == n else []


print(smallest_order(4, [[3, 0], [1, 0], [2, 1]]))  # [2, 1, 3, 0]
print(smallest_order(3, [[0, 1], [1, 0]]))          # []

Alien Dictionary

In this classic problem you receive words sorted in an unknown alphabet and must recover a valid letter order. Compare each pair of adjacent words, find the first position where their letters differ, and add an edge from the first word’s letter to the second word’s letter. Then run Kahn’s algorithm on the letters. Remember one edge case: if a longer word appears before its own prefix, such as abc before ab, the input is invalid and the answer is empty.

def alien_order(words):
    graph = {c: set() for w in words for c in w}
    indegree = {c: 0 for c in graph}
    for a, b in zip(words, words[1:]):
        if len(a) > len(b) and a.startswith(b):
            return ''
        for x, y in zip(a, b):
            if x != y:
                if y not in graph[x]:
                    graph[x].add(y)
                    indegree[y] += 1
                break

    queue = deque(c for c in indegree if indegree[c] == 0)
    out = []
    while queue:
        c = queue.popleft()
        out.append(c)
        for nxt in graph[c]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
    return ''.join(out) if len(out) == len(graph) else ''


print(alien_order(['wrt', 'wrf', 'er', 'ett', 'rftt']))  # wertf
print(alien_order(['z', 'x']))                           # zx
print(alien_order(['abc', 'ab']))                        # (empty string)

The three calls print wertf, zx and an empty string. The if y not in graph[x] check prevents counting the same edge twice, which would corrupt the indegree.

Common mistakes

• Reversing the edge direction. For [a, b] the edge goes from b to a. If your first example fails, check this before anything else.
• Forgetting disconnected courses. Courses with no prerequisites and no dependents must still appear in the final order. Starting the queue with every indegree-0 node, or looping over all nodes in DFS, handles this.
• Comparing against the sample answer. Many valid orders exist. Validate by checking that each prerequisite appears earlier.
• Marking a node done too early in DFS. If you only keep a visited set, you cannot tell a harmless revisit from a back edge. Use the visiting state.
• Hitting the recursion limit. A long chain can crash recursive DFS in Python. Prefer Kahn’s algorithm or increase the limit deliberately.
• Counting duplicate edges. If the input can repeat an edge, either de-duplicate it, as in the Alien Dictionary code, or make sure indegree and adjacency stay consistent.
• Returning True without checking the count. The whole cycle check is processed == total. Leaving it out makes every graph look valid.

How to explain it in an interview

A clear script beats a silent perfect solution. Try this structure:

1. Restate and model. “Each course is a node and each prerequisite is a directed edge. I need to know whether the graph has a cycle.”
2. Name the technique. “This is a topological sort. I will use Kahn’s algorithm with indegrees.”
3. Describe the loop. “I take every course with no remaining prerequisites, lower the indegree of its dependents and repeat.”
4. State the cycle rule. “If I finish fewer courses than numCourses, a cycle blocked the rest.”
5. Give complexity. “O(V + E) time and space.”
6. Test an edge case. A self-loop, an empty prerequisite list and two independent courses are all quick checks.

This structure also works for every variation above, because only step 3 changes.

Practice problems

Work through these in order. Each one adds a small twist to the template.

1. Course Schedule (207): detect a cycle with Kahn’s algorithm.
2. Course Schedule II (210): return the order.
3. Course Schedule IV (1462): answer reachability queries between courses.
4. Minimum Height Trees (310): peel leaves layer by layer, which is Kahn’s idea on an undirected tree.
5. Find All Possible Recipes from Given Supplies (2115): recipes are nodes, ingredients are dependencies.
6. Longest Increasing Path in a Matrix (329): topological order on a grid, or DFS with memoization.
7. Alien Dictionary (269): often locked behind Premium on LeetCode, but widely available on other practice sites.

If you are planning your overall preparation, the LeetPrep roadmap shows where graph problems fit, and our guide on how many LeetCode problems you should solve explains how many graph problems you need before moving on.

Frequently asked questions

Final thoughts

Topological sort looks like a special topic, but it is really one small idea used repeatedly: take what is ready, release what depended on it, and check whether everything got released. Learn Kahn’s algorithm until you can write it from memory, practise the level-by-level and heap variations, and keep DFS cycle detection as a backup. Solve Course Schedule and Course Schedule II without looking, then try the Alien Dictionary. If a graph problem still confuses you, send it through the contact page and we will consider writing a guide about it.

Keep learning: tree and graph traversals, heaps and how many problems to solve build on the ideas in this guide.

Also see: Dijkstra’s algorithm and Union-Find for related patterns.