Topological Sort with Kahn's Algorithm
Order tasks that depend on others.
Topological Sort with Kahn's Algorithm is a free Coding 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 Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
What Topological Order Is
A topological order lists every node of a directed graph so each edge points from earlier to later. Think tasks before the tasks that need them.
Only DAGs Allowed
This works only on a DAG, a directed acyclic graph. If a cycle exists, no valid order can ever satisfy every dependency.
The Indegree Idea
Kahn's algorithm leans on indegree: how many edges point into a node. A node with indegree zero has no unmet dependencies.
Count Every Indegree
First pass: walk all edges and count how many times each node is a destination. That gives you each node's indegree.
indeg = [0] * n
for u in range(n):
for v in adj[u]:
indeg[v] += 1Seed the Ready Queue
Every node with indegree zero is ready right away, so push them all into a queue to start.
from collections import deque
q = deque(u for u in range(n) if indeg[u] == 0)Process One Node
Pop a ready node and append it to your order. It is safe now because nothing left depends on it.
u = q.popleft()
order.append(u)Release Its Neighbors
For each neighbor, drop its indegree by one. When a neighbor hits zero, it becomes ready and joins the queue.
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)Repeat Until Empty
Keep popping and releasing until the queue empties. The order grows one safe node at a time until every node is placed.
Detect a Cycle for Free
If your final order holds fewer than n nodes, a cycle trapped the rest. Kahn's gives you cycle detection at no extra cost.
if len(order) < n:
print('cycle exists')The Running Time
Each node and edge is touched once, so Kahn's runs in O(V + E). That scales to graphs with millions of edges.
Many Valid Orders
When several nodes are ready at once, any of them can go next. So a DAG often has many valid topological orders, not just one.
Quick Check
You finish Kahn's algorithm but the order has fewer than n nodes. What does that mean?
Recap: Kahn's Algorithm
Count indegrees, queue the zeros, pop a node, decrement neighbors, and repeat. That is a clean topological sort in O(V+E). 🚀
Frequently asked questions
Is the “Topological Sort with Kahn's Algorithm” lesson free?
Yes — the full text of “Topological Sort with Kahn's Algorithm” is free to read here on the web, and the Coding 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 Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Topological Sort with Kahn's Algorithm”?
Order tasks that depend on others. 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; 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 “Topological Sort with Kahn's Algorithm” 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
- Topological Sort with Kahn's Algorithm
- Detect Cycles in Directed Graphs
- Strongly Connected Components
- Bridges & Articulation Points