Solution: Check If a Path Exists between Two Vertices

Statement

Given a 2D list, edges, representing a bidirectional graph of n nodes, where each vertex is labeled from $0$ to $n-1$. Each edge in the graph is represented as a pair, $[x_i, y_i]$, showing a bidirectional edge between $x_i$ and $y_i$. Each pair of vertices is connected by at most one edge, and no vertex is connected to itself.

Determine whether a valid path exists from the source vertex to the destination vertex. If it exists, return TRUE, otherwise return FALSE.

Constraints:

• $1\leq$ n $\leq 10^2$

• $0\leq$ edges.length $\leq n(n-1)/2$

• edges[i].length $= 2$

• $0 \leq x_i,y_i \leq n-1$

• $x_i\ne y_i$

• $0\leq$ source, destination $\leq n - 1$

• 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 list where, for each vertex, we list out all the neighbors it is connected to.

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 list 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: