Check if path exists between two vertices in a directed graph

In graph theory, a directed graph (or digraph) consists of a set of vertices (or nodes) and a set of directed edges connecting pairs of vertices. The problem you're addressing here is the classic graph problem of determining whether a path exists between two given vertices in a directed graph.

Problem Statement

Given a directed graph, you need to write a program that checks whether a path exists between two specified vertices.

Description with Example

Consider a scenario where you have a directed graph with seven vertices labeled from 0 to 6. The graph's edges are defined as follows:

Vertex 0 is connected to vertices 1, 2, and 6.
Vertex 1 is connected to vertex 2.
Vertex 2 is connected to vertex 6.
Vertex 3 is connected to vertex 2.
Vertex 4 is connected to vertices 3 and 5.
Vertex 5 is connected to vertex 1.
Vertex 6 is connected to vertex 5.

Check if path exists between two vertices

You are tasked with checking whether a path exists between certain pairs of vertices. Specifically, you want to determine if a path exists between vertex 5 and vertex 2, as well as between vertex 0 and vertex 4.

Idea to Solve

To solve this problem, you can use a Depth-First Search (DFS) algorithm. DFS is a graph traversal algorithm that starts at a source vertex, explores as far as possible along each branch before backtracking. You can modify DFS to determine whether there is a path between two specified vertices.

Pseudocode

function dfs(current_vertex, target_vertex, visited, graph):
    if current_vertex == target_vertex:
        return true
    
    visited[current_vertex] = true
    
    for each neighbor in graph[current_vertex]:
        if not visited[neighbor]:
            if dfs(neighbor, target_vertex, visited, graph):
                return true
    
    return false

function path_exists(graph, start_vertex, end_vertex):
    initialize visited array
    result = dfs(start_vertex, end_vertex, visited, graph)
    
    if result:
        print "Path exists between start_vertex and end_vertex"
    else:
        print "No path exists between start_vertex and end_vertex"

Algorithm Explanation

The dfs function performs a depth-first search from the current_vertex to the target_vertex. If the current vertex is equal to the target vertex, a path has been found, and the function returns true.
The visited array keeps track of visited vertices to avoid cycles and redundant traversal.
In the dfs function, mark the current_vertex as visited and iterate through its neighbors.
For each unvisited neighbor, recursively call the dfs function on that neighbor.
If any recursive call returns true, it means a path exists, and the function should propagate this information upward.
The path_exists function initializes the visited array and calls the dfs function. If the result of dfs is true, a path exists; otherwise, no path exists.

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)

Time Complexity

The time complexity of the DFS-based solution is O(V + E), where V is the number of vertices and E is the number of edges in the graph. This is because, in the worst case, DFS may visit every vertex and edge once.

Check if path exists between two vertices in a directed graph

Problem Statement

Description with Example

Idea to Solve

Pseudocode

Algorithm Explanation

Program solution

Output

Output

Output

Output

Output

Output

Time Complexity

Comment

New Comment