Binary Trees: Check if a given graph is tree or not

Problem Statement:

You are given an undirected graph, you need to check if the graph is a tree or not.

Example

In the below image, first graph is a tree, second graph is not a tree.

Solution

We know that an undirected graph is a tree if:

1. It has no cycle

2. If the graph is connected

1. To check if the graph is not a cycle we use below steps:

We can use either BSF or DFS.
We need to visit every vertex ‘v’, if there is an adjacent vertex ‘u’ such that ‘u’ is already visited and is not a parent of ‘v’, then we have a cycle.

2. How to check for connectivity is graph?
As the graph is undirected, we use BFS or DFS from any vertex, and check if all the vertices are reachable. If reachable then the graph is connected.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <list> 
#include <queue> 

using namespace std;

class Graph
{
    int V;    
    list<int> *adj; //adj list
    bool check_has_cycle(int v, bool visited[], int parent);
public:
    Graph(int V);   
    void add_edge(int v, int w);   
    bool is_tree();  
};
 
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}
 
void Graph::add_edge(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.
}
 

bool Graph::check_has_cycle(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 (check_has_cycle(*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;
}
 
bool Graph::is_tree()
{

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

    if (check_has_cycle(0, visited, -1))
             return false;
 
    //if there is a vertex that is not reachable from 0, then return false.
    for (int u = 0; u < V; u++)
        if (!visited[u])
           return false;
 
    return true;
}
 
int main()
{
    Graph g1(5);
    g1.add_edge(1, 0);
    g1.add_edge(0, 2);
    g1.add_edge(0, 3);
    g1.add_edge(3, 4);
    g1.is_tree()? cout << "Graph is Tree\n":
                 cout << "Graph is not Tree\n";
 
 
    return 0;
}

Output:

Graph is Tree