This is a C++ Program to check whether an undirected graph is tree or not. Graph is tree if it doesn’t contain cycles.

Here is source code of the C++ Program to Check if an UnDirected Graph is a Tree or Not Using DFS. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

`#include<iostream>`

`#include <list>`

`#include <limits.h>`

using namespace std;

`// Class for an undirected graph`

`class Graph`

`{`

int V; // No. of vertices

list<int> *adj; // Pointer to an array containing adjacency lists

bool isCyclicUtil(int v, bool visited[], int parent);

public:

Graph(int V); // Constructor

void addEdge(int v, int w); // to add an edge to graph

bool isCyclic(); // returns true if there is a cycle

};

Graph::Graph(int V)

`{`

this->V = V;

adj = new list<int> [V];

`}`

void Graph::addEdge(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.

`}`

`// A recursive function that uses visited[] and parent to detect`

`// cycle in subgraph reachable from vertex v.`

bool Graph::isCyclicUtil(int v, bool visited[], int parent)

`{`

`// Mark the current node as visited`

visited[v] = true;

`// Recur for all the vertices adjacent to this vertex`

list<int>::iterator i;

for (i = adj[v].begin(); i != adj[v].end(); ++i)

`{`

`// If an adjacent is not visited, then recur for that adjacent`

if (!visited[*i])

`{`

if (isCyclicUtil(*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 contains a cycle, else false.`

bool Graph::isCyclic()

`{`

`// Mark all the vertices as not visited and not part of recursion`

`// stack`

bool *visited = new bool[V];

for (int i = 0; i < V; i++)

visited[i] = false;

`// Call the recursive helper function to detect cycle in different`

`// DFS trees`

for (int u = 0; u < V; u++)

if (!visited[u]) // Don't recur for u if it is already visited

if (isCyclicUtil(u, visited, -1))

return true;

return false;

`}`

`// Driver program to test above functions`

int main()

`{`

Graph g1(5);

g1.addEdge(1, 0);

g1.addEdge(0, 2);

g1.addEdge(2, 0);

g1.addEdge(0, 3);

g1.addEdge(3, 4);

g1.isCyclic() ? cout << "Undirected Graph isn't a tree\n" : cout

<< "Undirected Graph is a tree\n";

Graph g2(3);

g2.addEdge(0, 1);

g2.addEdge(1, 2);

g2.isCyclic() ? cout << "Undirected Graph isn't a tree\n" : cout

<< "Undirected Graph is a tree\n";

return 0;

`}`

Output:

$ g++ UndirectedTree.cpp $ a.out Undirected Graph isn't a tree Undirected Graph is a tree ------------------ (program exited with code: 0) Press return to continue

**Sanfoundry Global Education & Learning Series – 1000 C++ Programs.**

Here’s the list of Best Reference Books in C++ Programming, Data Structures and Algorithms.