Kahn's Algorithm: Basic Idea
What you'll learn: How to perform topological sorting by repeatedly removing vertices that have no incoming edges.
The Core Concept
Kahn's Algorithm solves topological sorting by focusing on in-degrees (the number of incoming edges to each vertex). The key insight is simple: if a node has no incoming edges, it has no prerequisites, so it can be processed immediately.
Here's how it works:
- Count in-degrees: Calculate how many incoming edges each vertex has
- Start with zero in-degree nodes: Find all vertices with in-degree 0 and add them to a queue
- Process iteratively: Remove a vertex from the queue, add it to your sorted result, and decrease the in-degree of all its neighbors by 1
- Repeat: When a neighbor's in-degree drops to 0, add it to the queue
- Continue until the queue is empty
Why This Works
Think of it like taking college courses: you can only take a course once you've completed all its prerequisites. Kahn's Algorithm identifies courses with no prerequisites (in-degree 0), "takes" them, then updates which courses become available next.
As you remove edges from processed nodes, you're essentially saying "this prerequisite is now satisfied." When all prerequisites for a node are satisfied (in-degree reaches 0), that node is ready to be processed.
Detecting Cycles
If the algorithm finishes but hasn't processed all vertices, the remaining nodes form a cycle—there's circular dependency with no starting point.
Key Takeaway: Kahn's Algorithm performs topological sorting by maintaining in-degrees and repeatedly removing nodes with zero incoming edges until all nodes are processed or a cycle is detected.