Challenge: Check if a Path Exists Between Two Vertices
Given a graph and two vertices, can you write a code to check if a path exists between the two vertices?
We'll cover the following
Problem Statement #
You have to implement the bool checkPath(Graph g, int source, int destination)
function. It takes a source, and a destination and tells us whether or not a path exists between the two (from the source to the destination).
If there is no repeated sequence of edges and vertices between the source and the destination vertex then the path exists between these two vertices.
Note: Path will always exist if the source and destination nodes are the same.
Input #
A graph, a source value and a destination value.
Output #
Returns true
if a path exists from the source to the destination.
Sample Input #
graph = {
0 -> 2
0 -> 5
2 -> 3
2 -> 4
5 -> 3
5 -> 6
3 -> 6
6 -> 7
6 -> 8
6 -> 4
7 -> 8
}
source = 0
destination = 7
Sample Output #
true
Level up your interview prep. Join Educative to access 70+ hands-on prep courses.