Minimum number of edges between two vertices

Minimum number of edges between two vertices

Here given code implementation process.

//Minimum number of edges between two vertices of a Graph
#include <stdio.h>
#include <stdlib.h>
#include <limits.h> //for INT_MAX
struct AjlistNode
{
  int vId;//Vertices id
  struct AjlistNode*next;
};

struct Graph
{
  int data; //node key value
  struct AjlistNode*next;
};

int size;
  //set node key value
void setData(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");
  }
}
//Add Edge from Two given Nodes
void addEdge(struct Graph*node, int V ,int E)
{
    //add edge form V to E
    //V and E is Node location
  if (V<size && E <size)
  {
    //First 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");
    }
  }else
  {
        //not valid Vertices
    printf("Invalid Node Vertices %d  %d", V,E);
  }
}
void minEdge(int start,
  int end,
  int *visit,
  struct Graph*node,
  int*result,
  int edge)
{

  if (start >size || end >size || start<0 || end<0 || node==NULL)
  {
    //invalid input
    return ;
  }

  if (visit[start]==1)
  {
    return;
  }
  if (start==end)
  {
    if ( edge < *result)
    {
      *result=edge;
    }
  }
  visit[start]=1;
  struct AjlistNode *temp=node[start].next;
  while(temp!=NULL)
  {
    minEdge(temp->vId,end,visit,node,result,edge+1); 

    temp=temp->next;
  }
  visit[start]=0;

}


//Display Adjacency list of vertex
void printGraph(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");
  }
}
int main()
{
  
  size=7; //set number of nodes

  struct Graph*node=NULL;

  node=(struct Graph*)malloc(sizeof(struct Graph)*size);

  if (node==NULL)
  {
    printf("\n Memory overflow");
  }else
  {
    //First set node keys
    setData(node); 
    //Connected two node with Edges
    addEdge(node,0, 1);
    addEdge(node,0, 6);
    addEdge(node,1, 2);
    addEdge(node,1, 4);
    addEdge(node,2, 0);
    addEdge(node,2, 4);
    addEdge(node,3, 5); 
    addEdge(node,4, 3); 
    addEdge(node,5, 4); 
    addEdge(node,6, 3);
    printGraph(node);


    int result = INT_MAX,
        source = 2,
      destination = 5;

    int *visit=(int*)calloc(size,sizeof(int));
    
    //assume node are exist in graph
    minEdge(source,destination,visit,node,&result,0);

    printf("\n Minimum Edges in  between nodes \
[ %d , %d] is %d\n",source,destination,result );
  }  
  return 0;
}

Output

 Adjacency list of vertex 0  :  1  6
 Adjacency list of vertex 1  :  2  4
 Adjacency list of vertex 2  :  0  4
 Adjacency list of vertex 3  :  5
 Adjacency list of vertex 4  :  3
 Adjacency list of vertex 5  :  4
 Adjacency list of vertex 6  :  3
 Minimum Edges in  between nodes [ 2 , 5] is 3
//C++ program
//Minimum number of edges between two vertices of a Graph
#include <iostream>
#include <limits.h> //for INT_MAX
using namespace std;

struct AjlistNode
{
    int vId;//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 setData();
  void addEdge(int,int);
  void printGraph();
  void connect(int  ,int );
  void count_edge(int ,int);
  void min_edges(int,int ,int* ,int*,int);

};
Graph::Graph(int size)
{
  this->size = size;
    //set number of nodes
  node = new Vertices[size];
}
//set node key value
void Graph:: setData()
{
  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 start ,int end)
{
    //add edge form start to end
    //start and end is Node location
    //first create Adjacency node
  AjlistNode *newEdge=new AjlistNode;

  if(newEdge!=NULL)
  {

    newEdge->next = NULL;
    newEdge->vId = end;

    AjlistNode *temp=node[start].next;

    if(temp==NULL)
    {
      node[start].next=newEdge;
    }else
    {
            //Add node at last
      while(temp->next!=NULL)
      {
        temp=temp->next;
      }      
      temp->next=newEdge;          
    }
  }

}


void Graph ::  addEdge(int V ,int E)
{
  //add edge form V to E
  //V and E is Node location
  if(V<size && E <size)
  {
    connect(V,E);
  }else
  {
        //not valid Vertices
    cout<<"Invalid Node Vertices "<< V<<" "<<E;
  }
}

