Find if Path Exists in Graph
Find if Path Exists in Graph: given an undirected graph as edge pairs and a source and destination, return whether a path exists between them.
- 1 <= n <= 2 * 10⁵
- 0 <= edges.length <= 2 * 10⁵
- 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.
Intuition
Find if path exists in graph asks whether a route connects two vertices in an undirected graph. There are no weights and no requirement that the path be short — only whether one exists at all. That framing matters, because it rules out the machinery these problems often attract: - Dijkstra and BFS-for-shortest-path solve a harder question than this one; plain reachability needs no distances, no priority queue, and no level tracking. Any traversal works. DFS, BFS, or Union-Find all answer it correctly, and the choice comes down to the shape of the input rather than correctness. Build an adjacency list first, adding both directions for each edge since the graph is undirected. Omitting the reverse entry silently makes some reachable vertices unreachable. Then traverse from the source, marking vertices visited, and report whether the destination is reached. The visited set is what prevents infinite loops — an undirected edge is a two-cycle, so a traversal without it revisits the previous vertex forever. On a large graph, recursive DFS risks a stack overflow, since the recursion depth can reach the vertex count. An iterative stack or BFS avoids that entirely. Source equal to destination returns true with no traversal at all, which falls out naturally if the source is marked visited and checked before the loop. Union-Find is the better fit when many queries are asked against one fixed graph, since it answers each in near-constant time after construction.
Plain reachability — DFS or BFS from the source, stopping when the destination appears. The only detail that matters is building the adjacency list in both directions, since the edges are undirected.
Approach
Before reading on: price up what the direct approach costs here, then ask whether you are really just merging groups and asking what connects. Aim for O(V + E) time and O(V + E) space.
Recognise the simpler question
There are no weights and no shortest-path requirement. Dijkstra and level-tracking BFS solve something harder — plain reachability needs neither.
Build an undirected adjacency list
Add both directions for every edge. Omitting the reverse entry silently makes reachable vertices appear unreachable.
Traverse from the source
Run DFS or BFS outward from the start vertex. Either works — the choice depends on input shape, not correctness.
Mark visited vertices
An undirected edge is a two-cycle, so a traversal without a visited set bounces between two vertices forever. Marking on entry prevents that.
Handle the trivial case
Source equal to destination returns true without traversing. Marking the source visited and checking before the loop covers this naturally.
Prefer iteration on large graphs
Recursive DFS can reach a depth equal to the vertex count and overflow the stack. An explicit stack or BFS queue avoids the risk entirely.
Cost of the traversal
Every vertex and edge is examined at most once, giving O(V + E) time and O(V + E) space. Union-Find suits many queries against one fixed graph.
Solution & live demo
Common pitfalls
Adding edges in one direction only
adj[a].append(b)
adj[a].append(b) adj[b].append(a)
An undirected edge must be traversable from either endpoint. Storing one direction makes the graph directed and reports no path whenever the route needs to travel against an edge's insertion order.
Marking visited after recursing
for v in adj[u]:
if not seen[v] and dfs(v): return True
seen[u] = Trueseen[u] = True for v in adj[u]:
Undirected edges are symmetric, so a neighbour immediately recurses back into u. Without the flag already set, that becomes infinite mutual recursion and the stack overflows.
Missing the trivial case
return dfs(source)
if source == destination:
return TrueWhen the two are the same vertex the answer is trivially true, but a DFS that marks before testing may not report it depending on the check's placement. Handling it up front removes the ambiguity.
Edge cases
Return true immediately -- valid even with zero edges.
DFS exhausts its component without finding it -- return false.
Both adj[a].append(b) and adj[b].append(a) are required for correctness.
Harmless -- visited check prevents infinite recursion.