Posted on by Kalkicode
Code Graph

# Count all possible paths between two vertices

Counting all possible paths between two vertices in a graph involves finding the total number of distinct paths that can be taken from a starting vertex to a destination vertex, while traversing the edges of the graph.

The number of paths between two vertices can be computed using a graph traversal algorithm, such as depth-first search (DFS) or breadth-first search (BFS), which can explore all possible paths between two vertices.

The basic idea is to start from the source vertex, and explore all its adjacent vertices, recursively repeating the process for each adjacent vertex until the destination vertex is reached. During the traversal, we keep track of the number of paths that we have explored from the source vertex to the destination vertex.

Here is the algorithm to count all possible paths between two vertices in a graph:

1. Initialize a variable count to 0.
2. Start a DFS or BFS traversal from the source vertex.
3. For each adjacent vertex of the current vertex that has not been visited yet, recursively call the traversal function.
4. If the current vertex is the destination vertex, increment the count by 1.
5. When the traversal is complete, return the count.

Note that this algorithm assumes that the graph is a directed graph, meaning that the edges have a specific direction. If the graph is undirected, meaning that edges can be traversed in both directions, we would need to modify the algorithm to avoid revisiting nodes that we have already explored.

## Program List

``````//C Program to
//Count all possible paths between two vertices
#include<stdio.h>
#include<stdlib.h>

struct AjlistNode{
int vId;//Vertices id
struct AjlistNode*next;
};

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

int size; //number of nodes

//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);
}
}
//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");
}
}

//This function are capable to count all path between two nodes
void count_path(int start,
int end,
int *visit,
struct Graph*node,
int*result)
{

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

if(visit[start]==1)
{
//node is already visited
return;
}
if(start==end)
{
//when source and destination are get
*result=(*result)+1;
}
//active the visiting node status
visit[start]=1;

struct AjlistNode *temp=node[start].next;

while(temp!=NULL)
{
//check node by edges
count_path(temp->vId,end,visit,node,result);

temp=temp->next;
}
//inactive current visiting node status
visit[start]=0;
}

int main()
{

size=6; //set number of nodes
struct Graph*node=NULL;

int *visit=(int*)calloc(size,sizeof(int));

//Creating memory of graph nodes
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

printGraph(node);

//value 0 is source node
int source = 0;

//value 4 is destination node
int destination = 4;

//for resultant paths
int result=0;

count_path(source,destination,visit,node,&result);

printf("\n Possible Path : %d\n",result );
}
return 0;
}``````

#### Output

`````` Adjacency list of vertex 0  :  1  3
Adjacency list of vertex 1  :  2  4
Adjacency list of vertex 2  :  3  4  5
Adjacency list of vertex 3  :  1  5
Adjacency list of vertex 4  :
Adjacency list of vertex 5  :  4
Possible Path : 8
``````
``````//C++ program
//Count all possible paths between two vertices
#include <iostream>
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 printGraph();
void connect(int  ,int );
void count_path(int,int ,int* ,int*);
void total_path(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;
}
}

//This function are capable to count all path between two nodes
void Graph:: count_path(int start,
int end,
int *visit,
int*result)
{
if(start >size
|| end >size
|| start<0
|| end<0
|| node==NULL)
{
//invalid node location
return ;
}
if(visit[start]==1)
{
//node is already visited
return;
}
if(start==end)
{
//when source and destination are get
*result=(*result)+1;
}
//active the visiting node status
visit[start]=1;
AjlistNode *temp=node[start].next;
while(temp!=NULL)
{
//check node by edges
count_path(temp->vId,end,visit,result);
temp=temp->next;
}
//inactive current visiting node status
visit[start]=0;
}

void Graph :: total_path(int source,int destination)
{
//for resultant paths
int result=0;
int visit[size];
for(int i=0;i<size;i++)
{
visit[i]=0;
}
count_path(source,destination,visit,&result);
cout<<"\n Possible Path : "<<result<<"\n";
}

int main()
{
//Create Object
Graph g=Graph(6); //6 nodes
//First set node keys
g.setData();

//Connected two node with Edges

g.printGraph();

//value 0 is source node
int source = 0;
//value 4 is destination node
int destination = 4;

g.total_path(source,destination);

return 0;
}``````

#### Output

`````` Adjacency list of vertex 0 : 1 3
Adjacency list of vertex 1 : 2 4
Adjacency list of vertex 2 : 3 4 5
Adjacency list of vertex 3 : 1 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4
Possible Path : 8
``````
``````//Java program
//Count all possible paths between two vertices
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].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;
}
}
}
}
//This function are capable to count all path between two nodes
public void  count_path(int start,int end,boolean []visit)
{
if(start >size
|| end >size
|| start<0
|| end<0
|| node==null)
{
//invalid node location
return ;
}
if(visit[start]==true)
{
//node is already visited
return;
}
if(start==end)
{
//when source and destination are get
result=result+1;
}
//active the visiting node status
visit[start]=true;
AjlistNode  temp=node[start].next;
while(temp!=null)
{
//check node by edges
count_path(temp.id,end,visit);
temp=temp.next;
}
//inactive current visiting node status
visit[start]=false;
}