//Display Adjacency list of vertex
void Graph:: printGraph()
{
  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->vId is graph node vertices
        //in this case temp->vId is same as 
        //node[temp->vId].data

        cout<<" "<<node[temp->vId].data;
        temp=temp->next;
      }
    }
  }else
  {
    cout<<"Empty Graph"<<endl;
  }
}



void Graph:: min_edges(int start,
  int end,
  int visit[],
  int*result,
  int edge)
{

  if (start >size || end >size || start<0 || end<0 || node==NULL)
  {
    //invalid input
    return ;
  }
  if (visit[start]==1)
  {
    return;
  }
  if (start==end)
  {
    if ( edge < *result)
    {
      *result=edge;
    }
  }
  visit[start]=1;
  AjlistNode *temp=node[start].next;
  while(temp!=NULL)
  {
    min_edges(temp->vId,end,visit,result,edge+1); 
    temp=temp->next;
  }
  visit[start]=0;
}
void Graph :: count_edge(int source,int destination)
{

  int result = INT_MAX;

  int visit[size];

  for(int i=0;i<size;i++)
  {
    visit[i]=0;
  }
  min_edges(source,destination,visit,&result,0);
  cout<<"\n Minimum Edges in between nodes \
  [ "<< source <<","<< destination <<"] is "<< result<<"\n";
}
int main()
{
  //Create Object
  Graph g=Graph(7); //7 nodes
  //First set node keys
  g.setData();

  //Connected two node with Edges
  g.addEdge(0, 1);
  g.addEdge(0, 6);
  g.addEdge(1, 2);
  g.addEdge(1, 4);
  g.addEdge(2, 0);
  g.addEdge(2, 4);
  g.addEdge(3, 5); 
  g.addEdge(4, 3); 
  g.addEdge(5, 4); 
  g.addEdge(6, 3);

  g.printGraph();

  //value 2 is source node
  int source = 2;
  //value 5 is destination node
  int destination = 5;

  g.count_edge(source,destination);

  return 0;
}

Output

 Adjacency list of vertex 0 : 1 6
 Adjacency list of vertex 1 : 2 4
 Adjacency list of vertex 2 : 0 4
 Adjacency list of vertex 3 : 5
 Adjacency list of vertex 4 : 3
 Adjacency list of vertex 5 : 4
 Adjacency list of vertex 6 : 3
 Minimum Edges in between nodes   [ 2,5] is 3
//Java program
//Minimum number of edges between two vertices of a Graph
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,result;
    Vertices node[];

    MyGraph(int size)
    {
        //set value
        this.size = size;
        result = 1;
        node = new Vertices[size];
        
    }

    //set initial node value
    public void setData()
    {
        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 addEdge(int start,int end)
    {
        if(start < size && end < size && node != null)
        {
            connect(start,end);

        }else
        {
            System.out.println("\nEmpty Graph");
        }
    }

    public void printGraph()
    {

        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;
                }
            }
        }
    }
    public void min_edges(int start,
      int end,
      boolean []visit,
      int edge)
    {

        if (start >size || end >size || start<0 || end<0 || node==null)
        {
            //invalid input
            return ;
        }
        if (visit[start]==true)
        {
            return;
        }
        if (start==end)
        {
            if ( edge <  result)
            {
                result=edge;
            }
        }
        visit[start]=true;
        AjlistNode temp=node[start].next;
        while(temp!=null)
        {
            min_edges(temp.id,end,visit,edge+1); 
            temp=temp.next;
        }
        visit[start]=false;
    }
    public void  count_edge(int source,int destination)
    {
        //for resultant paths
        result=Integer.MAX_VALUE;
        boolean []visit=new boolean[size];
        for(int i=0; i < size; i++)
        {
            visit[i]=false;
        }
        min_edges(source,destination,visit,0);
        System.out.println("\n Minimum Edges in between nodes ["+ source +","+ destination +"] is "+ result+"\n");
    }

    public static void main(String[] args) 
    {
        int totalNode=7;

        MyGraph g=new MyGraph(totalNode);

        g.setData();

        //Connected two node with Edges
        g.addEdge(0, 1);
        g.addEdge(0, 6);
        g.addEdge(1, 2);
        g.addEdge(1, 4);
        g.addEdge(2, 0);
        g.addEdge(2, 4);
        g.addEdge(3, 5); 
        g.addEdge(4, 3); 
        g.addEdge(5, 4); 
        g.addEdge(6, 3);

        g.printGraph();

        //value 2 is source node
        int source = 2;
        //value 5 is destination node
        int destination = 5;

        g.count_edge(source,destination);

    }
}

