Find if Path Exists in Graph
EasyPrompt
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:
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 → 2Example 2:
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 * 1050 <= edges.length <= 2 * 105edges[i].length == 20 <= ui, vi <= n - 1ui != vi0 <= source, destination <= n - 1- There are no duplicate edges.
- There are no self edges.
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Build an adjacency list representation of the graph from the
edgesarray. Since the graph is bi-directional, for an edge[u, v], addvtou's list andutov's list. - Initialize a
visitedboolean array of sizento allfalse. - Create a stack (for an iterative approach) and push the
sourcevertex onto it. - Mark the
sourcevertex as visited. - While the stack is not empty:
- Pop a vertex
ufrom the stack. - If
uis thedestination, a path has been found, so returntrue. - For each neighbor
vofu:- If
vhas not been visited, mark it as visited and push it onto the stack.
- If
- Pop a vertex
- If the loop completes without finding the destination, it means no path exists. Return
false.
Walkthrough
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.
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; }}Complexity
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).
Trade-offs
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.
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.
Algorithm
- Build an adjacency list representation of the graph from the
edgesarray. - Initialize a
visitedboolean array of sizento allfalse. - Create a queue and add the
sourcevertex to it. - Mark the
sourcevertex as visited. - While the queue is not empty:
- Dequeue a vertex
u. - If
uis thedestination, returntrue. - For each neighbor
vofu:- If
vhas not been visited, mark it as visited and enqueue it.
- If
- Dequeue a vertex
- If the queue becomes empty and the destination has not been reached, return
false.
Walkthrough
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.
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; }}Complexity
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).
Trade-offs
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.
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.
Algorithm
- Initialize a Union-Find data structure with
nelements, where each vertex is in its own set. This typically involves aparentarray whereparent[i] = i. - Implement the
findoperation with path compression to quickly find the representative (root) of a set. - Implement the
unionoperation, preferably with an optimization like union by rank or size, to merge the sets of two elements. - Iterate through all the
edgesof the graph. For each edge[u, v], callunion(u, v)to merge the sets containinguandv. - After processing all edges, check if
sourceanddestinationare in the same set by comparing the results offind(source)andfind(destination). - If they are the same, a path exists, so return
true. Otherwise, returnfalse.
Walkthrough
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 elementi.union(i, j): Merges the two sets containing elementsiandj.
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.
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); }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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); }};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)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.