bfs to detect cycle in undirected graph

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

class Graph {
    int V;
    list<int> *adj;

public:
    Graph(int V);
    void addEdge(int v, int w);
    bool isCyclic();
};

Graph::Graph(int V) {
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int v, int w) {
    adj[v].push_back(w);
    adj[w].push_back(v);
}

bool Graph::isCyclic() {
    vector<bool> visited(V, false);
    vector<int> parent(V, -1);
    queue<int> q;

    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            visited[i] = true;
            q.push(i);

            while (!q.empty()) {
                int u = q.front();
                q.pop();

                for (auto it = adj[u].begin(); it != adj[u].end(); ++it) {
                    if (!visited[*it]) {
                        visited[*it] = true;
                        q.push(*it);
                        parent[*it] = u;
                    } else if (parent[u] != *it) {
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

int main() {
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(2, 3);

    if (g.isCyclic())
        cout << "Graph contains cycle\n";
    else
        cout << "Graph doesn't contain cycle\n";

    return 0;
}

Explanation: - The code defines a C++ class Graph to represent an undirected graph and detect cycles in it using the breadth-first search (BFS) algorithm. - The class has a constructor to initialize the number of vertices and an array of adjacency lists to store the connections between vertices. - The addEdge method is used to add edges between vertices in the graph. - The isCyclic method uses BFS to detect cycles in the graph. It maintains a queue to perform BFS traversal and checks for cycles by keeping track of visited vertices and their parent vertices. - The main function creates a graph with 4 vertices and adds edges between them. It then calls the isCyclic method to determine if the graph contains a cycle and prints the result.