Output

Adjacency list of vertex 0 :  1  6
Adjacency list of vertex 1 :  2  4
Adjacency list of vertex 2 :  0  4
Adjacency list of vertex 3 :  5
Adjacency list of vertex 4 :  3
Adjacency list of vertex 5 :  4
Adjacency list of vertex 6 :  3
 Minimum Edges in between nodes [2,5] is 3
import sys
#Python program
#Minimum number of edges between two vertices of a Graph
class AjLinkeNode:
  def __init__(self,data):
    self.id=data
    self.next=None

class Vertices:
  def __init__(self,data):
    self.data=data
    self.next=None

class Graph:
  """Constructor for Graph"""
  def __init__(self, size):
    self.size=size
    self.node=[]
    self.result=0
    

  def setData(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 addEdge(self,start,end):
     
    #start,end is two nodes
    if(self.size > start and self.size > start):
      
      self.connect(start,end)

    else:
      print("Invalid nodes")


  def printGraph(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.id),end=" ")

          temp=temp.next

        index+=1

  

  def min_edges(self,start,end,visit,edge) :

        if (start >self.size  or  end >self.size or start<0 or end<0 or self.node==None) :

            #invalid input
            return 
        if (visit[start]==True) :

            return
        if (start==end) :

            if (edge < self.result) :

              self.result=edge

        visit[start]=True

        temp=self.node[start].next

        while(temp!=None) :

          self.min_edges(temp.id,end,visit,edge +1) 
          temp=temp.next
        visit[start]=False

  def  count_edge(self,source,destination) :

    #for resultant paths
    self.result=sys.maxsize
    visit=[False]*self.size

    self.min_edges(source,destination,visit,0)
    print("\n  Minimum Edges in between nodes [",source,",",destination,"] : ",self.result)
    


    
def main():
  g=Graph(7)
  g.setData() 

  #Connected two node with Edges
  g.addEdge(0, 1)
  g.addEdge(0, 6)
  g.addEdge(1, 2)
  g.addEdge(1, 4)
  g.addEdge(2, 0)
  g.addEdge(2, 4)
  g.addEdge(3, 5) 
  g.addEdge(4, 3) 
  g.addEdge(5, 4) 
  g.addEdge(6, 3)
  g.printGraph()
  #value 2 is source node
  source = 2
  #value 5 is destination node
  destination = 5
  g.count_edge(source,destination)

if __name__=="__main__":
    main()

Output

Adjacency list of vertex 0 :   1  6 
Adjacency list of vertex 1 :   2  4 
Adjacency list of vertex 2 :   0  4 
Adjacency list of vertex 3 :   5 
Adjacency list of vertex 4 :   3 
Adjacency list of vertex 5 :   4 
Adjacency list of vertex 6 :   3 
  Minimum Edges in between nodes [ 2 , 5 ] :  3
