Detect a Cycle in Directed Graph | Topological Sort | Kahn's Algorithm | BFS

Detecting a cycle in a directed graph using Breadth-First Search (BFS) builds directly upon Kahn's Algorithm for topological sorting. While Depth-First Search (DFS) relies on tracking a pathVisited array and backtracking, BFS approaches the problem through in-degree reduction, leveraging the fundamental mathematical property that topological sorts are exclusively valid for Directed Acyclic Graphs (DAGs).

1. Why Do We Need This? (The Limitations of DFS in BFS)

In the previous video, cycle detection in directed graphs was solved using DFS by maintaining two separate arrays:

• A visited array to keep track of globally visited nodes.
• A pathVisited array to track nodes currently in the recursion stack, which is reset (backtracked) upon returning from a branch.

However, standard BFS does not use recursion or a call stack; it uses a queue and processes nodes iteratively level by level. Because BFS does not support backtracking, we cannot easily unset a path-visited flag once a branch is fully explored. Therefore, we need an alternative mental model and algorithm: Kahn's Algorithm.

2. Core Mental Model: Kahn's Algorithm & Topological Sort

A Topological Sort is a linear ordering of vertices $v_1, v_2, \dots, v_n$ in a directed graph such that for every directed edge $u \to v$, vertex $u$ comes before vertex $v$ in the ordering.

• Rule 1: A topological sort is only possible if the graph is a DAG (Directed Acyclic Graph).
• Rule 2: If a graph contains even a single cycle, a valid topological sort cannot be generated for all $n$ nodes because cyclic dependencies create circular roadblocks where no node can safely be placed first without violating the dependency rule.

Real-Life Analogy: Project Task Dependencies

Imagine managing a complex software engineering project where certain tasks must be completed before others (e.g., Task A must finish before Task B).

• If your tasks form a clean dependency tree, you can easily sequence them from start to finish (Topological Sort).
• If Task A depends on Task B, and Task B depends back on Task A, you are trapped in a deadlock (Cycle). You cannot sequence the project, and your workflow stalls because no task has zero prerequisites to start with.

3. Step-by-Step Evolution of the Algorithm

To detect whether a directed graph contains a cycle using BFS, we reuse the exact mechanics of Kahn's Algorithm:

1. Calculate In-Degrees: Compute the incoming edge count (in-degree) for every node in the graph. Nodes with an in-degree of 0 have no dependencies and can be executed first.
2. Initialize Queue: Push all nodes with an in-degree of 0 into a BFS Queue.
3. Process Queue & Reduce In-Degrees:
   • Pop a node from the queue.
   • For every adjacent neighbor of this node, decrement its in-degree by 1 (simulating the removal of the current node and its outgoing edges).
   • If any neighbor's in-degree drops to 0, push it into the queue.
4. Count Processed Nodes: Keep a count of how many total nodes are successfully popped and processed.

4. Complete Flow Walkthrough with an Example

Consider a directed cyclic graph with nodes, where a cycle exists among a subset of nodes.

Initial State:
- Calculate in-degrees for all nodes.
- Node 1 has in-degree = 0.
- Queue: [ 1 ]
- Count = 0

• Step 1: Pop node 1 from the queue.
  • Increment processed count (count = 1).
  • Look at node 1's adjacent neighbors (e.g., node 2).
  • Reduce node 2's in-degree by 1.
• Step 2: Because node 2's in-degree does not drop to 0 (suppose it remains 1 due to a cyclic dependency from another un-removed node), it is never pushed into the queue.
• Step 3: The BFS queue becomes completely empty prematurely because no other nodes have an in-degree of 0.
• Step 4: Final Evaluation:
  • Total nodes in graph = $N$.
  • Total successfully processed nodes (count) < $N$.
  • Conclusion: Since we could not include all nodes in our topological ordering, a cycle is definitively present.

5. Naive vs. Optimized Approach (Do We Need to Store the Result?)

Naive Topological Sort Array Storage

In standard topological sorting problems, you often store the resulting order in an array or list to return it.

// Naive approach storing the entire order
int count = 0;
int[] topo = new int[N];
int idx = 0;

while(!q.isEmpty()) {
    int node = q.poll();
    topo[idx++] = node;
    count++;
    
    for(int neighbor : adj.get(node)) {
        inDegree[neighbor]--;
        if(inDegree[neighbor] == 0) {
            q.add(neighbor);
        }
    }
}

Optimized Cycle Detection Approach

For cycle detection, we do not actually care about the specific sequence of the topological sort. Storing the elements in a separate array or list consumes extra memory unnecessarily.

Instead, we can simply maintain a primitive count variable that increments every time a node is popped from the queue. At the end of the BFS traversal, we check if count == N.

6. Complete Java Implementation

Here is the clean, optimized production-ready implementation for detecting a cycle in a directed graph using BFS (Kahn's Algorithm):

import java.util.*;

public class Solution {
    public boolean isCyclic(int V, ArrayList<ArrayList<Integer>> adj) {
        int[] inDegree = new int[V];
        
        // Step 1: Calculate in-degrees for all nodes
        for (int i = 0; i < V; i++) {
            for (int neighbor : adj.get(i)) {
                inDegree[neighbor]++;
            }
        }
        
        // Step 2: Push all nodes with in-degree 0 into the queue
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < V; i++) {
            if (inDegree[i] == 0) {
                q.add(i);
            }
        }
        
        int count = 0;
        
        // Step 3: BFS Traversal
        while (!q.isEmpty()) {
            int node = q.poll();
            count++; // Increment count of processed nodes
            
            // Get adjacent nodes and reduce their in-degree by 1
            for (int neighbor : adj.get(node)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    q.add(neighbor);
                }
            }
        }
        
        // Step 4: If count is equal to V, no cycle exists. Otherwise, cycle is present.
        if (count == V) {
            return false; // Directed Acyclic Graph (DAG) - No cycle
        }
        return true;     // Cycle detected
    }
}

7. Complexity Analysis

Summary and Key Takeaways

• BFS Alternative: Unlike DFS, which uses path-visited tracking and backtracking, BFS detects cycles in directed graphs by evaluating dependency resolution via Kahn's Algorithm.
• Topological Sort Principle: Topological sorts are only valid for Directed Acyclic Graphs (DAGs). If a cycle exists, a complete topological sort cannot be formed.
• In-Degree Strategy: Compute incoming edge counts for every node. Nodes with an in-degree of 0 serve as the starting roots placed into the BFS queue.
• Edge Reduction Workflow: As nodes are popped from the queue, decrement the in-degree of their neighbors. Whenever a neighbor's in-degree hits 0, push it into the queue.
• Count Validation: Instead of storing the full topological sort sequence, maintain a simple count variable tracking successfully processed nodes.
• The Cycle Rule: If count == V (total vertices), the graph is acyclic. If count < V, the traversal stalled due to circular dependencies, meaning a cycle is present.
• Optimal Efficiency: The algorithm runs in optimal $O(V + E)$ time and $O(V)$ auxiliary space, matching the performance of standard topological sorting.