Find if Path Exists in Graph Solution

Problem

You have an undirected graph with n nodes labeled 0 through n - 1. Given a list of bidirectional edges and two nodes source and destination, determine whether any path connects source to destination.

Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Output: false
Explanation: nodes 0–2 form one isolated component and nodes 3–5 form another, so there is no path between them

Counter-example where a path does exist:

Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: true
Explanation: 0 → 1 → 2 (or 0 → 2 directly) both work

Intuition

The question is really asking: do source and destination belong to the same connected component? Any traversal starting at source will eventually reach every reachable node; if destination shows up, the answer is true. Alternatively, Union-Find lets you group nodes into components as you process edges, then answer the question with a single root comparison.

Approach 1 — BFS

Build an adjacency list, then do a breadth-first search from source. Keep a visited set to avoid re-entering nodes. Return true the moment destination is dequeued.

If source == destination, return true immediately.
Build an adjacency list: for each undirected edge [u, v], add v to u's list and u to v's list.
Initialize a queue with source and mark it visited.
While the queue is non-empty, dequeue current_node; if it equals destination, return true.
Enqueue each unvisited neighbor and mark it visited before enqueuing.
If the queue empties without hitting destination, return false.

1from collections import deque
2
3def validPath(n: int, edges: list[list[int]], source: int, destination: int) -> bool:
4    if source == destination:
5        return True
6
7    adjacency = [[] for _ in range(n)]
8    for node_a, node_b in edges:
9        adjacency[node_a].append(node_b)
10        adjacency[node_b].append(node_a)  # undirected: add both directions
11
12    queue = deque([source])
13    visited = {source}
14
15    while queue:
16        current_node = queue.popleft()
17        if current_node == destination:
18            return True
19        for neighbor in adjacency[current_node]:
20            if neighbor not in visited:
21                visited.add(neighbor)  # mark before enqueuing to prevent duplicate entries
22                queue.append(neighbor)
23
24    return False

Time: O(n + e) — each node and each edge endpoint is processed at most once.

Space: O(n + e) — the adjacency list stores all edges twice, and the visited structure holds up to n entries.

Approach 2 — Union-Find

Process every edge by merging the two nodes into the same component. After all edges are processed, check whether source and destination share the same root. No graph traversal needed at query time.

Initialize parent[i] = i (each node is its own root) and rank[i] = 0 for all nodes.
For each edge [u, v], call union(u, v) to merge their components.
In find(node), apply path compression: recursively set each node's parent to the root.
In union, attach the root with lower rank under the root with higher rank (union by rank).
Return find(source) == find(destination).

1def validPath(n: int, edges: list[list[int]], source: int, destination: int) -> bool:
2    parent = list(range(n))
3    rank = [0] * n
4
5    def find(node: int) -> int:
6        if parent[node] != node:
7            parent[node] = find(parent[node])  # path compression flattens the tree
8        return parent[node]
9
10    def union(node_a: int, node_b: int) -> None:
11        root_a, root_b = find(node_a), find(node_b)
12        if root_a == root_b:
13            return
14        if rank[root_a] < rank[root_b]:
15            root_a, root_b = root_b, root_a
16        parent[root_b] = root_a  # attach smaller tree under taller to minimize depth
17        if rank[root_a] == rank[root_b]:
18            rank[root_a] += 1
19
20    for node_a, node_b in edges:
21        union(node_a, node_b)
22
23    return find(source) == find(destination)

Time: O((n + e) × α(n)) — α is the inverse Ackermann function, effectively constant; building and querying the structure touches each node and edge once.

Space: O(n) — only the parent and rank arrays; no adjacency list needed.

Complexity Summary

Approach	Time	Space	When to use
BFS	O(n + e)	O(n + e)	When you need to find or reconstruct the actual path, not just its existence
Union-Find	O((n + e) × α(n))	O(n)	When you only need to answer connectivity queries and want minimal memory

Common Mistakes

Building only one direction of each undirected edge — adding adjacency[u] → v but forgetting adjacency[v] → u turns the graph into a directed one, so you can traverse u → v but never v → u, producing false negatives on any path that requires the reverse direction.
Marking nodes visited after dequeuing instead of before enqueuing — the same node can be added to the queue multiple times before it's dequeued, causing redundant BFS work; mark it visited the moment you decide to enqueue it.
Comparing parent[source] and parent[destination] directly in Union-Find — parent[node] is not necessarily the root; always call find() on both nodes so path compression resolves the actual roots before comparing.
Omitting path compression in find() — without it, a long chain of unions builds a linked-list-shaped tree and each find() call walks the full chain in O(n), erasing the efficiency advantage of Union-Find.
Forgetting the source == destination early-exit — a node can always reach itself even with zero edges; some implementations incorrectly return false when source equals destination because the BFS dequeues and immediately looks for neighbors.

Find if Path Exists in Graph — Solution