Kahn's Algorithm for Topological Sort

Hello! In our last lesson, we explored the "what" and "why" of topological sorting, focusing on identifying problems that involve dependencies and can be modeled as a Directed Acyclic Graph (DAG). We established a framework for recognizing and articulating these problems in an interview setting.

Today, we transition from theory to practice. This lesson is dedicated to implementing one of the two main algorithms for topological sorting: Kahn's algorithm. You'll learn how this intuitive, breadth-first search (BFS) based approach works, how to implement it efficiently, and how it elegantly handles the critical edge case of cycle detection. This is a fundamental pattern for any coding interview involving graphs.

The Core Idea: Processing Nodes with No Prerequisites

Kahn's algorithm is beautifully simple and mirrors how we might solve a dependency problem in real life. Imagine your list of course prerequisites. You would naturally start by taking the courses that have no prerequisites. Once you complete them, you unlock a new set of courses whose prerequisites are now met. You repeat this process until all courses are taken.

Kahn's algorithm formalizes this logic:

1. A node with an in-degree of 0 (zero incoming edges) has no dependencies and can be "processed" first.
2. Once we process a node, we can think of it as being removed from the graph, along with its outgoing edges.
3. This "removal" may cause other nodes (its neighbors) to have their dependencies satisfied. In graph terms, their in-degrees decrease.
4. If a neighbor's in-degree drops to 0, it becomes a new node with no outstanding prerequisites, and it can be processed.

We use a queue to keep track of all nodes that are ready to be processed (i.e., those with an in-degree of 0). The following video from WilliamFiset provides an excellent animation of this core intuition.

The Algorithm Step-by-Step

To implement this, we need two key data structures:

• An array or hash map to store the in-degree of every node.
• A queue to store the nodes with an in-degree of 0.

The algorithm proceeds as follows:

1. Graph and In-Degree Calculation: First, build your graph representation (an adjacency list is best) and simultaneously calculate the in-degree for every node. You can do this by iterating through your list of edges: for each edge u -> v, you add v to u's adjacency list and increment the in-degree of v.

2. Initialization: Create a queue and add all nodes that initially have an in-degree of 0. These are your starting points.

3. Processing Loop: While the queue is not empty:
   a. Dequeue a node, let's call it u. Add u to your result list (this is the next node in your topological order).
   b. For each neighbor v of u:
   i. Decrement the in-degree of v. This signifies that one of its prerequisites (u) has been met.
   ii. If the in-degree of v becomes 0, it means all of its prerequisites are now satisfied. Add v to the queue.

4. Cycle Detection: After the loop finishes, check if the number of nodes in your result list is equal to the total number of nodes in the graph. If it is, you have a valid topological sort. If not, the graph must contain a cycle, and no topological sort is possible.

The "take U forward" channel provides an excellent, detailed walkthrough of this process with a concrete example. Watching it will help you visualize the state of the in-degree array and the queue at each step.

The image below illustrates the step-by-step removal of nodes with zero in-degree, which is the core of Kahn's algorithm.

Implementation and Complexity

Now, let's translate this logic into a functional algorithm. Your experience with LeetCode problems means you're already familiar with representing graphs and using queues for BFS, so this should feel like a natural extension of patterns you already know.

The article "Learn Topological Sort Algorithm" from Interview Kickstart provides a clean pseudocode and implementation.

The following image shows a snapshot of the algorithm mid-run. This is a great mental model for what your data structures should look like during any given iteration.

Complexity Analysis

Understanding the performance of your algorithms is crucial. Kahn's algorithm is highly efficient.

• Time Complexity: $O(V+E)$, where $V$ is the number of vertices and $E$ is the number of edges.

  • Calculating the initial in-degrees takes $O(E)$ time as we iterate through all edges.
  • Initializing the queue takes $O(V)$ time in the worst case (if many nodes have an in-degree of 0).
  • The main while loop runs once for each vertex. Inside the loop, we iterate through the neighbors of the current vertex. Over the entire execution, each edge is processed exactly once. Therefore, the work done in the loop is proportional to the sum of the degrees of all vertices, which is $O(E)$.
  • Total time: $O(V+E)$.

• Space Complexity: $O(V)$.

  • We need space for the in_degree array, which is $O(V)$.
  • The queue can hold up to $V$ vertices in the worst case, so it's $O(V)$.
  • The result list also stores $V$ vertices.
  • Note: This does not include the space for the adjacency list itself, which is $O(V+E)$.

The Interview Kickstart article also provides a concise summary of this complexity.

Conclusion

In this lesson, you've moved from the concept of topological sorting to a concrete, practical implementation. Kahn's algorithm provides an intuitive and efficient way to find a valid ordering for tasks with dependencies. Its iterative, BFS-based nature makes it easy to trace, and its method for cycle detection is a natural outcome of the algorithm's logic.

Key Takeaways:

• Kahn's Algorithm: A BFS-based approach for topological sort that processes nodes with an in-degree of 0.
• Core Components: It relies on an in_degree array to track prerequisites and a queue to manage nodes that are ready to be processed.
• Process: Initialize with 0-in-degree nodes, then iteratively dequeue a node, add it to the sort, and "relax" its neighbors by decrementing their in-degrees.
• Cycle Detection: If the final sorted list contains fewer nodes than the graph, a cycle exists.
• Complexity: The algorithm is efficient, with a time complexity of $O(V+E)$ and space complexity of $O(V)$.

While Kahn's algorithm is powerful, it's not the only way to perform a topological sort. In our next lesson, we will explore the second major approach: a recursive method based on Depth-First Search (DFS). We'll see how it differs from Kahn's algorithm and when you might choose one over the other.