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 list, edges, representing a bidirectional graph of n nodes, where each vertex is labeled from 00 to n−1n-1. Each edge in the graph is represented as a pair, [xi,yi][x_i, y_i], showing a bidirectional edge between xix_i and yiy_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≤1\leq n ≤102\leq 10^2

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

  • edges[i].length =2 = 2

  • 0≤xi,yi≤n−10 \leq x_i,y_i \leq n-1

  • xi≠yi x_i\ne y_i

  • 0≤0\leq source, destination ≤n−1\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 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 70+ hands-on prep courses.