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

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

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

Consider the following graph:

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.

Step 1

Step 2

Step 3

Step 4

Step 5

As node 6 is in our traversal ( BFS ), therefore we can draw a path from node 1 to node 6. ( 1->2->4->6 )

Solution using BFS

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.

Step 1

Step 2

Step 3

Step 4

As node 6 is in our traversal ( DFS ), therefore we can draw a path from node 1 to node 6. ( 1->2->4->6 )

Solution using DFS

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 :)