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 DSA Interview Prep lesson on CoddyKit — 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 DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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.
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, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
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 DSA 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 DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.
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 DSA Interview Prep lesson?
Yes. Every DSA 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