Program to check if the given graph is a tree or not | faceprep

Program to check if the given graph is a tree or not is discussed here. 

An undirected graph is given as input, 

The given graph is said to be a tree,

  • The graph is connected.
  • When there are no cycles in the graph.

For example,

check if the graph is a tree or not

The above-given graph is not a tree because it has a cycle.

graph is a tree or not

Algorithm to check if the given graph is a tree or not

  • Input the graph.
  • Check if the graph has any cycles in it.
  • If it has a cycle, then print “The given graph is not a tree”.
  • Else, print “The given graph is a tree”.

Program to check if the given graph is a tree or not is given below.

// C++ Program to check whether a graph is a tree or not
#include<iostream>
#include <list>
#include <limits.h>
using namespace std;

// Class representation for an undirected graph
class Graph
{
int V;
list<int> *adj; // Pointer to an array for maintaining adjacency lists
bool cycle_presence(int v, bool visited[], int parent);
public:
Graph(int V);
void add_edge_graph(int v, int w); // Add an edge to the graph
bool isTree(); // Returns true if graph is tree
};


int main()
{
Graph graph1(5);
char ch;
int a, b;
cout << “\nEnter the connections of graph 1\n”;
do
{
cin >> a >> b >> ch;
graph1.add_edge_graph(a, b);
}while(ch == ‘y’ || ch == ‘Y’);

graph1.isTree()? cout << “The given graph is a tree\n”: cout << “The given graph is not a tree\n”;
Graph graph2(5);
cout << “\nEnter the connections of graph 2\n”;
do
{
cin >> a >> b >> ch;
graph2.add_edge_graph(a, b);
}while(ch == ‘y’ || ch == ‘Y’);

graph2.isTree()? cout << “The given graph is a tree\n”: cout << “The given graph is not a tree\n”;

return 0;
}

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

// Adding the edges to the graph
void Graph::add_edge_graph(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list
adj[w].push_back(v); // Add v to w’s list
}

// Function that uses visited[] and parent to detect cycle
bool Graph::cycle_presence(int v, bool visited[], int parent)
{
// Mark current node as visited
visited[v] = true;

// Recur for all the vertexes adjacent to this vertex
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
{

if (!visited[*i])
{
if (cycle_presence(*i, visited, v))
return true;
}

// If an adjacent is visited and not parent of current vertex, then there is a cycle.
else if (*i != parent)
return true;
}
return false;
}

// Returns true if the graph is a tree, else returns false.
bool Graph::isTree()
{
// Mark all the vertexes as not visited
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;

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

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

return true;
}