Problem Statement:
You are given a undirected graph.
You need to see of that graph is a tree or not?
Example
Solution
A graph can be a tree if if is connected and there are no loops.
So we need to check for cycle for undirected graph and along with that we also mark the visited matrix so that we can check if the graph is connected or not.
Solution in C++
#include <algorithm>
//visit www.ProDeveloperTutorial.com for 450+ solved questions
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <stack>
#include <list>
using namespace std;
class Graph
{
private:
int V;
list<int> *adj; // to hold adjacency list
bool helper(int v, bool visited[], int parent);
public:
Graph(int V); // Constructor
void add_edge(int v, int w); // to add an edge to graph
void print_graph();
bool check_if_graph_is_tree();
};
Graph::Graph(int V)
{
// get the total number of nodes
this->V = V;
// initialize adjacency list for that number of nodes
adj = new list<int>[V];
}
void Graph::add_edge(int v, int w)
{
// add the edge to adjacency list
adj[v].push_back(w);
adj[w].push_back(v);
}
void Graph::print_graph()
{
for(auto i = 0; i < V; i++)
{
cout<<"\nAdjacency list of vertex "<<i<<endl;
for(auto j = adj[i].begin(); j != adj[i].end(); j++)
{
cout<<" ->"<<*j;
}
}
}
bool Graph::helper(int v, bool visited[], int parent)
{
visited[v] = true;
for (auto i = adj[v].begin(); i != adj[v].end(); ++i)
{
if (!visited[*i])
{
////check if the adjacent vertex is not visited,
// then recur that
if (helper(*i, visited, v))
return true;
}
// if it is visited and if it is not the parent of the current
// vertex, then there is a cycle.
else if (*i != parent){
return true;
}
}
return false;
}
bool Graph::check_if_graph_is_tree()
{
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
if (helper(0, visited, -1))
return false;
for (int u = 0; u < V; u++)
if (!visited[u])
return false;
return true;
}
int main()
{
Graph g(4);
g.add_edge(1, 0);
g.add_edge(0, 2);
g.add_edge(2, 1);
g.add_edge(0, 3);
g.add_edge(1, 3);
g.add_edge(2, 3);
if(g.check_if_graph_is_tree()){
cout<<"Graph can be tree"<<endl;
} else {
cout<<"Graph cannot be tree"<<endl;
}
return 0;
}
Output:
Graph cannot be tree