public void  total_path(int source,int destination)
{
//for resultant paths
result=0;
boolean []visit=new boolean[size];
for(int i=0;i<size;i++)
{
visit[i]=false;
}
count_path(source,destination,visit);
System.out.println("\n Possible Path : "+result);
}

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

MyGraph g=new MyGraph(totalNode);

g.setData();

//Connected two node with Edges

g.printGraph();

//value 0 is source node
int source = 0;
//value 4 is destination node
int destination = 4;

g.total_path(source,destination);

}
}``````

#### Output

``````Adjacency list of vertex 0 :  1  3
Adjacency list of vertex 1 :  2  4
Adjacency list of vertex 2 :  3  4  5
Adjacency list of vertex 3 :  1  5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 :  4
Possible Path : 8
``````
``````#Python program
#Count all possible paths between two vertices
#Using DFS
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):

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

#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

#This function are capable to count all path between two nodes
def count_path(self,start,end,visit) :

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

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

#node is already visited
return
if(start==end) :

#when source and destination are get
self.result+=1

#active the visiting node status
visit[start]=True
temp=self.node[start].next
while(temp!=None) :

#check node by edges
self.count_path(temp.id,end,visit)
temp=temp.next

#inactive current visiting node status
visit[start]=False

def  total_path(self,source,destination) :

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

self.count_path(source,destination,visit)
print("\n Possible Path : ",self.result)

def main():
g=Graph(6)
g.setData()
#Connected two node with Edges
g.printGraph()
#value 0 is source node
source = 0
#value 4 is destination node
destination = 4
g.total_path(source,destination)

if __name__=="__main__":
main()``````

#### Output

``````Adjacency list of vertex 0 :   1  3
Adjacency list of vertex 1 :   2  4
Adjacency list of vertex 2 :   3  4  5
Adjacency list of vertex 3 :   1  5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 :   4
Possible Path :  8
``````
``````//C# program
//Count all possible paths between two vertices
//Using DFS
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].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;
}
}
}
}
//This function are capable to count all path between two nodes
public void  count_path(int start,int end,Boolean []visit)
{
if(start >size
|| end >size
|| start<0
|| end<0
|| node==null)
{
//invalid node location
return ;
}
if(visit[start]==true)
{
//node is already visited
return;
}
if(start==end)
{
//when source and destination are get
result=result+1;
}
//active the visiting node status
visit[start]=true;
AjlistNode  temp=node[start].next;
while(temp!=null)
{
//check node by edges
count_path(temp.id,end,visit);
temp=temp.next;
}
//inactive current visiting node status
visit[start]=false;
}

public void  total_path(int source,int destination)
{
//for resultant paths
result=0;
Boolean []visit=new Boolean[size];
for(int i=0;i<size;i++)
{
visit[i]=false;
}
count_path(source,destination,visit);
Console.WriteLine("\n Possible Path : "+result);
}

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

MyGraph g=new MyGraph(totalNode);

g.setData();

//Connected two node with Edges

g.printGraph();

//value 0 is source node
int source = 0;
//value 4 is destination node
int destination = 4;

g.total_path(source,destination);

}
}``````

#### Output

``````Adjacency list of vertex 0 :  1  3
Adjacency list of vertex 1 :  2  4
Adjacency list of vertex 2 :  3  4  5
Adjacency list of vertex 3 :  1  5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 :  4
Possible Path : 8``````
``````<?php
/*
* PHP Program
//Count all possible paths between two vertices
*/

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;
}
}
{
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;
}
}
}
}

//This function are capable to count all path between two nodes
public function count_path(\$start,
\$end,
&\$visit,
&\$result)
{
if(\$start>\$this->size
|| \$end>\$this->size
|| \$start<0
|| \$end<0
)
{
//invalid node location
return ;
}
if(\$visit[\$start]==true)
{
//node is already visited
return;
}
if(\$start==\$end)
{
//when source and destination are get
\$result=(\$result)+1;
}
//active the visiting node status
\$visit[\$start]=true;
\$temp= \$this->node[\$start]->next;
while(\$temp!=NULL)
{
//check node by edges
\$this->count_path(\$temp->vId,\$end,\$visit,\$result);
\$temp=\$temp->next;
}
//inactive current visiting node status
\$visit[\$start]=false;
}

public function total_path(\$source,\$destination)
{
//for resultant paths
\$result=0;
\$visit= array_fill(0, \$this->size, false);
\$this->count_path(\$source,\$destination,\$visit,\$result);
echo "\n Possible Path : ".\$result."\n";
}

}

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

//Connected two node with Edges

\$g->printGraph();

//value 0 is source node
\$source=0;
//value 4 is destination node
\$destination=4;

\$g->total_path(\$source,\$destination);

}
main();
?>``````

#### Output

``````Adjacency list of vertex 0 :   1  3
Adjacency list of vertex 1 :   2  4
Adjacency list of vertex 2 :   3  4  5
Adjacency list of vertex 3 :   1  5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 :   4
Possible Path : 8
``````

## 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.

Categories
Relative Post