Detecting Cycles in an Undirected Graph using BFS

Cycle detection in an undirected graph requires a slightly different approach. Since every edge connects both ways, we must carefully track visited nodes and their parents to avoid false positives.

Detecting Cycles in an Undirected Graph using BFS

---

 Idea

• Perform a BFS from every unvisited node (to handle disconnected graphs).

• If a visited node is found that is not the parent, a cycle exists.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution {
  public:
    bool isCycle(int V, vector<vector<int>>& edges) {
        vector<vector<int>> adj(V);
        vector<bool> vis(V,false);
        
        for(int i=0;i<edges.size();i++){
            int u=edges[i][0];
            int v=edges[i][1];
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        for(int start=0;start<V;start++){
            if(!vis[start]){
                queue<pair<int,int>> q;
                q.push({start,-1});
                vis[start]=true;

                while(!q.empty()){
                    int node=q.front().first;
                    int parent=q.front().second;
                    q.pop();

                    for(int i=0;i<adj[node].size();i++){
                        int neighbor=adj[node][i];
                        if(!vis[neighbor]){
                            vis[neighbor]=true;
                            q.push({neighbor,node});
                        } else if(neighbor!=parent) {
                            return true;
                        }
                    }
                }
            }
        }

        return false;
    }
};

int main() {
    vector<vector<int>> edges = {
        {0, 1}, {1, 2}, {2, 0}, {3, 4}
    };

    int V = 5;

    Solution s;
    cout << (s.isCycle(V, edges) ? "Cycle Detected" : "No Cycle") << endl;
    return 0;
}

 Input
V = 5
edges = { {0,1}, {1,2}, {2,0}, {3,4} }
Output
Cycle Detected

Time and Space Complexity

• Time: O(V + E)

• Space: O(V)