Question

Simplest way to detect whether a graph is a tree in C++. Reading from text file

5
0 1 0 0 0
1 0 1 1 1
0 1 0 0 0
0 1 0 0 0
0 1 0 0 0

Answer 1

Following is the cpp program for checking whether the given graph is tree or not. I am able to run in my local system successfully. I have attached the screenshot for the same.

If you have any further doubts please feel free to comment. I will try to help you out.

============================================================================

/*
* main.cpp
*
* Created on: 10-Feb-2019
* Author: HOME
*/
#include<iostream>
#include <list>
#include <limits.h>
using namespace std;

class Graph
{
   int V; // No. of vertices
   list<int> *adj;
   bool cyclic(int v, bool visited[], int parent);
public:
   Graph(int V);
   void edgeAdd(int v, int w);
   bool checkTree();
};

Graph::Graph(int V)
{
   this->V = V;
   adj = new list<int>[V];
}

void Graph::edgeAdd(int v, int w)
{
   adj[v].push_back(w);
   adj[w].push_back(v);
}

bool Graph::cyclic(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 (cyclic(*i, visited, v))
           return true;
       }

         
       else if (*i != parent)
       return true;
   }
   return false;
}

bool Graph::checkTree()
{
   bool *visited = new bool[V];
   for (int i = 0; i < V; i++)
       visited[i] = false;

   if (cyclic(0, visited, -1))
           return false;

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

   return true;
}

int main()
{
   Graph graph(5);
   graph.edgeAdd(1, 0);
   graph.edgeAdd(0, 2);
   graph.edgeAdd(0, 3);
   graph.edgeAdd(3, 4);
   graph.checkTree()? cout << "Graph is Tree ":
               cout << "Graph is not Tree ";

   Graph newgraph(5);
   newgraph.edgeAdd(1, 0);
   newgraph.edgeAdd(0, 2);
   newgraph.edgeAdd(2, 1);
   newgraph.edgeAdd(0, 3);
   newgraph.edgeAdd(3, 4);
   newgraph.checkTree()? cout << "Graph is Tree ":
               cout << "Graph is not Tree ";

   return 0;
}
===============================================================

==================================================

Thank you !