C++ Program to Find Whether a Path Exists Between 2 Given Nodes

C++ Program to Find Whether a Path Exists Between 2 Given Nodes Article has many meanings. We are going to know this topic clearly through this article. We hope you like this article.

C++ Program to Find Whether a Path Exists Between 2 Given Nodes

C++ Program to Find Whether a Path Exists Between 2 Given Nodes

#include <iostream>
#include <list>
 
using namespace std;
 
// This class represents a directed graph using adjacency list representation
class Graph
{
        int V; // No. of vertices
        list<int> *adj; // Pointer to an array containing adjacency lists
    public:
        Graph(int V); // Constructor
        void addEdge(int v, int w); // function to add an edge to graph
        bool isReachable(int s, int d); // returns true if there is a path from s to d
};
 
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int> [V];
}
 
void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v’s list.
}
 
// A BFS based function to check whether d is reachable from s.
bool Graph::isReachable(int s, int d)
{
    // Base case
    if (s == d)
        return true;
 
    // Mark all the vertices as not visited
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;
 
    // Create a queue for BFS
    list<int> queue;
 
    // Mark the current node as visited and enqueue it
    visited[s] = true;
    queue.push_back(s);
 
    // it will be used to get all adjacent vertices of a vertex
    list<int>::iterator i;
 
    while (!queue.empty())
    {
        // Dequeue a vertex from queue and print it
        s = queue.front();
        queue.pop_front();
 
        // Get all adjacent vertices of the dequeued vertex s
        // If a adjacent has not been visited, then mark it visited
        // and enqueue it
        for (i = adj[s].begin(); i != adj[s].end(); ++i)
        {
            // If this adjacent node is the destination node, then return true
            if (*i == d)
                return true;
 
            // Else, continue to do BFS
            if (!visited[*i])
            {
                visited[*i] = true;
                queue.push_back(*i);
            }
        }
    }
 
    return false;
}
 
// Driver program to test methods of graph class
int main()
{
    // Create a graph given in the above diagram
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);
 
    cout << "Enter the source and destination vertices: (0-3)";
    int u, v;
    cin >> u >> v;
    if (g.isReachable(u, v))
        cout << "nThere is a path from " << u << " to " << v;
    else
        cout << "nThere is no path from " << u << " to " << v;
 
    int temp;
    temp = u;
    u = v;
    v = temp;
    if (g.isReachable(u, v))
        cout << "nThere is a path from " << u << " to " << v;
    else
        cout << "nThere is no path from " << u << " to " << v;
 
    return 0;
}

Read Also:C++ Program to Check if a Given Binary Tree is an AVL Tree or Not

Final Words

C++ Program to Find Whether a Path Exists Between 2 Given Nodes We got to know our topic very clearly. And if you have any doubts about this article you can let us know your doubts via comment.

Hi, I'm Ranjith a full-time Blogger, YouTuber, Affiliate Marketer, & founder of Coding Deekshi. Here, I post about programming to help developers.

Share on:

Leave a Comment