C++ Programming Code Examples C++ > Mathematics Code Examples Program to Find Path Between Two Nodes in a Graph Program to Find Path Between Two Nodes in a Graph This is a C++ Program to check and find if the path between two nodes exists. By running DFS on given graph we can find out whether path exists between two 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; }