## Introduction

In this blog, we will look at the approach to check whether the given graph is a tree or not. If a given graph is a tree, our function will return a true value and if the graph is not a tree then the function will return a false value.

### Problem Statement

**Given:** An undirected graph with V vertices and E edges.

**Problem:** Check whether the given graph is a tree or not. If the graph is a tree, the function will return a true value and if the graph is not a tree, then the function will return a false value.

### Sample Examples

Let us consider the following undirected graph to check whether the given graph is a tree or not.

This graph contains a loop, also known as a cycle. Hence, __the given graph is not a tree__.

If the graph was transformed to the below graph, then let us check if the given graph is a tree or not.

Now, the cycle in the previous graph is broken and the graph is now a connected graph. Therefore, __this graph is a tree__.

## Approach

A direct approach to check whether the given graph is a tree or not is by checking for the following two conditions:

- The graph should not contain a cycle or a loop.
- The graph must be connected.

### Pseudocode

To check whether there is a cycle or not in the graph:

- Take the input and create the undirected graph using the given number of edges and vertices.
- Create a recursive function to keep track of the current index/vertex, visited array for storing the visited nodes in the graph and the parent node.
- Now, mark the current node( the first node) as visited and store it in the visited array.
- Run a loop to find all the vertices which are not visited and are adjacent to the current node. Recursively call the function for those vertices, if the recursive function returns true, then return true.
- If the adjacent node is not a parent node and is already visited then return true.
- Then, create a wrapper function, that calls the recursive function for all the vertices and if any function returns true, return true. (Because all the nodes in the graph might not be connected or reachable from a starting vertex. To make sure every vertex of the graph is connected we are calling the recursive function for all unvisited nodes.)
- Else if for all vertices the function returns false, then return false.

To check whether the given graph is a tree or not:

- Create a function which defines a visited array for storing the visited nodes in the graph.
- Initially, mark all the nodes as unvisited.
- Now, call a function to check whether there is a cycle in the graph or not. If the function returns true then, the parent of the starting vertex is null. Else, return false.
- If the graph is not connected, then also return false.
- Else return true, which means the graph is a tree.

### Implementation in Python

```
from collections import defaultdict
class Graph:
def __init__(self,n_vertices):
self.V = n_vertices
self.graph = defaultdict(list)
def add_edge(self,u,v):
self.graph[u].append(v)
self.graph[v].append(u)
def is_cycle(self,v,visited_arr,parent):
visited_arr[v] = "Visited"
for i in self.graph[v] :
if(visited_arr[i] == "not Visited") :
if (self.is_cycle(i,visited_arr,v)):
return True
elif i != parent:
return False
return False
def is_tree(self):
visited_arr = ["not Visited"] * self.V
if (self.is_cycle(0,visited_arr,-1)) :
return False
for i in range(self.V) :
if(visited_arr[i] == "not Visited"):
return False
return True
# Example 1
g2 = Graph(5)
g2.add_edge(1,0)
g2.add_edge(0,2)
g2.add_edge(0,3)
g2.add_edge(3,4)
if (g2.is_tree() == True):
print("Graph is a Tree")
else :
print("Graph is a not a Tree")
# Example 2
g2 = Graph(5)
g2.add_edge(1,0)
g2.add_edge(0,2)
g2.add_edge(0,3)
g2.add_edge(1,3)
if (g2.is_tree() == True):
print("Graph is a Tree")
else :
print("Graph is a not a Tree")
```

**Output:**

```
Graph is a Tree
Graph is not a Tree
```

### Implementation in C++

```
#include <iostream>
#include <vector>
using namespace std;
// Data structure to store a graph edge
struct Edge {
int src, dest;
};
// A class to represent a graph object
class Graph
{
public:
// a vector of vectors to represent an adjacency list
vector<vector<int>> adjList;
// Graph Constructor
Graph(vector<Edge> const &edges, int n)
{
// resize the vector to hold `n` elements of type `vector<int>`
adjList.resize(n);
// add edges to the undirected graph
for (auto &edge: edges)
{
adjList[edge.src].push_back(edge.dest);
adjList[edge.dest].push_back(edge.src);
}
}
};
// Perform DFS on the graph and returns true if any back-edge
// is found in the graph
bool DFS(Graph const &graph, int v, vector<bool> &discovered, int parent)
{
// mark the current node as discovered
discovered[v] = true;
// do for every edge (v, w)
for (int w: graph.adjList[v])
{
// if `w` is not discovered
if (!discovered[w])
{
if (!DFS(graph, w, discovered, v)) {
return false;
}
}
// if `w` is discovered, and `w` is not a parent
else if (w != parent)
{
// we found a back-edge (cycle)
return false;
}
}
// no back-edges were found in the graph
return true;
}
// Check if the given undirected graph is a tree
bool isTree(Graph const &graph, int n)
{
// to keep track of whether a vertex is discovered or not
vector<bool> discovered(n);
// boolean flag to store if the graph is tree or not
bool isTree = true;
// Perform DFS traversal from the first vertex
isTree = DFS(graph, 0, discovered, -1);
for (int i = 0; isTree && i < n; i++)
{
// any undiscovered vertex means the graph is disconnected
if (!discovered[i]) {
isTree = false;
}
}
return isTree;
}
int main()
{
// initialize edges as per the above diagram
vector<Edge> edges =
{
{0, 1}, {1, 2}, {2, 4}, {1, 3}, {3, 4}
// edge (3, 4) introduces a cycle in the graph
};
// total number of nodes in the graph (0 to 5)
int n = 6;
// build a graph from the given edges
Graph graph(edges, n);
if (isTree(graph, n)) {
cout << "The graph is a tree";
}
else {
cout << "The graph is not a tree";
}
return 0;
}
```

**Output:**

`The graph is not a tree`

### Complexity Analysis

**Time Complexity: **In the given problem where we check whether the given graph is a tree or not, the time complexity of the program will be O(V+E) as the time complexity depends on the continuous number of iterations or value changes that we need to iterate over in the complete program, and here the total number of times we iterate will be the number of vertices and edges in the program.

**Space Complexity: **The space complexity for the given program is O(V) because we need space to store the V number of vertices of the graph.