Detect Cycle in an Undirected Graph

Given an undirected graph, check if the graph contains cycle(s) or not. The detailed description of the problem can be found here.

Solution: DFS is employed to solve this problem. Detecting cycles in the undirected graph is much simpler than that in the directed graph. Consider walking from node i to node j. If j was visited before and is not the parent of node i, we say we get a cycle.  The following is the solution to this problem; the time complexity if O(V+E) [part of code is from geeksforgeeks].

// A C++ Program to detect cycle in an undirected graph
#include<iostream>
#include <vector>

using std::vector;
using std::cout;
using std::endl;

class Graph
{
private:
    int V; // No. of vertices
    vector<int> *adj;
    bool isCyclicUtil(int v, vector<bool> &visited, int parent);
public:
    Graph(int v):V(v), adj(new vector<int>[V]){}
    void addEdge(int v, int w){
        adj[v].push_back(w);
        adj[w].push_back(v);
    }
    bool isCyclic();
};

bool Graph::isCyclicUtil(int v, vector<bool> &visited, int parent){
    visited[v] = true; 
    for (size_t i=0; i<adj[v].size(); ++i){
        int nbr = adj[v][i];
        if (!visited[nbr]){
            cout << "path: " << v << "----->" << nbr << endl;    
            if(isCyclicUtil(nbr, visited, v))
                return true;
        }
        else if(nbr != parent){
            cout << "path: " << v << "----->" << nbr << endl;    
            cout << "back edge: " << v << "----->" << nbr << endl;
            return true;
        }
    }
    return false;
}

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

    return false;
}

int main()
{
    // Create a graph given in the above diagram
    Graph g(5);
    g.addEdge(1, 0);
    g.addEdge(0, 2);
    g.addEdge(0, 3);
    g.addEdge(3, 4);
    g.addEdge(0, 4);

    if(g.isCyclic())
        cout << "Graph contains cycle" << endl;
    else
        cout << "Graph doesn't contain cycle" << endl;
    return 0;
}