Posted on by Kalkicode
Code Graph

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

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

  2. The visited array keeps track of visited vertices to avoid cycles and redundant traversal.

  3. In the dfs function, mark the current_vertex as visited and iterate through its neighbors.

  4. For each unvisited neighbor, recursively call the dfs function on that neighbor.

  5. If any recursive call returns true, it means a path exists, and the function should propagate this information upward.

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

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