Detect Cycle in directed graph

Link : GFG Problem Link

Problem Statement

You are given a directed graph with V vertices and E edges. Your task is to detect whether the graph contains a cycle or not.

Why Use Topological Sort for Cycle Detection?

What is Topological Sort?

Topological sort is a linear ordering of vertices such that for every directed edge u → v, vertex u comes before v in the ordering.

Properties of Topological Sort:

• Only Directed Acyclic Graphs (DAGs) have valid topological orderings.

• If a cycle exists, at least one node cannot be resolved in the ordering.

Why Topological Sort Fails on Cycles

• In Kahn’s Algorithm, we start with nodes of indegree = 0.

• For every processed node, we reduce the indegree of its neighbors.

• If there is a cycle, some nodes will never reach indegree = 0, hence:

  • They can’t be processed.

  • The total number of processed nodes < V.

This leads to the core insight:

If Topological Sort fails to include all vertices, a cycle is present.

Intuition

Imagine task dependencies:

• A → B → C is a valid sequence (DAG).

• But A → B → C → A forms a loop — impossible to schedule. That's a cycle.

By counting how many nodes can be processed using indegree logic, you can detect loops.

Approach: Kahn’s Algorithm (BFS for Topological Sort)

Steps:

1. Build the adjacency list from the edge list.

2. Compute the indegree of each node.

3. Add all nodes with indegree = 0 to a queue.

4. While the queue is not empty:

   • Pop a node and increase a count.

   • For each neighbor:

     • Decrease its indegree by 1.

     • If indegree becomes 0, add it to the queue.

5. If count != V, then a cycle exists.

Applications of Cycle Detection in Directed Graphs

• Detecting deadlocks in Operating Systems

• Build systems or compiler dependency resolution

• Circular references in software modules, spreadsheets, or database triggers

Code (Java – BFS Topological Sort with Cycle Detection)

class Solution {
    public boolean isCyclic(int V, List<List<Integer>> adj) {
        int[] indegree = new int[V];
        
        // Step 1: Compute indegree of each vertex
        for (int i = 0; i < V; i++) {
            for (int neighbor : adj.get(i)) {
                indegree[neighbor]++;
            }
        }

        // Step 2: Initialize queue with nodes having indegree 0
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < V; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        int count = 0;

        // Step 3: Process nodes
        while (!queue.isEmpty()) {
            int node = queue.poll();
            count++;

            for (int neighbor : adj.get(node)) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        // Step 4: Check if all nodes were processed
        return count != V;  // true if cycle exists
    }
}

Dry Run Example

Input:

Edges:

0 → 1  
1 → 2  
2 → 3  
3 → 1 (Cycle)

Execution:

• Indegree: [0, 2, 1, 1]

• Queue: [0]

• Process 0 → reduce indegree of 1 to 1 → queue becomes empty

• Remaining nodes have non-zero indegree → cycle detected

Time and Space Complexity

• Time Complexity: O(V + E)

• Space Complexity: O(V) for queue and indegree array

Conclusion

Detecting a cycle in a directed graph using Kahn’s Algorithm (a topological sort method) is efficient and intuitive. The key insight:

If not all nodes are processed during topological sorting, then the graph contains a cycle.