Graph Cycle Detection Using DFS in C++

 // C++ Program for Graph Cycle Detection using DFS
#include <iostream>
#include <vector>
using namespace std;

// Define a class for representing an undirected graph
class Graph {
    
private:
 // Number of vertices in the graph
    int V;    
// Adjacency list representation of the graph
    vector<int>* adj;      
    
public:
    // Constructor to initialize the adjacency list for the graph
    Graph(int vertices) : V(vertices) {
        // Allocate memory for adjacency lists
        adj = new vector<int>[V];   
    }

    // Function to add an edge between two vertices in a graph
    void addEdge(int v, int w) {
        adj[v].push_back(w);    
        adj[w].push_back(v);    
    }

    // Depth-first search function to check for cycles
    bool dfs(int node, int parent, vector<bool>& vis) {
        vis[node] = true;   // Mark the current node as visited
        for (auto nbr : adj[node]) {
            if (!vis[nbr]) {
                // If the neighbor is not visited, recursively visit it
                if (dfs(nbr, node, vis)) return true;
            }
            else if (nbr != parent) {
                // If the neighbor is visited and not the parent, it forms a cycle
                return true;
            }
        }
        // If no cycle is found, return false
        return false;   
    }

    // Function to check if the graph contains a cycle
    bool isCycle() {
        // Initialize visited array with all vertices as not visited
        vector<bool> vis(V, false); 
        
        // Start DFS traversal from vertex 0
        bool cycle = dfs(0, -1, vis); 
        
        // Return true if cycle is found, false otherwise
        return cycle;
    }
};

// Driver Code
int main() {
    // Initialize a graph object having 4 vertices
    Graph g(4);

    // Adding edges to the graph
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(0, 3);
    g.addEdge(1, 2);

    // Check if the graph contains a cycle and print the result
    if (g.isCycle()) {
        cout << "Graph contains cycle" << endl;
    } else {
        cout << "Graph doesn't contain cycle" << endl;
    }

    return 0;
}