Check if path exists between two vertices in a directed graph
Checking if a path exists between two vertices in a directed graph involves determining whether there is a sequence of edges that leads from the source vertex to the target vertex.

One way to check if a path exists between two vertices in a directed graph is to perform a depth-first search (DFS) or breadth-first search (BFS) starting from the source vertex, and stop when the target vertex is reached. If the target vertex is visited during the search, then there is a path between the source and target vertices. Otherwise, there is no path between the two vertices.
Another approach is to use the concept of connectivity, where two vertices are said to be connected if there is a path between them. We can use an algorithm such as the strongly connected components (SCC) algorithm or the Tarjan's algorithm to find the SCCs of the graph. If the source and target vertices belong to the same SCC, then there is a path between them.
Overall, checking if a path exists between two vertices in a directed graph can be done efficiently using various graph traversal or connectivity algorithms.
Program solution
//C Program
//Find if there is a path between two vertices in a directed graph
#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;
}
}
printf("\n");
}
else
{
printf("Empty Graph");
}
}
//Detect path between two nodes
void dfs(int start,
int end,
int *visit,
struct Graph*node,
int *result)
{
if(start==end)
{
*result=1;
return;
}
if(visit[start]==1)
{
return;
}
else
{
visit[start]=1;
struct AjlistNode *temp=node[start].next;
while(temp!=NULL)
{
dfs(temp->vId,end,visit,node,result);
temp=temp->next;
}
}
}
void path_exist(struct Graph*node,int start, int end)
{
int *visit=(int*)calloc(size,sizeof(int));
int result=0;
dfs(start,end,visit,node,&result);
if(result==0)
{
printf("\n Path is not exist between (%d-%d) \n",start,end);
}else
{
printf("\n Path is exist between (%d-%d) \n",start,end);
}
free(visit);
visit=NULL;
}
int main()
{
size=7;
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, 2);
addEdge(node,0, 6);
addEdge(node,1, 2);
addEdge(node,2, 6);
addEdge(node,3, 2);
addEdge(node,4, 3);
addEdge(node,4, 5);
addEdge(node,5, 1);
addEdge(node,6, 5);
printGraph(node);
int start=5,end=2;
path_exist(node,start,end);
start=0,end=4;
path_exist(node,start,end);
}
return 0;
}
Output
Adjacency list of vertex 0 : 1 2 6
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 6
Adjacency list of vertex 3 : 2
Adjacency list of vertex 4 : 3 5
Adjacency list of vertex 5 : 1
Adjacency list of vertex 6 : 5
Path is exist between (5-2)
Path is not exist between (0-4)
//C++ program
//Find if there is a path between two vertices in a directed graph
#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 set_data();
void add_edge(int,int);
void print_graph();
void connect(int ,int );
void dfs(int start,int end,int *visit,int *result);
void path_exist(int start, int end);
};
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->vId=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);
}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->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;
}
}
//Detect path between two nodes
void Graph:: dfs(int start,int end, int *visit, int *result)
{
if (start==end)
{
*result=1;
return ;
}
if (visit[start]==1)
{
return ;
}
else
{
visit[start]=1;
AjlistNode *temp=node[start].next;
while (temp!=NULL)
{
dfs(temp->vId,end,visit,result);
temp=temp->next;
}
}
}
void Graph:: path_exist(int start, int end)
{
int visit[size]={0};
int result=0;
dfs(start,end,visit,&result);
if(result==0)
{
cout<<"\n Path is not exist between ("<< start <<" - "<<end <<") ";
}
else
{
cout<<"\n Path is exist between ("<< start <<" - "<< end<<") \n";
}
}
int main()
{
//Create Object
Graph g = Graph(7);
//First set node keys
g.set_data();
//Connected two node with Edges
g.add_edge(0, 1);
g.add_edge(0, 2);
g.add_edge(0, 6);
g.add_edge(1, 2);
g.add_edge(2, 6);
g.add_edge(3, 2);
g.add_edge(4, 3);
g.add_edge(4, 5);
g.add_edge(5, 1);
g.add_edge(6, 5);
g.print_graph();
int start=5,end=2;
g.path_exist(start,end);
start=0,end=4;
g.path_exist(start,end);
return 0;
}
Output
//Java program
//Find if there is a path between two vertices in a directed 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;
public boolean result;
public Vertices []node;
MyGraph(int size)
{
//set value
this.size = size;
result=false;
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);
}
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;
}
}
}
}
//Detect path between two nodes
public void dfs(int start,int end, int []visit)
{
if (start==end)
{
result=false;
return ;
}
if (visit[start]==1)
{
return ;
}
else
{
visit[start]=1;
AjlistNode temp=node[start].next;
while (temp!=null)
{
dfs(temp.vId,end,visit);
temp=temp.next;
}
}
}
public void Graph:: path_exist(int start, int end)
{
boolean []visit=new int[size];
for(int i=0;i<size;i++)
{
visit[i]=false;
}
result=false;
dfs(start,end,visit);
if(result==true)
{
System.out.print("\n Path is not exist between ("+ start +" - "+end +") ");
}
else
{
System.out.print("\n Path is exist between ("+ start +" - "+ end+") \n");
}
}
public static void main(String[] args)
{
int totalNode=7;
MyGraph g=new MyGraph(totalNode);
g.set_data();
g.add_edge(0, 4);
g.add_edge(0, 3);
g.add_edge(1, 0);
g.add_edge(1, 2);
g.add_edge(1, 4);
g.add_edge(2, 4);
g.add_edge(2, 5);
g.add_edge(3, 4);
g.add_edge(5, 4);
g.print_graph();
g.all_paths(1,4);
}
}
Output
Adjacency list of vertex 0 : 1 2 6
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 6
Adjacency list of vertex 3 : 2
Adjacency list of vertex 4 : 3 5
Adjacency list of vertex 5 : 1
Adjacency list of vertex 6 : 5
Path is exist between (5 - 2)
Path is not exist between (0 - 4)
#Python program
#Find if there is a path between two vertices in a directed graph
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=[]
self.result=False
self.visit=None
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)
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
#Detect path between two nodes
def dfs(self, start, end) :
if (start==end) :
self.result=True
return
if (self.visit[start]==True) :
return
else :
self.visit[start]=True
temp=self.node[start].next
while (temp!=None) :
self.dfs(temp.key,end)
temp=temp.next
def path_exist(self, start, end) :
self.visit=[False]*self.size
self.result=False
self.dfs(start,end)
if(self.result==True) :
print("\n Path is not exist between (", start ," - ",end ,") ")
else :
print("\n Path is exist between (", start ," - ", end,") \n")
def main():
g=Graph(7)
g.set_data();
#Connected two node with Edges
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(0, 6)
g.add_edge(1, 2)
g.add_edge(2, 6)
g.add_edge(3, 2)
g.add_edge(4, 3)
g.add_edge(4, 5)
g.add_edge(5, 1)
g.add_edge(6, 5)
g.print_graph()
start=5
end=2
g.path_exist(start,end)
start=0
end=4
g.path_exist(start,end)
if __name__=="__main__":
main()
Output
Adjacency list of vertex 0 : 1 2 6
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 6
Adjacency list of vertex 3 : 2
Adjacency list of vertex 4 : 3 5
Adjacency list of vertex 5 : 1
Adjacency list of vertex 6 : 5
Path is exist between (5 - 2)
Path is not exist between (0 - 4)
//C# program
//Find if there is a path between two vertices in a directed 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;
public Boolean result;
public Vertices []node;
MyGraph(int size)
{
//set value
this.size = size;
result=false;
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);
}
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;
}
}
}
}
//Detect path between two nodes
public void dfs(int start,int end, Boolean []visit)
{
if (start==end)
{
result=true;
return ;
}
if (visit[start]==true)
{
return ;
}
else
{
visit[start]=true;
AjlistNode temp=node[start].next;
while (temp!=null)
{
dfs(temp.id,end,visit);
temp=temp.next;
}
}
}
public void path_exist(int start, int end)
{
Boolean []visit=new Boolean[size];
for(int i=0;i<size;i++)
{
visit[i]=false;
}
result=false;
dfs(start,end,visit);
if(result==false)
{
Console.Write("\nPath is not exist between ("+ start +" - "+end +") ");
}
else
{
Console.Write("\nPath is exist between ("+ start +" - "+ end+") \n");
}
}
public static void Main(String[] args)
{
int totalNode=7;
MyGraph g=new MyGraph(totalNode);
g.set_data();
//Connected two node with Edges
g.add_edge(0, 1);
g.add_edge(0, 2);
g.add_edge(0, 6);
g.add_edge(1, 2);
g.add_edge(2, 6);
g.add_edge(3, 2);
g.add_edge(4, 3);
g.add_edge(4, 5);
g.add_edge(5, 1);
g.add_edge(6, 5);
g.print_graph();
int start=5,end=2;
g.path_exist(start,end);
start=0;
end=4;
g.path_exist(start,end);
}
}
Output
Adjacency list of vertex 0 : 1 2 6
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 6
Adjacency list of vertex 3 : 2
Adjacency list of vertex 4 : 3 5
Adjacency list of vertex 5 : 1
Adjacency list of vertex 6 : 5
Path is exist between (5 - 2)
Path is not exist between (0 - 4)
<?php
/*
* PHP Program
* Find if there is a path between two vertices in a directed graph
*/
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);
}
else
{
echo "\n Invalid 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;
}
}
}
}
//Detect path between two nodes
public function dfs( $start, $end, &$visit, &$result)
{
if ($start==$end)
{
$result=1;
return ;
}
if ($visit[$start]==true)
{
return ;
}
else
{
$visit[$start]=true;
$temp=$this->node[$start]->next;
while ($temp!=NULL)
{
$this->dfs($temp->key,$end,$visit,$result);
$temp=$temp->next;
}
}
}
public function path_exist( $start, $end)
{
$visit=array_fill(0, $this->size, false);
$result=0;
$this->dfs($start,$end,$visit,$result);
if($result==0)
{
echo "\n Path is not exist between (". $start ." - ".$end .") ";
}
else
{
echo "\n Path is exist between (". $start ." - ". $end.") \n";
}
}
}
function main()
{
//create object
$g=new MyGraph(7);
//First set node keys
$g->set_data();
//Connected two node with Edges
$g->add_edge(0, 1);
$g->add_edge(0, 2);
$g->add_edge(0, 6);
$g->add_edge(1, 2);
$g->add_edge(2, 6);
$g->add_edge(3, 2);
$g->add_edge(4, 3);
$g->add_edge(4, 5);
$g->add_edge(5, 1);
$g->add_edge(6, 5);
$g->print_graph();
$start=5;
$end=2;
$g->path_exist($start,$end);
$start=0;
$end=4;
$g->path_exist($start,$end);
}
main();
?>
Output
Adjacency list of vertex 0 : 1 2 6
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 6
Adjacency list of vertex 3 : 2
Adjacency list of vertex 4 : 3 5
Adjacency list of vertex 5 : 1
Adjacency list of vertex 6 : 5
Path is exist between (5 - 2)
Path is not exist between (0 - 4)
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