Solution: Check If a Path Exists between Two Vertices
Let’s solve the Check If a Path Exists between Two Vertices problem.
We'll cover the following
Statement
Given a 2D array, edges
, representing a bidirectional graph of n
nodes, where each vertex is labeled from
Determine whether a valid path exists from the source
vertex to the destination
vertex. If it exists, return TRUE, otherwise return FALSE.
Constraints:
n
edges.length
edges[i].length
source
,destination
There are no duplicate edges
There are no self-edges
Solution
In this solution, we use the breadth-first search (BFS) approach to determine if a path exists from the source vertex to the destination vertex in a given graph. To do this, we represent the graph using an adjacency matrix where adjacency[i][j]
is 1
if there is an edge between vertex i
and vertex j
, and 0
otherwise.
We use a queue to store the nodes to explore, and a set to store the nodes that have been visited. We start by pushing the source node to the queue, and while there are still vertices to explore in the queue, we will repeat the following steps:
Dequeue a vertex from the queue.
Check if this vertex is the destination we’re looking for. If it is, there’s a path from the source to the destination, and we return TRUE.
Otherwise, we visit all of its neighboring vertices using the adjacency matrix of the graph:
If any of these neighbors haven’t been visited yet, add them to the queue to explore later, mark them as visited so we don’t explore them again, and continue the breadth-first search.
If we’ve explored all possible paths from the source vertex and still haven’t found the destination, then there’s no path from the source to the destination, and we return FALSE.
Let’s look at the illustration below to better understand the solution:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.