# Find if there exists a path between two nodes in a directed graph

#### Algorithms Graph Algorithms

Get FREE domain for 1st year and build your brand new site

You are given a directed graph and two vertices on it. Your task is to find if there exists a path between the first vertex to the second vertex or not.

## Example

#### Input to construct the above graph:

Input:
No. of nodes in graph = 4
No. of edges in graph = 5
Edges:
1 2
2 3
2 4
3 1
3 4
No. of queries = 2
1 4
4 2
Output:
Yes
No


#### Explanation:

For the first query, the answer is Yes because we can construct a path as shown in the diagram below ( 1->2->4 ) but for the second query the answer is No because there are no outgoing edges from vertex four.

## Approach

To solve this problem, we can use either BFS (Breadth First Search) or DFS (Depth First Search) to find if there exists a path between two vertices.

Some important points:
1. For representing nodes we will use 1-indexing or in other words the nodes will be numbered from 1 to number_of_nodes.

2. To represent the graph we will use a 2-D vector in C++ and we will use the adjacency list representation as it gives us lower time and space complexity. We will resize the 2-D vector to contain vectors equal to no. of nodes.

std::vector <std::vector<int>> graph;
graph.resize(number_of_nodes);


## 1. Using BFS

Here we will use Breadth First Search in the solution. Take the first vertex as the source in BFS and if the second vertex is found in traversal print Yes otherwise No.

#### Pseudocode

isPathBFS(Graph G, node source, node end):
Queue Q
Q.enqueue( source ) //add the source node to the queue first

tag source as visited

while (Q is not empty):
v  =  Q.dequeue( )

for all neighbours w of v in Graph G
if w is end :
return true

if w is not visited :
Q.enqueue( w )
tag w as visited
return false


#### Example

In the Graph G in the image below, we find whether there exists a path between node 1 and node 6 using BFS. To find if there exists such a path, we will use BFS with node 1 as our source and check if node 6 exists in our traversal.

## Solution using BFS

• C++

### C++

// C++ program to check if there exists a path between two vertices of a graph.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

//function definition
bool isPathBFS(vector <vector<int>>& graph, int nodes, int source, int end){
//BFS implementation

bool visited[nodes];
for(int i = 0;i<nodes;++i){
visited[i] = false;
}

queue <int> traversal;
traversal.push(source);
visited[source-1] = true;

while(!traversal.empty()){
//dequeue the front element
source = traversal.front();
traversal.pop();

for(int i = 0;i < (int)graph[source-1].size();++i){
if(graph[source-1][i]==end)
return true;

if(visited[graph[source-1][i]-1]==false){

traversal.push(graph[source-1][i]);
visited[graph[source-1][i]-1] = true;
}
}
}

return false;
}

int main(){
//input
int nodes;
cout << "No. of nodes in graph = ";
cin >> nodes;

int edges;
cout << "No. of edges in graph = ";
cin >> edges;

vector <vector<int>> graph;
graph.resize(nodes);

cout << "Edges:\n";
int source,end;

while(edges--){
cin >> source>>end;

//As we are using 1-indexing for nodes
if(source > nodes || end > nodes){
cout << "Invalid nodes.";
return 1;
}

graph[source-1].push_back(end);
}

int query;
cout << "No. of queries = ";
cin >> query;

while(query--){
cin >> source>>end;

//output
if(source > nodes || end > nodes){
cout << "Invalid nodes.\n";
continue;
}

if(isPathBFS(graph,nodes,source,end)){
cout << "Yes"<<"\n";
}else cout << "No"<<"\n";
}
return 0;
}


### Time Complexity ( for adjancency list representation )

• Worst case time complexity: O(V+E)
• Best case time complexity: Ω(1)
• Space complexity: O(V+E)
where V is the number of vertices and E is the number of edges.

## 2. Using DFS

Here we will use Depth First Search in the solution. Take the first vertex as the source in DFS and if the second vertex is found in traversal print Yes otherwise No.

#### Pseudocode

isPathDFS(Graph G, node source, node end):
Stack S
S.push( source )

tag source as visited

while(S is not empty):
v = S.top()
S.pop()

for all neighbours of w of v in Graph G:
if w is end :
return true

if w is not visited :
S.push( w )
tag w as visited

return false


#### Example

In the Graph G in the image below, we find whether there exists a path between node 1 and node 6 using DFS. To find if there exists such a path, we will use DFS with node 1 as our source and check if node 6 exists in our traversal.

## Solution using DFS

• C++

### C++

// C++ program to check if there exists a path between two vertices of a graph.
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

//function definition
bool isPathDFS(vector <vector<int>>& graph, int nodes, int source, int end){
//DFS implementation

bool visited[nodes];
for(int i = 0;i<nodes;++i){
visited[i] = false;
}

stack <int> traversal;
traversal.push(source);
visited[source-1] = true;

while(!traversal.empty()){
//Pop the front element
source = traversal.top();
traversal.pop();

for(int i = 0;i < (int)graph[source-1].size();++i){
if(graph[source-1][i]==end)
return true;

if(visited[graph[source-1][i]-1]==false){

traversal.push(graph[source-1][i]);
visited[graph[source-1][i]-1] = true;
}
}
}

return false;
}

int main(){
//input
int nodes;
cout << "No. of nodes in graph = ";
cin >> nodes;

int edges;
cout << "No. of edges in graph = ";
cin >> edges;

vector <vector<int>> graph;
graph.resize(nodes);

cout << "Edges:\n";
int source,end;

while(edges--){
cin >> source>>end;

//As we are using 1-indexing for nodes
if(source > nodes || end > nodes){
cout << "Invalid nodes.";
return 1;
}

graph[source-1].push_back(end);
}

int query;
cout << "No. of queries = ";
cin >> query;

while(query--){
cin >> source>>end;

//output
if(source > nodes || end > nodes){
cout << "Invalid nodes.\n";
continue;
}

if(isPathDFS(graph,nodes,source,end)){
cout << "Yes"<<"\n";
}else cout << "No"<<"\n";
}
return 0;
}


### Time Complexity ( for adjancency list representation )

• Worst case time complexity: O(V+E)
• Best case time complexity: Ω(1)
• Space complexity: O(V+E)
where V is the number of vertices and E is the number of edges.

#### Tradeoffs between BFS and DFS approach

BFS can be useful to find the minimum number of edges between two nodes while DFS may not always give us the path with minimum number of edges as it may traverse one adjacent node very deeply before going to other neighbouring nodes (as BFS works level by level while DFS works depth wise).
For other differences between BFS vs DFS refer to the article : BFS vs DFS

Exercise: Modify the above algorithm to find any path between two vertices if it exists.

Also feel free to share your approach in the discussion thread below. Happy Coding :)