Find a available path from a given source to a given destination in a given graph.

Intuition

Use DFS to find all reachable nodes and check if the destination lie within those nodes.

Approach

We first transform the adjacency matrix to adjacency list to make BFS easier, then we use a queue to maintain the reachable nodes, to prevent from cycling, we also use a set to keep track of visited nodes. If at any point, we reach the destination, we return directly.

Complexity

Time complexity: iterate all nodes at most once $$O(n)$$
Space complexity: stores nodes of the same distance in the graph to the source $$O(n)$$

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        unordered_map<int, vector<int>> adjs;
        for (const auto &edge: edges) {
            adjs[edge[0]].push_back(edge[1]);
            adjs[edge[1]].push_back(edge[0]);
        }

        unordered_set<int> visited;
        queue<int> q;
        q.push(source);
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            if (node == destination)    return true;
            for (int next_node: adjs[node]) {
                if (visited.find(next_node) != visited.end())   
                    continue;
                q.push(next_node);
                visited.insert(next_node);
            }
        }
        return false;
    }
};

1971. Find if Path Exists in Graph

Path from source to destination in a given graph

Intuition

Approach

Complexity

Code