Detect cycle in an undirected graph

To detect a cycle in an undirected graph using C++, you can use the Depth-First Search (DFS) algorithm. Here are the steps to detect a cycle in an undirected graph:

1. Create a graph data structure: Start by defining a graph data structure to represent the given graph. You can use an adjacency list or an adjacency matrix to store the graph's edges and vertices.

2. Initialize visited and parent arrays: Create an array to keep track of visited vertices and another array to keep track of the parent of each vertex. Initialize both arrays to mark all vertices as unvisited and set their parent as -1.

3. Perform DFS traversal: Start the DFS traversal from each unvisited vertex in the graph. For each vertex, call the DFS function, passing the vertex, visited array, and parent array as arguments.

4. Explore adjacent vertices: In the DFS function, mark the current vertex as visited. Then, iterate through all the adjacent vertices of the current vertex.

5. Check for a back edge: If an adjacent vertex is visited and is not the parent of the current vertex, it means there is a back edge in the graph, indicating a cycle. Return true to indicate the presence of a cycle.

6. Recurse on unvisited vertices: If the adjacent vertex is not visited, set its parent as the current vertex and call the DFS function recursively on that vertex.

7. Return false: If the DFS traversal completes without finding any back edges, return false to indicate that there is no cycle in the graph.

Here is an example code snippet in C++ that implements the above steps to detect a cycle in an undirected graph:

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

class Graph {
    int V;
    list<int> *adj;
    bool isCyclicUtil(int v, bool visited[], int parent);
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::isCyclicUtil(int v, bool visited[], int parent) {
    visited[v] = true;
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i) {
        if (!visited[*i]) {
            if (isCyclicUtil(*i, visited, v))
                return true;
        } else if (*i != parent)
            return true;
    }
    return false;
}

bool Graph::isCyclic() {
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;
    for (int u = 0; u < V; u++) {
        if (!visited[u]) {
            if (isCyclicUtil(u, visited, -1))
                return true;
        }
    }
    return false;
}

int main() {
    Graph g(5);
    g.addEdge(1, 0);
    g.addEdge(0, 2);
    g.addEdge(2, 0);
    g.addEdge(0, 3);
    g.addEdge(3, 4);
    g.isCyclic() ? cout << "Graph contains a cycle\n" : cout << "Graph doesn't contain a cycle\n";
    return 0;
}

This code defines a Graph class with functions to add edges, perform DFS traversal, and check for a cycle using the isCyclic function. In the main function, a graph is created and edges are added. The isCyclic function is then called to determine if there is a cycle in the graph.