Aayush's Blog
Find If Path Exists in Graph Leetcode Solution

Find If Path Exists in Graph Leetcode Solution

Aayush Shah's photo
Aayush Shah
·

4 min read

Table of contents

Hello and welcome back to the daily session of crying while grinding Leetcode! Today we tackle a topic that makes most developers wish they'd chosen a different career: Graphs!

Don't worry though, this is one of the simplest graph problems you're going to encounter (actually, this is so easy that you'll probably never encounter it, but you get my point).

Let's begin!

Understanding The Problem

As always, go through the problem description at least twice.

There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.

You want to determine if there is a valid path that exists from vertex source to vertex destination.

Given edges and the integers n, source, and destination, return true if there is a valid path from source to destination, or false otherwise.

The problem is pretty simple, we need to check if a path exists between two given nodes of a graph. Don't get confused by terms like "bi-directional graph". It just means an undirected graph, that is, if there is an edge from node A to node B, the same edge also works as a path from B to A.

Graph problems like this require us to perform a traversal. Let's see how that works.

Intuition

There are two kinds of traversals we can perform on a graph: Depth First Search and Breadth First Search.

Let's see in brief how each of these works.

Depth First Search (DFS) is an algorithm for graph traversal in which we travel as far as possible from the root node before backtracking. The basic idea is to start from a random node, mark the node as "visited", and move on to one of its adjacent unvisited neighbors and continue this process until there are no unvisited neighbours left. Once this stage is reached, we backtrack and check for other unvisited nodes and traverse them.

Breadth First Search (BFS) is an algorithm for traversing a graph. It starts at a given vertex and explores all the vertices that are reachable from it, before moving on to the next vertex. The algorithm traverses the graph level by level, visiting all the vertices at each level before moving on to the next.

If you'd like to read up on these traversals in more detail, check out the links at the end of the article.

We will be using BFS to solve this problem Take a look at the algorithm for BFS below:

  1. Initialize a queue Q and a set S of visited vertices.

  2. Add the starting vertex v to Q and S.

  3. While Q is not empty:

  4. Remove the first vertex v from Q.

  5. For each neighbor w of v:

    1. If w is not in S, add it to S and Q.

  6. Return S, the set of visited vertices.

The algorithm terminates when the queue is empty, which means that all reachable vertices have been visited.

We need to tweak this algorithm a bit to find the solution to our problem. We start from our source node and perform a BFS traversal. Now, inside the loop for BFS, we just check if the current node we're on is the destination . If so, we return true. If the loop ends, and we haven't found destination on any path from source , we return false.

Let's see what the code for this looks like.

Coding The Solution

Here's the full solution to this problem.

class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int start, int end) {
        set<int> graph[n];

        //construct an adjacency list
        for(vector<int> edge:edges){
            graph[edge[0]].insert(edge[1]);
            graph[edge[1]].insert(edge[0]);
        }
        //if the destination is present in the source's adjacency list, return true, no need to perform BFS.
        //this suggests that there is a direct path from the source to the destination.
        if(graph[start].find(end) != graph[start].end()){
            return true;
        }

        //perform BFS
        queue<int> q;
        q.push(start);

        vector<bool> visited(n);
        int current;

        while(!q.empty()){
            current = q.front();
            q.pop();
            if(current == end) return true;
            for(int i : graph[current]){
                if(!visited[i]){
                    visited[i] = true;
                    q.push(i);
                }
            }
        }
        return false;
    }
};

We use a HashSet to store the adjacency list of the graph. If either of these terms confuses you, check out the links at the end of the article for more details.

That's it for today's problem. Please leave any suggestions you might have in the comments and subscribe to my newsletter for daily posts!

Cheers!

Additional Resources

leetcodeleetcode-solutionGraphBFSleetcodedaily