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,

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

**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;

}