# Find if Path Exists in Graph
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-if-path-exists-in-graph)
Canonical: https://scaleengineer.com/dsa/problems/find-if-path-exists-in-graph
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Graph
---
## Problem
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_ _._

**Example 1:**

![](https://assets.glich.co/dsa/find-if-path-exists-in-graph/image0.png) 

**Input:** n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
**Output:** true
**Explanation:** There are two paths from vertex 0 to vertex 2:
- 0 → 1 → 2
- 0 → 2

**Example 2:**

![](https://assets.glich.co/dsa/find-if-path-exists-in-graph/image1.png) 

**Input:** n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
**Output:** false
**Explanation:** There is no path from vertex 0 to vertex 5.

**Constraints:**

* `1 <= n <= 2 * 105`
* `0 <= edges.length <= 2 * 105`
* `edges[i].length == 2`
* `0 <= ui, vi <= n - 1`
* `ui != vi`
* `0 <= source, destination <= n - 1`
* There are no duplicate edges.
* There are no self edges.

# Approaches
## Depth-First Search (DFS)
This approach treats the problem as a graph traversal. We start at the `source` vertex and explore as far as possible along each branch before backtracking. This is the essence of Depth-First Search (DFS). We use a `visited` set or array to keep track of visited vertices to avoid infinite loops in graphs with cycles. If the `destination` vertex is encountered during the traversal, we know a path exists.
**Time:** O(V + E), where V is the number of vertices (`n`) and E is the number of edges. Building the adjacency list takes O(V + E) time. The DFS traversal itself visits each vertex and edge at most once. · **Space:** O(V + E), where V is the number of vertices and E is the number of edges. This is for storing the adjacency list (O(V+E)), the `visited` array (O(V)), and the stack (O(V) in the worst case).
**Pros:** Conceptually straightforward and relatively easy to implement.; Guaranteed to find a path if one exists.
**Cons:** For very large graphs, a recursive implementation might lead to a stack overflow error if the path is very long. An iterative approach with an explicit stack is safer.; Requires O(V + E) space for the adjacency list, which can be significant.
### Explanation
To implement DFS, we first need a suitable representation of the graph. An adjacency list is a common and efficient choice. We can build it by iterating through the `edges` array. For each edge `[u, v]`, we add `v` to the list of `u`'s neighbors and `u` to the list of `v`'s neighbors.

Once the graph is built, we start the traversal from the `source` node. We need a `visited` array to keep track of the nodes we have already processed to prevent getting stuck in cycles. The traversal can be implemented either recursively or iteratively using a stack.

In the iterative version, we push the `source` onto a stack. Then, in a loop, we pop a node, check if it's the `destination`, and if not, we push all its unvisited neighbors onto the stack. If the stack becomes empty and we haven't found the `destination`, no path exists.

```java
class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        if (source == destination) {
            return true;
        }

        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        boolean[] visited = new boolean[n];
        Stack<Integer> stack = new Stack<>();

        stack.push(source);
        visited[source] = true;

        while (!stack.isEmpty()) {
            int u = stack.pop();

            if (u == destination) {
                return true;
            }

            for (int v : adj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    stack.push(v);
                }
            }
        }

        return false;
    }
}
```
### Algorithm
- Build an adjacency list representation of the graph from the `edges` array. Since the graph is bi-directional, for an edge `[u, v]`, add `v` to `u`'s list and `u` to `v`'s list.
- Initialize a `visited` boolean array of size `n` to all `false`.
- Create a stack (for an iterative approach) and push the `source` vertex onto it.
- Mark the `source` vertex as visited.
- While the stack is not empty:
  - Pop a vertex `u` from the stack.
  - If `u` is the `destination`, a path has been found, so return `true`.
  - For each neighbor `v` of `u`:
    - If `v` has not been visited, mark it as visited and push it onto the stack.
- If the loop completes without finding the destination, it means no path exists. Return `false`.

## Breadth-First Search (BFS)
Breadth-First Search (BFS) is another graph traversal algorithm that can solve this problem. Instead of going deep into one branch, BFS explores the graph layer by layer from the `source` vertex. It uses a queue to manage the order of vertices to visit. If a path exists, BFS will find it. A key property of BFS is that it finds the shortest path in terms of the number of edges in an unweighted graph, although this is not a requirement for the current problem.
**Time:** O(V + E). Building the adjacency list is O(V + E). The BFS traversal visits each vertex and edge at most once. · **Space:** O(V + E). O(V + E) for the adjacency list, O(V) for the `visited` array, and O(V) for the queue in the worst case (e.g., a star graph).
**Pros:** Guaranteed to find a path if one exists.; Avoids the potential for stack overflow that can occur with deep recursion in DFS.; Finds the shortest path in terms of edge count.
**Cons:** Like DFS, it requires O(V + E) space for the adjacency list, which can be memory-intensive for large graphs.
### Explanation
The setup for BFS is similar to DFS. We first build an adjacency list to represent the graph. We also use a `visited` array to avoid reprocessing nodes and getting into infinite loops.

The main difference is the data structure used for traversal: BFS uses a queue (First-In, First-Out). The algorithm starts by adding the `source` node to the queue and marking it as visited. Then, it enters a loop that continues as long as the queue is not empty. In each iteration, it dequeues a vertex `u`. If `u` is the `destination`, a path is found. Otherwise, it iterates through all of `u`'s neighbors. For any neighbor that has not been visited, it marks it as visited and enqueues it. If the loop finishes, it means all reachable nodes from the `source` have been visited, and since the `destination` was not among them, no path exists.

```java
class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        if (source == destination) {
            return true;
        }

        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();

        queue.offer(source);
        visited[source] = true;

        while (!queue.isEmpty()) {
            int u = queue.poll();

            if (u == destination) {
                return true;
            }

            for (int v : adj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    queue.offer(v);
                }
            }
        }

        return false;
    }
}
```
### Algorithm
- Build an adjacency list representation of the graph from the `edges` array.
- Initialize a `visited` boolean array of size `n` to all `false`.
- Create a queue and add the `source` vertex to it.
- Mark the `source` vertex as visited.
- While the queue is not empty:
  - Dequeue a vertex `u`.
  - If `u` is the `destination`, return `true`.
  - For each neighbor `v` of `u`:
    - If `v` has not been visited, mark it as visited and enqueue it.
- If the queue becomes empty and the destination has not been reached, return `false`.

## Union-Find (Disjoint Set Union)
The Union-Find data structure (also known as Disjoint Set Union or DSU) is highly optimized for problems involving connectivity and partitioning a set of elements into disjoint subsets. The core idea is to determine if the `source` and `destination` vertices belong to the same connected component of the graph. We process all the edges, and for each edge `(u, v)`, we `union` the sets that `u` and `v` belong to. After all edges are processed, if `source` and `destination` are in the same set, a path exists between them.
**Time:** O(V + E * α(V)), where V is `n`, E is `edges.length`, and α is the very slow-growing Inverse Ackermann function. For all practical purposes, α(V) is a small constant (≤ 5), making the complexity nearly linear, i.e., O(V + E). · **Space:** O(V), where V is the number of vertices (`n`). We need two arrays of size `n` for the `parent` and `rank` information.
**Pros:** Extremely fast, with nearly constant time operations on average.; More space-efficient than traversal methods as it doesn't require building an adjacency list (O(V) vs O(V+E)).; Perfectly suited for connectivity problems.
**Cons:** The implementation is more complex than a standard graph traversal like BFS or DFS.; This method only determines connectivity; it cannot be used to reconstruct the actual path between the source and destination.
### Explanation
A Union-Find data structure maintains a collection of disjoint sets and provides two primary operations: `find` and `union`.

- `find(i)`: Returns the representative (or root) of the set containing element `i`.
- `union(i, j)`: Merges the two sets containing elements `i` and `j`.

We start by creating `n` sets, one for each vertex. Then, we iterate through the `edges` array. For each edge `[u, v]`, we merge the components of `u` and `v` using the `union` operation. This effectively builds up the connected components of the graph. After processing all edges, we simply need to check if `source` and `destination` have the same representative using the `find` operation. If `find(source)` equals `find(destination)`, they are in the same connected component, and thus a path exists.

To achieve high efficiency, two optimizations are crucial: **path compression** (in the `find` operation) and **union by rank/size** (in the `union` operation). These optimizations reduce the time complexity of the operations to nearly constant on an amortized basis.

```java
class Solution {
    private class UnionFind {
        private int[] parent;
        private int[] rank;

        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = 1;
            }
        }

        public int find(int i) {
            if (parent[i] == i) {
                return i;
            }
            // Path compression
            return parent[i] = find(parent[i]);
        }

        public void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) {
                // Union by rank
                if (rank[rootI] > rank[rootJ]) {
                    parent[rootJ] = rootI;
                } else if (rank[rootI] < rank[rootJ]) {
                    parent[rootI] = rootJ;
                } else {
                    parent[rootJ] = rootI;
                    rank[rootI]++;
                }
            }
        }
    }

    public boolean validPath(int n, int[][] edges, int source, int destination) {
        if (source == destination) return true;
        
        UnionFind uf = new UnionFind(n);
        for (int[] edge : edges) {
            uf.union(edge[0], edge[1]);
        }

        return uf.find(source) == uf.find(destination);
    }
}
```
### Algorithm
- Initialize a Union-Find data structure with `n` elements, where each vertex is in its own set. This typically involves a `parent` array where `parent[i] = i`.
- Implement the `find` operation with path compression to quickly find the representative (root) of a set.
- Implement the `union` operation, preferably with an optimization like union by rank or size, to merge the sets of two elements.
- Iterate through all the `edges` of the graph. For each edge `[u, v]`, call `union(u, v)` to merge the sets containing `u` and `v`.
- After processing all edges, check if `source` and `destination` are in the same set by comparing the results of `find(source)` and `find(destination)`.
- If they are the same, a path exists, so return `true`. Otherwise, return `false`.

# Solutions
### Java

```java
class Solution {
private
  boolean[] vis;
private
  List<Integer>[] g;
public
  boolean validPath(int n, int[][] edges, int source, int destination) {
    vis = new boolean[n];
    g = new List[n];
    Arrays.setAll(g, k->new ArrayList<>());
    for (var e : edges) {
      int a = e[0], b = e[1];
      g[a].add(b);
      g[b].add(a);
    }
    return dfs(source, destination);
  }
private
  boolean dfs(int source, int destination) {
    if (source == destination) {
      return true;
    }
    vis[source] = true;
    for (int nxt : g[source]) {
      if (!vis[nxt] && dfs(nxt, destination)) {
        return true;
      }
    }
    return false;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool validPath(int n, vector<vector<int>> &edges, int source,
                 int destination) {
    vector<bool> vis(n);
    vector<vector<int>> g(n);
    for (auto &e : edges) {
      int a = e[0], b = e[1];
      g[a].emplace_back(b);
      g[b].emplace_back(a);
    }
    function<bool(int)> dfs = [&](int i) -> bool {
      if (i == destination)
        return true;
      vis[i] = true;
      for (int &j : g[i]) {
        if (!vis[j] && dfs(j)) {
          return true;
        }
      }
      return false;
    };
    return dfs(source);
  }
};

```

### Python

```python
class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool: def dfs(i): if i == destination: return True vis . add(i) for j in g[i]: if j not in vis and dfs(j): return True return False g = defaultdict(list) for a, b in edges: g[a]. append(b) g[b]. append(a) vis = set() return dfs(source)

```