Find if Path Exists in Graph — BFS, DFS, and Union Find

Problem Statement#

LeetCode 1971 — Find if Path Exists in Graph (Easy)

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] = [u, v] denotes a bi-directional edge between vertex u and vertex v. 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.

Constraints:

• 1 <= n <= 2 * 10^5
• 0 <= edges.length <= 2 * 10^5
• edges[i].length == 2, 0 <= u, v <= n - 1, u != v
• 0 <= source, destination <= n - 1

Example 1:

n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: true (path 0 -> 1 -> 2 or directly 0 -> 2)

Example 2:

n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Output: false (the graph splits into two components and 0 cannot reach 5)

Why This Problem Matters#

Despite its Easy tag, this problem is a remarkably common interview opener at Amazon, Google, and Meta because it sits at the intersection of three major graph patterns: BFS traversal, DFS traversal, and Union Find. A single follow-up nudge from the interviewer turns it into a much harder dynamic connectivity question — the kind of problem regularly seen at staff-engineer level.

The interviewer is checking:

1. Adjacency list construction. Can you convert an edge list to a usable adjacency list in O(N + E) time without confusing yourself on undirected edges?
2. Algorithm trade-offs. BFS, DFS, and Union Find all solve this in roughly the same time, but each has very different strengths for follow-ups (shortest path, recursion depth, edge streaming).
3. Edge cases. What happens when source == destination? When the graph is empty? When edges form self-loops or duplicates? These are all stated as not occurring, but interviewers love to probe whether you would ask.

The problem also demonstrates the philosophy that "easy" graph questions are often gateways to advanced topics. Mastering all three approaches here pays compound interest later.

The Core Insight#

Reachability in an undirected graph reduces to "is destination in the connected component of source?" Three independent algorithms answer that question:

• BFS: Explore nodes level by level from source. If you ever pop destination, return true.
• DFS: Same idea but depth-first. Slightly easier to write recursively, slightly more risky for stack depth on chain graphs.
• Union Find: Merge every edge into a disjoint-set forest. After processing all edges, source and destination are connected iff find(source) == find(destination).

For a single query, all three are O(N + E) time. The reason to memorize all three is that each becomes the right answer when the problem is modified:

• Need shortest path? BFS wins because it tracks distance natively.
• Need many queries on the same graph? Union Find wins because it preprocesses once and answers each query in near-O(1).
• Need to know the path itself? DFS makes path reconstruction with a parent map almost trivial.

Visual Dry Run#

Use Example 2: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5.

Adjacency list (undirected, so each edge added in both directions):
  0: [1, 2]
  1: [0]
  2: [0]
  3: [5, 4]
  4: [5, 3]
  5: [3, 4]
 
BFS from 0:
  queue = [0], visited = {0}
  pop 0 -> push 1, 2. visited = {0, 1, 2}
  pop 1 -> 0 already visited
  pop 2 -> 0 already visited
  queue empty, destination 5 not seen.
Return false.
 
Union Find on the same edges:
  union(0, 1): parent[1] = 0
  union(0, 2): parent[2] = 0
  union(3, 5): parent[5] = 3
  union(5, 4): root of 5 is 3, parent[4] = 3
  union(4, 3): already same root.
  find(0) = 0, find(5) = 3. Different roots -> false.

Both methods agree because the graph splits into two connected components: {0, 1, 2} and {3, 4, 5}.

Solution (Optimal)#

Python (BFS)#

from collections import deque, defaultdict
 
class Solution:
    def validPath(self, n: int, edges: list[list[int]], source: int, destination: int) -> bool:
        if source == destination:
            return True                           # Trivial early return
 
        adj = defaultdict(list)                   # Build undirected adjacency list
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)                      # Undirected = both directions
 
        visited = {source}
        queue = deque([source])
 
        while queue:
            node = queue.popleft()
            for nxt in adj[node]:
                if nxt == destination:
                    return True                   # Found the target
                if nxt not in visited:
                    visited.add(nxt)              # Mark on enqueue
                    queue.append(nxt)
 
        return False                              # Exhausted component without finding it

JavaScript (Union Find)#

/**
 * Union Find with path compression and union by rank.
 * Best when edges arrive in a stream or many queries hit the same graph.
 */
var validPath = function(n, edges, source, destination) {
    const parent = Array.from({length: n}, (_, i) => i);  // each node is its own root
    const rank = new Array(n).fill(0);
 
    const find = (x) => {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];                // path compression (halving)
            x = parent[x];
        }
        return x;
    };
 
    const union = (a, b) => {
        const ra = find(a), rb = find(b);
        if (ra === rb) return;                            // already merged
        // Union by rank keeps the tree shallow
        if (rank[ra] < rank[rb]) parent[ra] = rb;
        else if (rank[ra] > rank[rb]) parent[rb] = ra;
        else { parent[rb] = ra; rank[ra]++; }
    };
 
    for (const [u, v] of edges) union(u, v);              // merge every edge
 
    return find(source) === find(destination);            // same component?
};

Complexity. BFS / DFS run in O(N + E) time and O(N) space. Union Find with path compression and union by rank runs in O((N + E) * alpha(N)) time, where alpha is the inverse Ackermann function and behaves like a constant for any realistic input.

Common Mistakes#

1. Forgetting the graph is undirected. Adding adj[u].append(v) only goes one way. You must add the reverse edge too. This single mistake produces a working but wrong solution that passes only directed test cases.
2. Building an O(N times N) adjacency matrix. With n up to 2 times 10 to the 5, an N times N matrix uses 40 GB. Always use an adjacency list for sparse graphs.
3. Recursive DFS without sys.setrecursionlimit (Python). A chain graph of 200,000 nodes will blow the default limit. Either bump the limit or write an iterative DFS.
4. Forgetting source == destination early return. When source equals destination the answer is trivially true. Without the early return some implementations still work, but a careless one might return false because it never explores.
5. Skipping path compression in Union Find. Without it the find operation can degrade to O(N) per call on adversarial inputs, turning the whole solution into O(N times E).

Interview Tips#

• Volunteer the three approaches up front. Saying "BFS, DFS, and Union Find all work; I will pick BFS because it extends naturally to shortest path follow-ups" demonstrates breadth.
• Highlight the undirected detail. Explicitly say "the graph is undirected, so I will add both directions to the adjacency list." Interviewers often nod and move on.
• Discuss query patterns. If the interviewer says "imagine many queries on the same graph," pivot to Union Find without prompting.
• Note alpha (Inverse Ackermann). Mentioning that Union Find is "essentially constant per operation" signals depth without being pedantic.

Follow-up Questions#

1. Many queries on the same graph. Switch to Union Find. Build once in O(N alpha(N)), answer each query in O(alpha(N)).
2. Edges arrive in a stream and you must answer queries online. Use the dynamic Union Find approach. Note that deletions are not supported by vanilla Union Find — you would need link-cut trees for that.
3. Return the actual path, not just the boolean. Run BFS storing a parent map, then walk back from destination to source.
4. Find the shortest path. BFS already explores level by level; record distance when enqueuing.
5. Weighted edges with positive weights. Switch to Dijkstra's algorithm with a min-heap.

Key Takeaways#

• Path existence in an undirected graph is a connected components problem; three different algorithms solve it.
• BFS is the right default and extends naturally to shortest-path follow-ups.
• Union Find with path compression and union by rank shines when there are many queries on the same graph or when edges arrive online.
• Always remember to add both directions when building the adjacency list of an undirected graph.
• Discussing trade-offs between BFS, DFS, and Union Find is the easiest way to differentiate yourself in a FAANG interview.
• The source == destination edge case is small but interviewers absolutely watch for it.