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.
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; }}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.