Graph Theory37 sections · 1633 units
Open in Course

Kahn's Algorithm - The Intuition

Peeling the Onion

The in-degree of a node is the number of edges pointing to it. For courses, in-degree means "how many prerequisites are left". When in-degree becomes 00, the course is ready to take. You have finished all its prerequisites. Kahn's algorithm exploits this: start with all courses that have in-degree 00 (no prerequisites).

Take them, then remove their outgoing edges. This decreases the in-degree of their neighbors. When a neighbor's in-degree drops to 00, it becomes ready. You repeat until all courses are taken or you discover a cycle.