Given a directed graph and two vertices (say source and destination vertex), determine if the destination vertex is reachable from the source vertex or not. If the path exists from the source vertex to the destination vertex, print it.
For example, there exists two paths {0-3-4-6-7} and {0-3-5-6-7} from vertex 0 to vertex 7 in the following graph. Whereas there is no path from vertex 7 to any other vertex.
We can use Breadth First Search (BFS) algorithm to efficiently check the connectivity between any two vertices in the graph. The idea is to start the BFS routine from the source vertex and check if the destination vertex is reached during the traversal. If the destination vertex is not encountered at any point, we can say that it is not reachable from the source vertex.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 |
#include <iostream> #include <queue> #include <vector> using namespace std; // Data structure to store graph edges struct Edge { int src, dest; }; // Class to represent a graph object class Graph { public: // construct a vector of vectors to represent adjacency list in C++ vector<vector<int>> adjList; // Graph Constructor Graph(const vector<Edge> &edges, int N) { // resize the vector to N elements each of type vector<int> adjList.resize(N); // add edges to the directed graph for (auto &edge: edges) { adjList[edge.src].push_back(edge.dest); } } }; // Function to perform BFS traversal from the source vertex in the graph to // determine if the destination vertex is reachable from the source or not bool isConnected(const Graph &graph, int src, int dest, vector<bool> &discovered) { // create a queue used to do BFS queue<int> q; // mark source vertex as discovered discovered[src] = true; // push source vertex into the queue q.push(src); // run till queue is not empty while (!q.empty()) { // pop front node from queue and print it int v = q.front(); q.pop(); // if destination vertex is found if (v == dest) { return true; } // do for every edge (v -> u) for (int u : graph.adjList[v]) { if (!discovered[u]) { // mark it discovered and push it into queue discovered[u] = true; q.push(u); } } } return false; } int main() { // vector of graph edges as per above diagram vector<Edge> edges = { {0, 3}, {1, 0}, {1, 2}, {1, 4}, {2, 7}, {3, 4}, {3, 5}, {4, 3}, {4, 6}, {5, 6}, {6, 7} }; // Number of nodes in the graph (labelled from 0 to N-1) int N = 8; // create a graph from given edges Graph graph(edges, N); // stores vertex is discovered or not vector<bool> discovered(N); // source and destination vertex int src = 0, dest = 7; // perform BFS traversal from the source vertex to check the connectivity if (isConnected(graph, src, dest, discovered)) { cout << "Path exists from vertex " << src << " to vertex " << dest; } else { cout << "No path exists between vertices " << src << " and " << dest; } return 0; } |
Output:
Path exists from vertex 0 to vertex 7
How to print the complete path?
The idea is to store the complete path between the source and destination vertex in a vector or an array using recursion. This can be easily achieved if Depth First Search (DFS) is used to determine path between the vertices. This is demonstrated below in C++:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
#include <iostream> #include <vector> using namespace std; // data structure to store graph edges struct Edge { int src, dest; }; // class to represent a graph object class Graph { public: // construct a vector of vectors to represent adjacency list in C++ vector<vector<int>> adjList; // Graph Constructor Graph(const vector<Edge> &edges, int N) { // resize the vector to N elements of type vector<int> adjList.resize(N); // add edges to the directed graph for (auto &edge: edges) { adjList[edge.src].push_back(edge.dest); } } }; // Function to perform DFS traversal in a directed graph to find the // complete path between source and destination vertices bool isConnected(const Graph &graph, int src, int dest, vector<bool> &discovered, vector<int> &path) { // mark current node as discovered discovered[src] = true; // include current node in the path path.push_back(src); // if destination vertex is found if (src == dest) { return true; } // do for every edge (src -> i) for (int i: graph.adjList[src]) { // u is not discovered if (!discovered[i]) { // return true if destination is found if (isConnected(graph, i, dest, discovered, path)) return true; } } // backtrack: remove current node from the path path.pop_back(); // return false if destination vertex is not reachable from src return false; } // Utility function to print a vector void printPath(const vector<int> &path) { for (int i: path) cout << i << ' '; cout << endl; } int main() { // vector of graph edges as per above diagram vector<Edge> edges = { {0, 3}, {1, 0}, {1, 2}, {1, 4}, {2, 7}, {3, 4}, {3, 5}, {4, 3}, {4, 6}, {5, 6}, {6, 7} }; // Number of nodes in the graph (labelled from 0 to N-1) int N = 8; // create a graph from given edges Graph graph(edges, N); // stores vertex is discovered or not vector<bool> discovered(N); // source and destination vertex int src = 0, dest = 7; // vector to store the complete path between source and destination vector<int> path; // perform DFS traversal from the source vertex to check the connectivity // and store path from the source vertex to the destination vertex if (isConnected(graph, src, dest, discovered, path)) { cout << "Path exists from vertex " << src << " to vertex " << dest; cout << "\nThe complete path is: "; printPath(path); } else { cout << "No path exists between vertices " << src << " and " << dest; } return 0; } |
Output:
Path exists from vertex 0 to vertex 7
The complete path is: 0 3 4 6 7
The time complexity of above solutions is O(n + m) where n is number of vertices and m is number of edges in the graph.
Exercise: Extend the solution to print all paths between given vertices (solution link)
Thanks for reading.
Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply