if two vertices of the graph has a path …then how to print the path between them(any possible path)?
You can do this by one of the two methods
- DFS (Depth First Search)
- BFS (Breadth First Search)
For any possible path, DFS would be enough. But, BFS gives you the shortest path between the two vertices. In either of these algorithms, you need to just make a minor addition to the code to make it suitable to help you print the path between two vertices. You need to maintain an array prev[n] (n=number of vertices in the graph), which will record the vertex that was previously visited to reach vertex i (1<=i<=n). The purpose of this array is that, every time a new vertex j is visited, prev[j] is updated to i (where i is the vertex visited before j).
After the traversal is done, you can write a simple while loop to print the path. Here is a pseudocode to print the path from vertex i to j :
//after traversal is done
x = j
while (x!=i)
print x->
x = prev[x]
print x
If you need to find the path between only two vertices for your problem, then you could optimize the code by calling DFS(x) or BFS(x), where x is your source vertex and stop the execution of the traversal once your destination, say y, is reached.
A detailed explanation about how to find the shortest path between two vertices using BFS is given here, do check it out: Shortest Path using BFS
2 Likes
DFS is more appropriate for printing the path. Even without maintaining the previous array, you can simply display the vertex at which the DFS call returns.