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

Kahn's Algorithm: Implementation

Step through the queue-based implementation and maintain in-degree counts.

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:

  1. Initialize: Count the in-degree for every vertex. Add all vertices with in-degree 0 (no prerequisites) to the queue.
  2. 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
  3. 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.