//C# program
//Minimum number of edges between two vertices of a Graph
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,result;
  public Vertices []node;

  MyGraph(int size)
  {
    //set value
    this.size = size;
    result = 1;
    node = new Vertices[size];

  }

  //set initial node value
  public void setData()
  {
    if(node == null)
    {
      Console.WriteLine("\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 addEdge(int start,int end)
  {
    if(start < size && end < size && node != null)
    {
      connect(start,end);

    }else
    {
      Console.WriteLine("\nEmpty Graph");
    }
  }

  public void printGraph()
  {

    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;
        }
      }
    }
  }
  public void min_edges(int start,
    int end,
    Boolean []visit,
    int edge)
  {

    if (start >size || end >size || start<0 || end<0 || node==null)
    {
      //invalid input
      return ;
    }
    if (visit[start]==true)
    {
      return;
    }
    if (start==end)
    {
      if ( edge <  result)
      {
        result=edge;
      }
    }
    visit[start]=true;
    AjlistNode temp=node[start].next;
    while(temp!=null)
    {
      min_edges(temp.id,end,visit,edge+1); 
      temp=temp.next;
    }
    visit[start]=false;
  }
  public void  count_edge(int source,int destination)
  {
    //for resultant paths
    result = int.MaxValue;
    Boolean []visit = new Boolean[size];
    for(int i=0; i < size; i++)
    {
      visit[i]=false;
    }
    min_edges(source,destination,visit,0);
    Console.WriteLine("\n Minimum Edges in between nodes ["+ source +","+ destination +"] is "+ result+"\n");
  }

  public static void Main(String[] args) 
  {
    int totalNode=7;

    MyGraph g=new MyGraph(totalNode);

    g.setData();

    //Connected two node with Edges
    g.addEdge(0, 1);
    g.addEdge(0, 6);
    g.addEdge(1, 2);
    g.addEdge(1, 4);
    g.addEdge(2, 0);
    g.addEdge(2, 4);
    g.addEdge(3, 5); 
    g.addEdge(4, 3); 
    g.addEdge(5, 4); 
    g.addEdge(6, 3);

    g.printGraph();

    //value 2 is source node
    int source = 2;
    //value 5 is destination node
    int destination = 5;

    g.count_edge(source,destination);

  }
}

Output


Adjacency list of vertex 0 :  1  6
Adjacency list of vertex 1 :  2  4
Adjacency list of vertex 2 :  0  4
Adjacency list of vertex 3 :  5
Adjacency list of vertex 4 :  3
Adjacency list of vertex 5 :  4
Adjacency list of vertex 6 :  3
 Minimum Edges in between nodes [2,5] is 3
<?php 
/*
* PHP Program 
  Minimum number of edges between two vertices of a Graph
*/

  class AjlistNode
  {
    public $vId;
    public $next;
    function __construct($vId)
    {
      $this->vId=$vId;
      $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 setData()
  {
    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 addEdge($start,$end)
  {
    if($this->size > $start && $this->size>$end)
    {
      $this->connect($start,$end);
    }
    else
    {
      echo "\n Invalid node";
    }
  }
  public function printGraph()
  {
    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->vId]->data);
          $temp=$temp->next;
        }
      }
    }
  }
  public function  min_edges($start,$end,$visit,&$result,$edge)
  {

    if ($start > $this->size|| $end>$this->size|| $start<0|| $end<0|| $this->node==NULL)
    {
      //invalid input
      return ;
    }
    if ($visit[$start]==true)
    {
      return;
    }
    if ($start== $end)
    {
      if ($edge<$result)
      {
        $result= $edge;
      }
    }
    $visit[$start]=true;
    $temp =  $this->node[$start]->next;
    while($temp!=NULL)
    {
      $this->min_edges($temp->vId,$end,$visit,$result,$edge+1); 
      $temp=$temp->next;
    }
    $visit[$start]=false;
  }

  public function count_edge($source,$destination)
  {
    //for resultant paths
    $result= PHP_INT_MAX;
    $visit= array_fill(0, $this->size, false);
    $this->min_edges($source,$destination,$visit,$result,0);
    echo "\n Minimum Edges in between nodes[". $source.",". $destination."] is ". $result."\n";
  }

}


function main()
{
    //create object
  $g=new MyGraph(7);
  $g->setData();

  //Connected two node with Edges
  $g->addEdge(0,1);
  $g->addEdge(0,6);
  $g->addEdge(1,2);
  $g->addEdge(1,4);
  $g->addEdge(2,0);
  $g->addEdge(2,4);
  $g->addEdge(3,5); 
  $g->addEdge(4,3); 
  $g->addEdge(5,4); 
  $g->addEdge(6,3);
  
  $g->printGraph();
  
  //value 2 is source node
  $source=2;
  //value 5 is destination node
  $destination=5;
  
  $g->count_edge($source,$destination);

}
main();
?>

Output

Adjacency list of vertex 0 :   1  6
Adjacency list of vertex 1 :   2  4
Adjacency list of vertex 2 :   0  4
Adjacency list of vertex 3 :   5
Adjacency list of vertex 4 :   3
Adjacency list of vertex 5 :   4
Adjacency list of vertex 6 :   3
 Minimum Edges in between nodes[2,5] is 3


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







© 2021, kalkicode.com, All rights reserved