# 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

``````#include <iostream>
#include <list>

using namespace std;

// This class represents a directed graph using adjacency list representation
class Graph
{
int V; // No. of vertices
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;
}

{
}

// 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
{
// 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);

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;
}``````

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: