Course contentsShow
← Computer Science
Lesson 722 of 2,87217. Graph Traversal AlgorithmsFree lesson

Kahn's Algorithm: Basic Idea

Learn the in-degree based approach: repeatedly remove nodes with zero incoming edges.

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:

  1. Count in-degrees: Calculate how many incoming edges each vertex has
  2. Start with zero in-degree nodes: Find all vertices with in-degree 0 and add them to a queue
  3. 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
  4. Repeat: When a neighbor's in-degree drops to 0, add it to the queue
  5. 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.