Detect Cycle in an directed graph - BFS

Practice Link

Given an directed graph with V vertices and E edges, check whether it contains any cycle or not.

No Cycle

Cycle exists

Note#

Graph can also be disconnected -> Check for every node as source/starting node.

Use DFS algorithm if need to use the nodes in the cycle.

BFS (Kahn's Algorithm)#

This approach leverages the key insight that topological sorting is only possible for a Directed Acyclic Graph (DAG). Kahn's algorithm processes nodes in topological order by repeatedly removing nodes whose in-degree has dropped to zero. If any nodes remain with a non-zero in-degree after the BFS completes, those nodes are part of a cycle — because no ordering can satisfy a circular dependency.

• Compute in-degree for every vertex.
• Push all vertices with in-degree 0 into a queue (these have no dependencies, so they can be safely processed first).
• While the queue is non-empty, dequeue a node, increment the visited count, and reduce the in-degree of all its neighbors by 1; enqueue any neighbor whose in-degree reaches 0.
• If remaining vertices have in-degree > 0 → at least one cycle exists (they were never dequeued because their dependency count never reached zero).
• If totalNodesVisited == V, the graph is a DAG — no cycle exists.

Implementation#

bool isCyclic(int V, vector<vector<int>> adj) {
        vector<int> inDegree(V,0);
        for(int i=0;i<adj.size();i++)
        {
            for(int j=0;j<adj[i].size();j++)
            {
                inDegree[adj[i][j]]++;
            }
        }
        
        queue<int> q;
        for(int i=0;i<V;i++)
            if(inDegree[i]==0)
                q.push(i);
        
        int totalNodesVisited=0;
        while(!q.empty())
        {
            int currNode = q.front();
            q.pop();
            totalNodesVisited++;
            
            for(auto adjNode: adj[currNode])
            {
                inDegree[adjNode]--;
                if(inDegree[adjNode]==0)
                {
                    q.push(adjNode);
                }
            }
        }
        return totalNodesVisited != V;
    }

Complexities#

Time Complexity: O(V+E) + O(N)#

We are exploring every vertex V and exploring all its edges. O(N) -> For covering disconnected components

Same TC as BFS

Space Complexity: O(N)+O(V+E),#

O(N) to keep visited nodes, and O(V+E) to create the adjacency list.