Kahn's Algorithm: Implementation
What you'll learn: You'll see how to implement Kahn's algorithm step-by-step using a queue and in-degree tracking to perform topological sorting.
The Core Mechanics
Kahn's algorithm uses a queue (first-in, first-out) and an in-degree array to process vertices in topological order. The in-degree of a vertex is the number of incoming edges pointing to it—essentially, how many prerequisites it has.
Here's how it works:
- Initialize: Count the in-degree for every vertex. Add all vertices with in-degree 0 (no prerequisites) to the queue.
- Process: While the queue isn't empty:
- Remove a vertex from the queue (this is next in topological order)
- For each neighbor of this vertex, decrease its in-degree by 1 (we've "completed" one prerequisite)
- If any neighbor's in-degree becomes 0, add it to the queue
- Verify: If you've processed all vertices, you have a valid topological sort. If not, there's a cycle.
Why This Works
Think of it like taking college courses: you can only take a class once all its prerequisites are done (in-degree = 0). As you complete courses, you unlock new ones by satisfying their requirements. The queue ensures you process courses in a valid order.
The in-degree count acts like a checklist: "How many courses must I finish before taking this one?" When that count hits zero, you're ready to go.
Practical Notes
- The queue maintains vertices ready to process (no blocking dependencies)
- Decrementing in-degrees simulates "removing" edges as you go
- The algorithm naturally detects cycles: if vertices remain with non-zero in-degree after processing, they're stuck in a cycle
Key Takeaway: Kahn's algorithm maintains in-degree counts and uses a queue to iteratively process vertices with zero in-degrees, building the topological order front-to-back while detecting cycles.