--- title: "Kahn's algorithm in Python: topological sort, step by step" url: https://algopath.pro/blog/kahns-algorithm-python language: en summary: "Kahn's algorithm sorts a directed graph by counting incoming edges. The code in Python, a trace you can follow by hand, the wording that tells you a problem wants it, and the three ways it breaks." updated: 2026-10-15 --- # Kahn's algorithm in Python: topological sort, step by step **Short answer.** Kahn's algorithm is a topological sort that counts incoming edges. Take every node with no incoming edges. Remove it and lower the counts of its neighbours. Repeat until nothing is left to remove. If some nodes never came out, the graph has a cycle. ## What does a topological sort do? It lines up the nodes of a directed graph. Every edge then points left to right. The everyday version is a course list with prerequisites. A topological order is an order you can take the courses in. It only exists for a graph without cycles. If A needs B and B needs A, there is no order. ## How does Kahn's algorithm work? Four steps, none of them hard. - Count the incoming edges of every node. That is its in-degree. - Put every node with in-degree 0 in a queue. - Pop a node and append it to the answer. Lower the in-degree of each neighbour by one. - A neighbour that reaches zero goes into the queue. Trace it on a graph with edges A→C, B→C, C→D. | Step | Queue | Popped | Answer | | --- | --- | --- | --- | | 0 | A, B | | | | 1 | B | A | A | | 2 | C | B | A, B | | 3 | D | C | A, B, C | | 4 | | D | A, B, C, D | C only entered the queue at step 2. Two edges led into it, and both had to go first. ## How do you write Kahn's algorithm in Python? The graph comes as an edge list. Nodes are numbered 0 to n-1. ``` from collections import deque def kahn(n, edges): graph = [[] for _ in range(n)] indegree = [0] * n for a, b in edges: graph[a].append(b) indegree[b] += 1 queue = deque(v for v in range(n) if indegree[v] == 0) order = [] while queue: v = queue.popleft() order.append(v) for w in graph[v]: indegree[w] -= 1 if indegree[w] == 0: queue.append(w) if len(order) != n: return None # the graph has a cycle return order ``` The cycle check is built in. A node on a cycle never reaches zero. So it never reaches the answer. Time is O(V + E). Every node is popped once and every edge is lowered once. ## When does a problem want Kahn's algorithm? The wording gives it away before you start thinking. - "Courses and prerequisites", "can you finish all courses". - "Build order", "package dependencies", "task scheduling". - "Return any valid order in which…". - "Detect a cycle in a directed graph". - "Recover the alphabet from a sorted list of words". The common thread is directed dependencies. The question is an order, or whether one exists. The signals, the near misses and six code templates are on the [topological sort pattern page](/patterns/topological-sort). ## How is Kahn's algorithm different from the DFS version? There are two ways to topologically sort. Both give a valid order. - Kahn starts from nodes with no incoming edges. The order is built front to back. - DFS goes deep and records a node on the way out. The result is reversed at the end. - Kahn finds a cycle by counting. DFS finds one by meeting a grey node. - Kahn gives you layers for free: nodes that could run in parallel. Interviewers usually expect Kahn. It is easier to explain out loud. That is half the score. ## How do you solve Course Schedule with Kahn's algorithm? The problem. There are n courses. Some pairs say "take b before a". Can you finish all of them? Read it as a graph. Each pair is an edge b→a. The question is whether the graph has a cycle. Run `kahn`. If it returns an order, the answer is yes. If it returns None, no. Course Schedule II asks for the order itself. Same code, return the list instead of a boolean. Trace a small case out loud: n = 3, pairs (1, 0) and (2, 1). In-degrees are 0, 1, 1. The queue starts with 0. Popping 0 frees 1, popping 1 frees 2. Order: 0, 1, 2. Now add the pair (0, 2). Every node has in-degree 1. The queue starts empty, the order is empty, the answer is no. ## How do you explain Kahn's algorithm in an interview? Three sentences, in this order, before any code. - "The prerequisites form a directed graph. I need a topological order." - "I count incoming edges and start from the nodes with none. Removing a node frees its neighbours." - "Every node and edge is touched once, so O(V + E). If the order is short, there is a cycle." Then the code. Then the trace above on three nodes. Say the complexity once more at the end. ## Where does Kahn's algorithm break? Three mistakes account for most wrong answers. - An edge read backwards. The order comes out mirrored and every test fails. - The `len(order) != n` check left out. A cyclic graph returns a short list and no error. - A list with `pop(0)` instead of a deque. That is O(n) per step. ## How do you make Kahn's algorithm stick? Write `kahn` from memory. Then solve Course Schedule and Course Schedule II. They are the same problem; the second asks for the order. A day later, write it again without looking. Why the gap matters is in the piece on [spaced repetition](/blog/spaced-repetition). Recognising the pattern from the wording is a separate skill. It is covered in [LeetCode patterns](/blog/leetcode-patterns). ## FAQ ### What is the time complexity of Kahn's algorithm? O(V + E) time and O(V + E) space for the adjacency list. ### What does Kahn's algorithm return on a graph with a cycle? A partial order. That is why the answer's length is compared with the node count. ### Is the topological order unique? No. Whenever two nodes sit in the queue, either can go first. Both orders are valid. ### Why a queue rather than a stack? A stack works too. The queue gives a layer-by-layer order. That is the one problems usually ask for.