Skip to main content

Check if a given graph is tree or not

A graph is the form of a tree when the nodes of the graph is not form a loop by together its path. Or graph is not containing any self loops. That is called of an tree.

Check if graph is form of tree

Here given code implementation process.

//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
Last updated on by Kalkicode




Comment

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