Last Updated on March 23, 2022 by Ria Pathak
Concepts Used
Depth First Search, Graph
Difficulty Level
Medium
Problem Statement :
Check whether the graph is a tree or not.
See original problem statement here
Solution Approach :
Introduction :
For a graph to be tree, there should not be any loops and every vertex must be reachable from atleast one other vertex.
This problem can be solved by many ways like Breadth First Search, Depth First Search or Disjoint Set. Below we are going to discuss two of the above mentioned methods to solve this problem.
Method 1 :
The graph must follow these properties:
If there arenvertices then there must ben-1edges.
It should be connected i.e. every vertex can be reached with atleast one other vertex.In trees, every node/vertex is connected to atleast one other vertex. Also the total number of edges is also
n-1fornnodes.
Method 2 :
The another way of checking our graph whether it is a tree or not that it should have following properties:
It must not contain any cycle.
It must be connected.As, we can see this approach is almost similar to the approach in method
1, our goal is to make sure that our graph has no loops or in other words it has exactlyn-1edges and must be connected. By this way we can ensure our graph is a tree, otherwise not. Refer to the example below for better understanding.See C++ implementation below.
Algorithms :
dfs() :
- For each call, for some vertex
v( dfs(v) ), we will mark the vertexvas visited (visited[v]= true).- Iterate for all the adjacent vertices of
vand for every adjacent vertexa, do following :
ifais not visited i.evisited[a]= false,
and ifahas value1.
recursively call dfs (a).
Complexity Analysis:
The time complexity of the first method is represented in the form of
O(V+E), whereVis the number of verices andEis the number of edges.The space complexity of the algorithm is
O(V)forvisited[]array.
Solutions:
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#define INT_MIN -99999
//ADJACENCY LIST
struct node {
int vertex;
struct node* next;
};
struct node* createNode(int);
struct Graph {
int numVertices;
struct node** adjLists;
};
// Create a node
struct node* createNode(int v) {
struct node* newNode = malloc(sizeof(struct node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
// Create a graph
struct Graph* createAGraph(int vertices) {
struct Graph* graph = malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->adjLists = malloc(vertices * sizeof(struct node*));
int i;
for (i = 0; i < vertices; i++)
graph->adjLists[i] = NULL;
return graph;
}
// Add edge
void addEdge(struct Graph* graph, int s, int d) {
// Add edge from s to d
struct node* newNode = createNode(d);
newNode->next = graph->adjLists[s];
graph->adjLists[s] = newNode;
// Add edge from d to s
newNode = createNode(s);
newNode->next = graph->adjLists[d];
graph->adjLists[d] = newNode;
}
void dfs(struct Graph *adj,int visited[], int v)
{
visited[v]= 1;
struct node *u = adj->adjLists[v];
while(u)
//for (i = adj[v].begin(); i != adj[v].end(); ++i)
{
if(!visited[u->vertex])
dfs(adj,visited,u->vertex);
u= u->next;
}
}
int isTree(struct Graph *adj,int n)
{
int visited[n];
for (int i = 0; i < n; i++)
{visited[i] = 0; }
dfs(adj,visited,0);
for (int u = 0; u < n; u++)
if (!visited[u])
return 0;
return 1;
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
int n,e;
scanf("%d %d",&n,&e);
struct Graph* graph = createAGraph(n);
int edge = e;
while(e--)
{
int u,v;
scanf("%d %d",&u,&v);
addEdge(graph, u,v);
}
if(edge == n-1 && isTree(graph,n))
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
#include<iostream>
#include <list>
#include <limits.h>
using namespace std;
class Graph
{
int V;
list<int> *adj;
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
void dfs(bool visited[],int i);
bool isTree(); // returns true if graph is tree
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::dfs(bool visited[], int v)
{
visited[v]= true;
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
{
if(!visited[*i])
dfs(visited,*i);
}
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
adj[w].push_back(v);
}
bool Graph::isTree()
{
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
dfs(visited,0);
for (int u = 0; u < V; u++)
if (!visited[u])
return false;
return true;
}
int main()
{
int t;
cin>>t;
while(t--){
int n,e;
cin>>n>>e;
Graph g1(n);
int edge = e;
while(e--)
{
int u,v;
cin>>u>>v;
g1.addEdge(u,v);
}
if(edge == n-1 && g1.isTree())
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
import java.io.*;
import java.util.*;
class Graph
{
private int V; // No. of vertices
private LinkedList<Integer> adj[]; //Adjacency List
// Constructor
Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
// Function to add an edge into the graph
void addEdge(int v,int w)
{
adj[v].add(w);
adj[w].add(v);
}
Boolean isCyclicUtil(int v, Boolean visited[], int parent)
{
visited[v] = true;
Integer i;
Iterator<Integer> it = adj[v].iterator();
while (it.hasNext())
{
i = it.next();
if (!visited[i])
{
if (isCyclicUtil(i, visited, v))
return true;
}
else if (i != parent)
return true;
}
return false;
}
Boolean isTree()
{
Boolean visited[] = new Boolean[V];
for (int i = 0; i < V; i++)
visited[i] = false;
if (isCyclicUtil(0, visited, -1))
return false;
for (int u = 0; u < V; u++)
if (!visited[u])
return false;
return true;
}
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int t= sc.nextInt();
while(t-- !=0)
{
int n,e;
n = sc.nextInt();
e = sc.nextInt();
Graph g1 = new Graph(n);
while(e--!=0)
{
int u,v;
u = sc.nextInt();
v = sc.nextInt();
g1.addEdge(u,v);
}
if (g1.isTree())
System.out.println("YES");
else
System.out.println("NO");
}
}
}
[forminator_quiz id="1928"]
This article tried to discuss Graph. Hope this blog helps you understand and solve the problem. To practice more problems on Graph you can check out MYCODE | Competitive Programming.