Cycle Detection with Kahn's Algorithm

Welcome back. In our last lesson, we mastered a powerful DFS-based technique to detect cycles in a directed graph by tracking nodes in the active recursion path. This is a fundamental skill, but it's not the only way to solve the problem.

Today, we'll explore an entirely different, BFS-based approach using Kahn's algorithm. You've already seen Kahn's algorithm as a way to produce a topological sort. The core insight for this lesson is that the very failure of this algorithm to sort all nodes is a definitive signal that a cycle exists. This provides an elegant and intuitive alternative for cycle detection.

By the end of this lesson, you will be able to leverage Kahn's algorithm not just for sorting, but as a robust tool to detect a cycle in any directed graph.

The Logic: When Topological Sort Fails

Let's begin by recalling the fundamental prerequisite for a topological sort: the graph must be a Directed Acyclic Graph (DAG). If a graph contains even one cycle, a linear ordering of its vertices that respects all directed edges is impossible.

This "all or nothing" property is what we will exploit. The strategy is simple:

1. Attempt to generate a topological sort for the given graph using Kahn's algorithm.
2. Count the number of vertices included in the resulting sort.
3. If this count is less than the total number of vertices in the graph, we can definitively conclude that a cycle exists.

Why does this work? Kahn's algorithm builds the sort by repeatedly finding and processing nodes with an in-degree of zero. Nodes within a cycle, however, will never reach an in-degree of zero as long as their predecessors in the cycle haven't been processed. This creates a "stalemate" where the algorithm can't proceed, leaving the cyclic nodes unsorted.

Kahn's Algorithm for Cycle Detection

The core of Kahn's algorithm remains the same as when we used it for topological sorting. The only modification is that instead of building the full sorted list, we only need to count how many nodes we successfully "visit".

The algorithm proceeds as follows:

1. Compute In-degrees: Calculate the in-degree for every vertex in the graph. This is typically done by iterating through the edges and incrementing the in-degree count of the destination node for each edge.
2. Initialize Queue: Create a queue and add all vertices with an initial in-degree of 0. These are the starting points of our traversal.
3. Initialize Counter: Create a counter variable, say visited_nodes, and initialize it to 0.
4. Process Nodes: While the queue is not empty:
   a. Dequeue a vertex, let's call it u.
   b. Increment visited_nodes.
   c. For each neighbor v of u:
   i. Decrement the in-degree of v.
   ii. If the in-degree of v becomes 0, enqueue v.
5. Check for Cycle: After the loop terminates (i.e., the queue is empty), compare visited_nodes with the total number of vertices, N.
   • If visited_nodes == N, every node was visited, and the graph is a DAG (no cycle).
   • If visited_nodes < N, the algorithm terminated before visiting all nodes, which proves a cycle exists.

The following video provides a concise and clear explanation of this exact logic.

A Practical Example: The "Course Schedule" Problem

Let's ground this in a classic interview problem: LeetCode #207, "Course Schedule". The problem asks if you can finish all courses given a list of prerequisites. This is a perfect mapping to cycle detection—if there's a circular dependency (e.g., Course A requires B, and B requires A), you can't finish.

The next video uses this problem to give a detailed walkthrough of Kahn's algorithm for cycle detection, complete with excellent visualizations and a line-by-line code explanation.

To reinforce your understanding and have a static code reference, let's turn to a textual resource that lays out the algorithm clearly.

Conclusion

In this final lesson on topological sorting, we've added a powerful BFS-based tool to your cycle detection toolkit. By understanding that a topological sort is only possible on a DAG, you can use the success or failure of Kahn's algorithm to efficiently determine if a directed graph contains a cycle. This pattern is not only elegant but also highly practical for solving dependency-based problems common in coding interviews.

Key Takeaways:

• Cycle Detection via Topological Sort: The core idea is that a graph has a cycle if and only if a topological sort cannot be generated for all its vertices.
• Kahn's Algorithm as the Tool: We use Kahn's algorithm (the BFS-based approach) to attempt the sort.
• The Deciding Factor: The algorithm detects a cycle if the number of nodes visited/sorted is less than the total number of nodes in the graph. This happens because nodes in a cycle never have their in-degrees reduced to zero by external nodes.
• BFS vs. DFS: You now have two distinct methods for cycle detection in directed graphs: a DFS-based method using a recursion stack tracker, and a BFS-based method using in-degrees (Kahn's). Both have a time complexity of $O(V+E)$ and are excellent tools to have.

This concludes our module on graph traversals, shortest paths, and topological sorting. You are now equipped with a robust set of algorithms for a wide range of graph problems. In our next lesson, we will venture into a new and powerful algorithmic paradigm: Dynamic Programming.