Detect a cycle in a undirected graph

Problem Statement:

You are given a undirected graph.
You need to find out if the graph contains cycle or not.

Example

Solution

We can use DFS to solve this problem.

For this we have a recursive stack and an array to hold the vertex that are visited.

For every non visited vertex, mark the current vertex as visited in visited array and also in recursion stack.

Then find all the vertices that are not visited and are adjacent to the current node.

Then we need to check for every visited vertex ‘v’, there is an adjacent vertex ‘u’ such that ‘u’ is already visited and ‘u’ is not the parent of ‘v’, then there is a cycle.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <stack> 
#include <list> 

using namespace std;

class Graph
{

private:
   int V; 
   list<int> *adj; // to hold adjacency list
   bool helper(int v, bool visited[], int parent);
public:
   Graph(int V); // Constructor
   void add_edge(int v, int w); // to add an edge to graph
   void print_graph();
   bool check_if_has_cycle();
};

Graph::Graph(int V)
{
   // get the total number of nodes
   this->V = V;

   // initialize adjacency list for that number of nodes
   adj = new list<int>[V];
}

void Graph::add_edge(int v, int w)
{
   // add the edge to adjacency list
   adj[v].push_back(w); 
   adj[w].push_back(v); 
}

void Graph::print_graph()
{
   for(auto i = 0; i < V; i++)
   {
      cout<<"\nAdjacency list of vertex "<<i<<endl;

      for(auto j = adj[i].begin(); j != adj[i].end(); j++)
      {
         cout<<" ->"<<*j;
      }
   }
}

bool Graph::helper(int v, bool visited[], int parent)
{
     
    visited[v] = true;
 
    for (auto i = adj[v].begin(); i != adj[v].end(); ++i)
    {
         
        if (!visited[*i])
        {
         ////check if the adjacent vertex is not visited, 
         // then recur that
           if (helper(*i, visited, v))
              return true;
        } 
        // if it is visited and if it is not the parent of the current 
        // vertex, then there is a cycle.
        else if (*i != parent){
           return true;
        }
    }
    return false;
}

bool Graph::check_if_has_cycle()
{
     
    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 (helper(u, visited, -1))
             return true;
    }
    return false;
}

int main()
{

   Graph g(4);
   g.add_edge(1, 0);
   g.add_edge(0, 2);
   g.add_edge(2, 1);
   g.add_edge(0, 3);
   g.add_edge(1, 3);
   g.add_edge(2, 3);


   if(g.check_if_has_cycle()){
      cout<<"Graph has cycle"<<endl;
   } else {
      cout<<"Graph does has cycle"<<endl;
   }

   return 0;
}

Output:

Graph has cycle