#1971
Find if Path Exists in Graph
Easy Adjacency list + BFS
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
An undirected graph has n vertices and an edge list. Decide whether a path exists from source to destination.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: can you get from source to destination?
Why this works: build the adjacency list and BFS from the source; if you reach the destination, a path exists.
Example: edges [0-1, 1-2, 2-0], 0 → 2
visit 0 → neighbours 1, 2 → found 2 → true✦Hints open one at a time
Build an adjacency list from the edge list.
BFS or DFS from source with a visited array.
↗Approach
Adjacency list of size n, then BFS from source; return true when destination is reached. (Union-Find also works.)
</>Solution (Java)
import java.util.*;
class Solution {
public boolean validPath(int n, int[][] edges, int source, int destination) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]); // undirected: both ways
}
boolean[] seen = new boolean[n];
Queue<Integer> q = new ArrayDeque<>();
q.offer(source);
seen[source] = true;
while (!q.isEmpty()) {
int u = q.poll();
if (u == destination) return true;
for (int v : adj.get(u)) {
if (!seen[v]) {
seen[v] = true;
q.offer(v);
}
}
}
return false;
}
}!Common mistake
Adding each undirected edge in only one direction.
Complexity
- Time: O(V + E).
- Space: O(V + E).
Topic: Graphs
🎬 Episodes 74–85: video coming soon