Detect Cycle in an undirected graph - BFS

Practice Link

Given an undirected 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.

BFS#

In an undirected graph a cycle exists if, during BFS, we encounter a neighbor that is already visited and is not the direct parent we came from. The parent check is essential because every undirected edge appears in both directions in the adjacency list — without it, every edge would look like a back-edge and falsely signal a cycle.

• Start from one node (unvisited) and explore all nodes via BFS.
• Use a visited array to keep track of explored nodes.
• Track the parent of each node in the BFS queue to avoid false-positive cycle detection on the edge we just traversed.
• If during traversal we find a neighbor that is already visited and is not our parent, we have reached it from two different paths — a cycle exists.
• Continue traversal until all nodes are visited or a cycle is found (handles disconnected graphs by restarting from every unvisited node).

class Solution{
public:

    bool isCycleBFS(vector<int> adj[], int src, vector<bool> &visited){
        queue<pair<int,int>> q;
        q.push({src, -1});
        visited[src] = true;

        while(!q.empty()){
            auto [currNode, parentNode] = q.front();
            q.pop();

            for(auto nextNode: adj[currNode]){
                if(!visited[nextNode]){
                    visited[nextNode] = true;
                    q.push({nextNode, currNode});
                }
                else if(nextNode != parentNode){
                    return true;
                }
            }

        }
        return false;
    }

    bool isCycle(int V, vector<int> adj[]) {
        vector<bool> visited(V, false);

        for(int i=0;i<V;i++){
            if(!visited[i] && isCycleBFS(adj, i, visited))
                return true;
        }
        return false;
    }
};

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

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

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

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