Check if a given graph is tree or not
The problem at hand involves determining whether a given graph is a tree or not. In graph theory, a tree is a special type of graph that is acyclic (no cycles) and connected. It's a fundamental concept with applications in various fields like computer science, network design, and biology. This problem is crucial because trees have unique properties that make them valuable in many algorithms and structures.
Problem Statement
Given a graph, we need to decide whether it meets the criteria of a tree. Specifically, we're looking for the following characteristics:
-
Acyclic
The graph must not have any cycles. A cycle is a path that starts and ends at the same vertex, passing through other vertices.
-
Connected
Every pair of vertices in the graph should be connected by a path.
Example
Let's illustrate the problem with an example. Consider the following graph:

Idea to Solve
To solve this problem, we can utilize a depth-first search (DFS) approach. We'll start at a vertex and explore its adjacent vertices. While doing so, we'll mark vertices as visited. If we encounter a vertex that has already been visited, it implies a cycle exists. After visiting all vertices, we'll check if every vertex has been visited exactly once. If not, the graph is not connected.
Pseudocode
function detect_cycle(point, visit, node):
if visit[point] >= 1:
visit[point] = visit[point] + 1
return
visit[point] = 1
for each neighbor in node[point]:
detect_cycle(neighbor, visit, node)
visit[point] = visit[point] - degree_of(point) // Adjust visit count
function check_tree(node):
create an array visit of size size and initialize all elements to 0
status = 0
for index from 0 to size:
if visit[index] > 0:
status = 1
break
if status == 1:
print("This is a Graph")
else:
print("This is a Tree")
main:
// Create and initialize the graph
create an array node of size size
set_data(node)
add edges to the graph
check_tree(node)
Algorithm Explanation
-
detect_cycle
function uses DFS to traverse the graph. If we encounter a vertex that has been visited before, we increment its visit count. This signifies that we're revisiting a vertex, indicating the presence of a cycle. After visiting all neighbors, we adjust the visit count based on the number of neighbors. If the visit count becomes negative, it means we've accounted for all paths from that vertex. -
check_tree
function initializes an arrayvisit
to keep track of vertex visits. If a vertex has been visited more than once, it's part of a cycle. After visiting all vertices, if any vertex has not been visited, the graph is not connected.
Code Solution
//C Program
//Check if a given graph is tree or not
#include <stdio.h>
#include <stdlib.h>
struct AjlistNode
{
//Vertices id
int vId;
struct AjlistNode*next;
};
struct Graph
{
//node key value
int data;
struct AjlistNode*next;
};
int size; //number of nodes
//set node key value
void set_data(struct Graph*node)
{
if(node!=NULL && size>0)
{
int index=0;
for(index; index < size; index++)
{
//set vertic node data
node[index].data = index;//set node key
//Initial no AjlistNode
//set NULL Value
node[index].next = NULL;
}
}else
{
printf("Vertic Node is Empty");
}
}
void connect_edge(struct Graph*node, int V ,int E)
{
// create Adjacency node
struct AjlistNode *newEdge=(struct AjlistNode*)malloc(
sizeof(struct AjlistNode)
);
if(newEdge!=NULL)
{
newEdge->next=NULL;
newEdge->vId=E;
struct AjlistNode *temp = node[V].next;
if(temp==NULL)
{
node[V].next=newEdge;
}
else
{
//Add node at last
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=newEdge;
}
}
else
{
printf("\n Memory overflow");
}
}
//Add Edge from Two given Nodes
void add_edge(struct Graph*node, int V ,int E)
{
//add edge form V to E
//V and E is Node location
if(V<size && E <size)
{
connect_edge(node,V,E);
if(V==E)
{
return;//self loop
}
connect_edge(node,E,V);
}
else
{
//not valid Vertices
printf("Invalid Node Vertices %d %d", V,E);
}
}
//Display Adjacency list of vertex
void print_graph(struct Graph*node)
{
if(node!=NULL)
{
struct AjlistNode *temp=NULL;
for(int index=0;index<size;index++)
{
printf("\n Adjacency list of vertex %d :",index);
temp=node[index].next;
while(temp!=NULL)
{
//temp->vId is graph node vertices
//in this case temp->vId is same as
//node[temp->vId].data
printf(" %d",node[temp->vId].data);
temp=temp->next;
}
}
}
else
{
printf("Empty Graph");
}
}
//Detecting cycle in graph
void detect_cycle(int point,int *visit,struct Graph*node)
{
if(visit[point]>=1)
{
visit[point]=visit[point]+1;
return;
}
visit[point]=1;
struct AjlistNode *temp=node[point].next;
int counter=0;
while(temp!=NULL)
{
counter++;
detect_cycle(temp->vId,visit,node);
temp=temp->next;
}
if(counter>0)
{
visit[point]=visit[point]-counter;
if(visit[point]<0)
{
visit[point]=-visit[point];
}
}
}
void check_tree(struct Graph*node)
{
if(node==NULL)
{
printf("Empty Graph\n");
return;
}
print_graph(node);
int *visit=(int*)calloc(size,sizeof(int));
int test=0,status=0;
detect_cycle(test,visit,node);
printf("\n Result : ");
for(int index=0; index < size; index++)
{
if(index==0 && visit[index] == 1)
{
//This are start vertex
continue;
}
if(visit[index]>0)
{
status=1;
break;
}
}
if(status==1)
{
//When cycle exist
printf("This is an Graph\n");
}
else
{
//When no cycle exist
printf("This is an Tree\n");
}
}
int main()
{
size=6;
struct Graph*node=node=(struct Graph*)malloc(
sizeof(struct Graph)*size
);
if(node==NULL)
{
printf("\n Memory overflow");
}
else
{
//First set node keys
set_data(node);
//Connected two node with Edges
add_edge(node,0,1);
add_edge(node,1,2);
add_edge(node,2,3);
add_edge(node,3,4);
add_edge(node,3,5);
check_tree(node);
add_edge(node,4,0);
//Case two
check_tree(node);
}
return 0;
}
Output
Adjacency list of vertex 0 : 1
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 1 3
Adjacency list of vertex 3 : 2 4 5
Adjacency list of vertex 4 : 3
Adjacency list of vertex 5 : 3
Result : This is an Tree
Adjacency list of vertex 0 : 1 4
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 1 3
Adjacency list of vertex 3 : 2 4 5
Adjacency list of vertex 4 : 3 0
Adjacency list of vertex 5 : 3
Result : This is an Graph
//C++ program
//Check if a given graph is tree or not
#include <iostream>
using namespace std;
struct AjlistNode
{
int id;//Vertices id
struct AjlistNode*next;
};
struct Vertices
{
int data; //node key value
struct AjlistNode*next;
};
class Graph
{
Vertices *node;
int size;//number of
public:
Graph(int);
void set_data();
void add_edge(int,int);
void print_graph();
void connect(int ,int );
void detect_cycle(int point,int *visit);
void check_tree();
};
Graph::Graph(int size)
{
this->size = size;
//set number of nodes
node = new Vertices[size];
}
//set node key value
void Graph:: set_data()
{
if(node!=NULL)
{
int index=0;
for(index;index<size;index++)
{
//set vertic node data
node[index].data=index;//set node key
//Initial no AjlistNode
//set NULL Value
node[index].next=NULL;
}
}
else
{
cout<<"Vertic Node is Empty"<<endl;
}
}
//Add Edge from Two given Nodes
void Graph:: connect(int V ,int E)
{
//add edge form V to E
//V and E is Node location
//first create Adjacency node
AjlistNode *newEdge=new AjlistNode;
if(newEdge!=NULL)
{
newEdge->next=NULL;
newEdge->id=E;
AjlistNode *temp=node[V].next;
if(temp==NULL)
{
node[V].next=newEdge;
}else
{
//Add node at last
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=newEdge;
}
}
}
void Graph:: add_edge(int V ,int E)
{
//add edge form V to E
//V and E is Node location
if(V<size && E <size)
{
connect(V,E);
if(V != E)
{
connect(E,V);
}
}else
{
//not valid Vertices
cout<<"Invalid Node Vertices "<< V<<" "<<E;
}
}
//Display Adjacency list of vertex
void Graph:: print_graph()
{
if(node!=NULL)
{
AjlistNode *temp=NULL;
for(int index=0; index < size; index++)
{
cout<<"\n Adjacency list of vertex "<<index<<" :";
temp=node[index].next;
while(temp!=NULL)
{
//temp->id is graph node vertices
//in this case temp->id is same as
//node[temp->id].data
cout<<" "<<node[temp->id].data;
temp=temp->next;
}
}
}
else
{
cout<<"Empty Graph"<<endl;
}
}
//Detecting cycle in graph
void Graph:: detect_cycle(int point,int *visit)
{
if (visit[point]>=1)
{
visit[point]=visit[point]+1;
return ;
}
visit[point]=1;
AjlistNode *temp=node[point].next;
int counter=0;
while (temp!=NULL)
{
counter++;
detect_cycle(temp->id,visit);
temp=temp->next;
}
if (counter>0)
{
visit[point]=visit[point]-counter;
if (visit[point]<0)
{
visit[point]=-visit[point];
}
}
}
void Graph:: check_tree()
{
if (node==NULL)
{
cout<<"Empty Graph\n";
return ;
}
print_graph();
int visit[size] ={0};
int test=0,status=0;
detect_cycle(test,visit);
cout<<"\n Result : ";
for (int index=0; index < size; index++)
{
if (index==0 && visit[index] == 1)
{
//This are start vertex
continue;
}
if (visit[index]>0)
{
status=1;
break ;
}
}
if (status==1)
{
//When cycle exist
cout<<"This is an Graph\n";
}
else
{
//When no cycle exist
cout<<"This is an Tree\n";
}
}
int main()
{
//Create Object
Graph g = Graph(6);
//First set node keys
g.set_data();
//Connected two node with Edges
g.add_edge(0,1);
g.add_edge(1,2);
g.add_edge(2,3);
g.add_edge(3,4);
g.add_edge(3,5);
g.check_tree();
g.add_edge(4,0);
//Case two
g.check_tree();
return 0;
}
Output
Adjacency list of vertex 0 : 1
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 1 3
Adjacency list of vertex 3 : 2 4 5
Adjacency list of vertex 4 : 3
Adjacency list of vertex 5 : 3
Result : This is an Tree
Adjacency list of vertex 0 : 1 4
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 1 3
Adjacency list of vertex 3 : 2 4 5
Adjacency list of vertex 4 : 3 0
Adjacency list of vertex 5 : 3
Result : This is an Graph
//Java program
//Check if a given graph is tree or not
public class MyGraph
{
static class AjlistNode
{
int id;//Vertices node key
AjlistNode next;
}
static class Vertices
{
int data;
AjlistNode next;
}
//number of Vertices
public int size;
public Vertices []node;
MyGraph(int size)
{
//set value
this.size = size;
node = new Vertices[size];
}
//set initial node value
public void set_data()
{
if(node == null)
{
System.out.println("\nEmpty Graph");
}else
{
for(int index = 0; index < size; index++)
{
// avoid java.lang.nullPointerException
node[index]=new Vertices();
node[index].data=index;//set your data
node[index].next=null;
}
}
}
//connect two nodes
public void connect(int start,int end)
{
AjlistNode newEdge=new AjlistNode();
newEdge.id=end;//end node
newEdge.next=null;
if(node[start].next==null)
{
node[start].next=newEdge;
}else
{
AjlistNode temp=node[start].next;
while(temp.next!=null)
{
temp=temp.next;
}
temp.next=newEdge;
}
}
//Add edge at the end
public void add_edge(int start,int end)
{
if(start < size && end < size && node != null)
{
connect(start,end);
if(start!=end)
{
connect(end,start);
}
}
else{
System.out.println("\nInvalid nodes "+start+" "+end);
}
}
public void print_graph()
{
if(size>0 && node!=null)
{
for(int index=0;index<size;index++)
{
System.out.print("\nAdjacency list of vertex "+index+" :");
AjlistNode temp=node[index].next;
while(temp!=null)
{
System.out.print(" "+node[temp.id].data);
temp=temp.next;
}
}
}
}
//Detecting cycle in graph
public void detect_cycle(int point,int []visit)
{
if (visit[point]>=1)
{
visit[point]=visit[point]+1;
return ;
}
visit[point]=1;
AjlistNode temp=node[point].next;
int counter=0;
while (temp!=null)
{
counter++;
detect_cycle(temp.id,visit);
temp=temp.next;
}
if (counter>0)
{
visit[point]=visit[point]-counter;
if (visit[point]<0)
{
visit[point]=-visit[point];
}
}
}
public void check_tree()
{
if (node==null)
{
System.out.print("Empty Graph\n");
return ;
}
print_graph();
int []visit=new int[size];
for (int i=0;i<size ;i++ )
{
visit[i]=0;
}
int test=0,status=0;
detect_cycle(test,visit);
System.out.print("\n Result : ");
for (int index=0; index < size; index++)
{
if (index==0 && visit[index] ==1)
{
//This are start vertex
continue;
}
if (visit[index]>0)
{
status=1;
break ;
}
}
if (status==1)
{
//When cycle exist
System.out.print("This is an Graph\n");
}
else
{
//When no cycle exist
System.out.print("This is an Tree\n");
}
}
public static void main(String[] args)
{
int totalNode=6;
MyGraph g=new MyGraph(totalNode);
g.set_data();
//Connected two node with Edges
g.add_edge(0,1);
g.add_edge(1,2);
g.add_edge(2,3);
g.add_edge(3,4);
g.add_edge(3,5);
g.check_tree();
g.add_edge(4,0);
//Case two
g.check_tree();
}
}
Output
Adjacency list of vertex 0 : 1
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 1 3
Adjacency list of vertex 3 : 2 4 5
Adjacency list of vertex 4 : 3
Adjacency list of vertex 5 : 3
Result : This is an Tree
Adjacency list of vertex 0 : 1 4
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 1 3
Adjacency list of vertex 3 : 2 4 5
Adjacency list of vertex 4 : 3 0
Adjacency list of vertex 5 : 3
Result : This is an Graph
#Python program
#Check if a given graph is tree or not
class AjLinkeNode:
def __init__(self,data):
self.key=data
self.next=None
class Vertices:
def __init__(self,data):
self.data=data
self.next=None
class Graph:
def __init__(self,size):
self.size=size
self.node=[]
def set_data(self):
if(self.size>0 and self.node!=None):
index=0
while(index<self.size):
self.node.append(Vertices(index))
index+=1
#connect two node with edge
def connect(self,start,end):
new_edge=AjLinkeNode(end)
if(self.node[start].next==None):
self.node[start].next=new_edge
else:
temp=self.node[start].next
while(temp.next!=None):
temp=temp.next
temp.next=new_edge
#add edge
def add_edge(self,start,end):
#start,end is two nodes
if(self.size>start and self.size>start):
self.connect(start,end)
if(start!=end):
self.connect(end,start)
else:
print("Invalid nodes")
def print_graph(self):
if(self.size>0 and self.node!=None):
index=0
while(index<self.size):
print("\nAdjacency list of vertex {0} :".format(index),end=" ")
temp=self.node[index].next
while temp!=None:
print(" {0}".format(temp.key),end=" ")
temp=temp.next
index+=1
#Detecting cycle in graph
def detect_cycle(self, point, visit) :
if (visit[point]>=1) :
visit[point]=visit[point]+1
return
visit[point]=1
temp=self.node[point].next
counter=0
while (temp!=None) :
counter += 1
self.detect_cycle(temp.key,visit)
temp=temp.next
if (counter > 0) :
visit[point]=visit[point]-counter
if (visit[point] < 0) :
visit[point]=-visit[point]
def check_tree(self) :
if (self.node==None) :
print("Empty Graph\n")
return
self.print_graph()
visit =[0]*self.size
i=0
while(i<self.size) :
visit[i]=0
i+=1
status=0
self.detect_cycle(0,visit)
print("\n Result : ",end=" ")
index=0
while (index < self.size ) :
if (index==0 and visit[index] == 1) :
index+=1
#This are start vertex
continue
if (visit[index]>0) :
status=1
break
index+=1
if (status==1) :
#When cycle exist
print("This is an Graph\n")
else :
#When no cycle exist
print("This is an Tree\n" )
def main():
g=Graph(6)
g.set_data();
#Connected two node with Edges
g.add_edge(0,1)
g.add_edge(1,2)
g.add_edge(2,3)
g.add_edge(3,4)
g.add_edge(3,5)
g.check_tree()
g.add_edge(4,0)
#Case two
g.check_tree()
if __name__=="__main__":
main()
Output
Adjacency list of vertex 0 : 1
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 1 3
Adjacency list of vertex 3 : 2 4 5
Adjacency list of vertex 4 : 3
Adjacency list of vertex 5 : 3
Result : This is an Tree
Adjacency list of vertex 0 : 1 4
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 1 3
Adjacency list of vertex 3 : 2 4 5
Adjacency list of vertex 4 : 3 0
Adjacency list of vertex 5 : 3
Result : This is an Graph
//C# program
//Check if a given graph is tree or not
using System;
public class AjlistNode
{
public int id;//Vertices node key
public AjlistNode next;
}
public class Vertices
{
public int data;
public AjlistNode next;
}
public class MyGraph
{
//number of Vertices
public int size;
public Vertices []node;
MyGraph(int size)
{
//set value
this.size = size;
node = new Vertices[size];
}
//set initial node value
public void set_data()
{
if(node == null)
{
Console.WriteLine("\nEmpty Graph");
}else
{
for(int index = 0; index < size; index++)
{
// avoid C#.lang.nullPointerException
node[index]=new Vertices();
node[index].data=index;//set your data
node[index].next=null;
}
}
}
//connect two nodes
public void connect(int start,int end)
{
AjlistNode newEdge=new AjlistNode();
newEdge.id=end;//end node
newEdge.next=null;
if(node[start].next==null)
{
node[start].next=newEdge;
}else
{
AjlistNode temp=node[start].next;
while(temp.next!=null)
{
temp=temp.next;
}
temp.next=newEdge;
}
}
//Add edge at the end
public void add_edge(int start,int end)
{
if(start < size && end < size && node != null)
{
connect(start,end);
if(start!=end)
{
connect(end,start);
}
}
else{
Console.WriteLine("\nInvalid nodes "+start+" "+end);
}
}
public void print_graph()
{
if(size>0 && node!=null)
{
for(int index=0;index<size;index++)
{
Console.Write("\nAdjacency list of vertex "+index+" :");
AjlistNode temp=node[index].next;
while(temp!=null)
{
Console.Write(" "+node[temp.id].data);
temp=temp.next;
}
}
}
}
//Detecting cycle in graph
public void detect_cycle(int point,int []visit)
{
if (visit[point]>=1)
{
visit[point]=visit[point]+1;
return ;
}
visit[point]=1;
AjlistNode temp=node[point].next;
int counter=0;
while (temp!=null)
{
counter++;
detect_cycle(temp.id,visit);
temp=temp.next;
}
if (counter>0)
{
visit[point]=visit[point]-counter;
if (visit[point]<0)
{
visit[point]=-visit[point];
}
}
}
public void check_tree()
{
if (node==null)
{
Console.Write("Empty Graph\n");
return ;
}
print_graph();
int []visit=new int[size];
for (int i=0;i<size ;i++ )
{
visit[i]=0;
}
int test=0,status=0;
detect_cycle(test,visit);
Console.Write("\n Result : ");
for (int index=0; index < size; index++)
{
if (index==0 && visit[index] ==1)
{
//This are start vertex
continue;
}
if (visit[index]>0)
{
status=1;
break ;
}
}
if (status==1)
{
//When cycle exist
Console.Write("This is an Graph\n");
}
else
{
//When no cycle exist
Console.Write("This is an Tree\n");
}
}
public static void Main(String[] args)
{
int totalNode=6;
MyGraph g=new MyGraph(totalNode);
g.set_data();
//Connected two node with Edges
g.add_edge(0,1);
g.add_edge(1,2);
g.add_edge(2,3);
g.add_edge(3,4);
g.add_edge(3,5);
g.check_tree();
g.add_edge(4,0);
//Case two
g.check_tree();
}
}
Output
Adjacency list of vertex 0 : 1
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 1 3
Adjacency list of vertex 3 : 2 4 5
Adjacency list of vertex 4 : 3
Adjacency list of vertex 5 : 3
Result : This is an Tree
Adjacency list of vertex 0 : 1 4
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 1 3
Adjacency list of vertex 3 : 2 4 5
Adjacency list of vertex 4 : 3 0
Adjacency list of vertex 5 : 3
Result : This is an Graph
<?php
/*
* PHP Program
* Check if a given graph is tree or not
*/
class AjlistNode
{
public $key;
public $next;
function __construct($key)
{
$this->key=$key;
$this->next=NULL;
}
}
class Node
{
public $data;
public $next;
function __construct($data)
{
$this->data=$data;
$this->next=NULL;
}
}
class MyGraph
{
public $node;
public $size;
function __construct($size)
{
$this->size=$size;
$this->node=[]; //empty array
}
public function set_data()
{
if($this->size>0)
{
for($index=0;$index<$this->size;$index++)
{
$this->node[$index]=new Node($index);
}
}
}
public function connect($start,$end)
{
$newEdge=new AjlistNode($end);
if($this->node[$start]->next==NULL)
{
$this->node[$start]->next=$newEdge;
}
else
{
$temp=$this->node[$start]->next;
while($temp->next!=NULL)
{
$temp=$temp->next;
}
$temp->next= $newEdge;
}
}
public function add_edge($start,$end)
{
if($this->size > $start && $this->size>$end)
{
$this->connect($start,$end);
if($start!=$end)
{
$this->connect($end,$start);
}
}
else
{
echo "\n Invalkey node";
}
}
public function print_graph()
{
if($this->size>0 && count($this->node)>0 && $this->node!=NULL)
{
for($index=0;$index<$this->size;$index++)
{
echo "\nAdjacency list of vertex ".$index." : ";
$temp=$this->node[$index]->next;
while($temp!=NULL)
{
echo " ".$this->node[$temp->key]->data;
$temp=$temp->next;
}
}
}
}
//Detecting cycle in graph
public function detect_cycle( $point, &$visit)
{
if ($visit[$point]>=1)
{
$visit[$point]=$visit[$point]+1;
return ;
}
$visit[$point]=1;
$temp=$this->node[$point]->next;
$counter=0;
while ($temp!=NULL)
{
$counter++;
$this->detect_cycle($temp->key,$visit);
$temp=$temp->next;
}
if ($counter>0)
{
$visit[$point]=$visit[$point]-$counter;
if ($visit[$point]<0)
{
$visit[$point]=-$visit[$point];
}
}
}
public function check_tree()
{
if ($this->node==NULL)
{
echo "Empty Graph\n";
return ;
}
$this->print_graph();
$visit = array_fill(0, $this->size, 0);
$test=0;
$status=0;
$this->detect_cycle($test,$visit);
echo "\n Result : ";
for ( $index=0; $index < $this->size; $index++)
{
if ($index==0 && $visit[$index] == 1)
{
//This are start vertex
continue;
}
if ($visit[$index]>0)
{
$status=1;
break ;
}
}
if ($status==1)
{
//When cycle exist
echo "This is an Graph\n";
}
else
{
//When no cycle exist
echo "This is an Tree\n";
}
}
}
function main()
{
//create object
$g=new MyGraph(6);
//First set node keys
$g->set_data();
//Connected two node with Edges
$g->add_edge(0,1);
$g->add_edge(1,2);
$g->add_edge(2,3);
$g->add_edge(3,4);
$g->add_edge(3,5);
$g->check_tree();
$g->add_edge(4,0);
//Case two
$g->check_tree();
}
main();
?>
Output
Adjacency list of vertex 0 : 1
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 1 3
Adjacency list of vertex 3 : 2 4 5
Adjacency list of vertex 4 : 3
Adjacency list of vertex 5 : 3
Result : This is an Tree
Adjacency list of vertex 0 : 1 4
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 1 3
Adjacency list of vertex 3 : 2 4 5
Adjacency list of vertex 4 : 3 0
Adjacency list of vertex 5 : 3
Result : This is an Graph
Time Complexity
The time complexity of this algorithm depends on the size of the graph and the number of edges. In the worst case, the DFS process will visit each vertex and edge once, resulting in a time complexity of O(V + E), where V is the number of vertices and E is the number of edges.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment