Check if the undirected graph is a tree or not

Problem Statement:

You are given a undirected graph.

You need to see of that graph is a tree or not?

Example

Solution

A graph can be a tree if if is connected and there are no loops.

So we need to check for cycle for undirected graph and along with that we also mark the visited matrix so that we can check if the graph is connected or not.

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_graph_is_tree();
};

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_graph_is_tree()
{
     
    bool *visited = new bool[V];

    for (int i = 0; i < V; i++)
        visited[i] = false;
 
    if (helper(0, visited, -1))
             return false;

    for (int u = 0; u < V; u++)
        if (!visited[u])
           return false;
  
    return true;
}

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_graph_is_tree()){
      cout<<"Graph can be tree"<<endl;
   } else {
      cout<<"Graph cannot be tree"<<endl;
   }

   return 0;
}

Output:

Graph cannot be tree

 

 

 

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *