Kahn's Algorithm: BFS Topological Sort
Compute in-degrees for all nodes, enqueue zero-in-degree nodes, and process the queue to produce a topological order while detecting cycles.
Kahn's Algorithm: BFS Topological Sort is a free Coding Interview Prep lesson on CoddyKit. This is lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, and your progress syncs across the web and the CoddyKit app. The Coding Interview Prep course includes 4 lessons in total.
What Is Topological Sort?
A topological sort of a Directed Acyclic Graph (DAG) is an ordering of its nodes such that every directed edge u → v means u comes before v in the ordering. It represents a valid execution order for tasks with dependencies — like build systems, course scheduling, or package management. Only DAGs have valid topological orderings; a cycle makes it impossible.
Kahn's Algorithm: Core Idea
Kahn's Algorithm is a BFS-based approach to topological sort. The key insight: a node with in-degree 0 (no prerequisites) can be placed first in the ordering. After placing it, remove it and decrement the in-degree of its neighbours. New zero-in-degree nodes become available. Repeat until all nodes are placed or a cycle is detected (nodes remain with non-zero in-degree).
In-Degree Computation
First, build the adjacency list and compute the in-degree (number of incoming edges) for each node. Nodes with in-degree 0 are the starting points — they have no dependencies. For a graph with edges [(0,1),(0,2),(1,3),(2,3)], in-degrees are: 0→0, 1→1, 2→1, 3→2. Only node 0 starts with in-degree 0.
from collections import deque, defaultdict
def compute_in_degree(n, edges):
in_degree = [0] * n
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
return graph, in_degree
graph, ind = compute_in_degree(4, [(0,1),(0,2),(1,3),(2,3)])
print('In-degrees:', ind) # [0, 1, 1, 2]Kahn's Algorithm Implementation
Enqueue all zero-in-degree nodes into a queue. Process each node: add it to the result, then for each neighbour decrement its in-degree and enqueue it if it reaches 0. If the result list has fewer nodes than the graph, a cycle exists — some nodes could never be dequeued.
from collections import deque, defaultdict
def kahn_topological_sort(n, edges):
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque(i for i in range(n) if in_degree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
if len(order) == n:
return order # valid topological sort
return [] # cycle detected
print(kahn_topological_sort(4, [(0,1),(0,2),(1,3),(2,3)]))Cycle Detection via Kahn's
Kahn's algorithm provides free cycle detection: if len(order) < n, some nodes were never added to the queue because their in-degree never reached 0 — they are part of a cycle. This is cleaner than maintaining a colour-coded visited array. Return an empty list to signal a cycle exists.
# Cyclic graph: 0->1->2->0
edges_cycle = [(0,1),(1,2),(2,0)]
result = kahn_topological_sort(3, edges_cycle)
print(result) # [] (cycle detected)
# Acyclic graph
edges_dag = [(0,1),(1,2)]
result = kahn_topological_sort(3, edges_dag)
print(result) # [0, 1, 2]Time and Space Complexity
Kahn's algorithm processes each node once (dequeued once) and each edge once (in-degree decremented once). Time complexity: O(V + E). Space: O(V + E) for the adjacency list and in-degree array plus O(V) for the queue. This is optimal — you must at minimum read all nodes and edges to produce a valid ordering.
Lexicographically Smallest Topological Order
Kahn's algorithm with a min-heap instead of a queue produces the lexicographically smallest topological order. Replace deque with heapq: push (node) and always process the smallest available node first. This guarantees the lex-smallest valid ordering among all possible topological sorts.
import heapq
from collections import defaultdict
def kahn_lex_order(n, edges):
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
heap = [i for i in range(n) if in_degree[i] == 0]
heapq.heapify(heap)
order = []
while heap:
node = heapq.heappop(heap)
order.append(node)
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
heapq.heappush(heap, nxt)
return order if len(order) == n else []
print(kahn_lex_order(6, [(5,2),(5,0),(4,0),(4,1),(2,3),(3,1)]))Application: Course Schedule I
Course Schedule (LeetCode 207): given n courses and prerequisites, can you finish all courses? Model prerequisites as directed edges and check if a valid topological sort exists (i.e., no cycle). Return True if Kahn's produces an order of length n, False if a cycle is detected.
from collections import deque, defaultdict
def canFinish(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites: # b must be taken before a
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
count = 0
while queue:
node = queue.popleft()
count += 1
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return count == numCourses
print(canFinish(2, [[1,0]])) # True
print(canFinish(2, [[1,0],[0,1]])) # False (cycle)Application: Course Schedule II
Course Schedule II (LeetCode 210): return the actual order in which to take courses. Same as above but return the order list instead of a boolean. If a cycle exists, return an empty list. This directly uses the Kahn's output as the answer.
from collections import deque, defaultdict
def findOrder(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return order if len(order) == numCourses else []
print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))Parallel Task Scheduling
A more advanced use: given tasks with dependencies, find the minimum number of 'rounds' needed if tasks with no dependencies can run in parallel. Process Kahn's level by level (similar to BFS level-order): enqueue all zero-in-degree nodes, process the entire current queue as one round, then enqueue newly freed nodes as the next round. Count rounds.
from collections import deque, defaultdict
def min_rounds(n, edges):
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque(i for i in range(n) if in_degree[i] == 0)
rounds = 0
while queue:
rounds += 1
for _ in range(len(queue)): # process current level
node = queue.popleft()
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return rounds
print(min_rounds(4, [(0,2),(1,2),(2,3)])) # 3Topological Sort and DP on DAGs
Topological sort enables dynamic programming on DAGs: process nodes in topological order, and when computing dp[v], all predecessors dp[u] are already final. This combines topological sort with DP for problems like longest path in a DAG, minimum cost to reach all nodes, or maximum profit from a dependency chain. The ordering guarantees that each node's DP value is computed exactly once after all its dependencies.
from collections import deque, defaultdict
def longest_path_dag(V, edges):
graph = defaultdict(list)
in_degree = [0] * V
for u, v, w in edges:
graph[u].append((v, w))
in_degree[v] += 1
queue = deque(i for i in range(V) if in_degree[i] == 0)
dp = [0] * V
while queue:
u = queue.popleft()
for v, w in graph[u]:
dp[v] = max(dp[v], dp[u] + w)
in_degree[v] -= 1
if in_degree[v] == 0: queue.append(v)
return max(dp)
print(longest_path_dag(4, [(0,1,3),(0,2,2),(1,3,4),(2,3,1)])) # 7Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: Kahn's algorithm computes topological sort by iteratively removing zero-in-degree nodes with BFS, cycle detection is free — if len(order) < n, a cycle exists, and replacing the queue with a min-heap gives the lexicographically smallest topological order. Next up we explore DFS-based post-order topological sort as an alternative to Kahn's.
Learn Coding Interview Prep with an AI tutor — free
Write and run real code in your browser, get instant help from a 24/7 AI tutor, and pick up where you left off on the web or in the app.
- Courses
- 90
- Lessons
- 360
Frequently Asked Questions
Is the “Kahn's Algorithm: BFS Topological Sort” lesson free?
Yes — the full text of “Kahn's Algorithm: BFS Topological Sort” is free to read here on the web. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO. The Coding Interview Prep course includes 4 lessons in total.
What will I learn in “Kahn's Algorithm: BFS Topological Sort”?
Compute in-degrees for all nodes, enqueue zero-in-degree nodes, and process the queue to produce a topological order while detecting cycles. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners, so you can start here or from the beginning and move at your own pace. This is lesson 1 of 4.
How long does the “Kahn's Algorithm: BFS Topological Sort” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Kahn's Algorithm: BFS Topological Sort
- DFS Post-Order Topological Sort
- Course Schedule I and II
- Strongly Connected Components with Kosaraju