Find if Path Exists in Graph

Find if Path Exists in Graph

What is this problem about?

The Find if Path Exists in Graph coding problem is a fundamental connectivity task. Given an undirected graph with $n$ nodes and a list of edges, you need to determine if there is a valid path from a source node to a destination node. It is a classic "reachability" check.

Why is this asked in interviews?

Companies like Google, Amazon, and Bloomberg use this Find if Path Exists in Graph interview question to verify a candidate's baseline knowledge of Graph interview patterns. It evaluates whether you can represent a graph (e.g., using an adjacency list) and traverse it efficiently. Reachability is the core of networking, social connections, and pathfinding in games.

Algorithmic pattern used

This problem can be solved using several patterns:

1. Breadth-First Search (BFS): Uses a queue to explore neighbors layer-by-layer. Good for finding the shortest path (though not required here).
2. Depth-First Search (DFS): Uses a stack (or recursion) to explore as deep as possible along a branch.
3. Union Find (Disjoint Set Union): Groups connected components. If find(source) == find(destination), a path exists. This is often the most efficient for multiple connectivity queries.

Example explanation

Graph: 0-1, 1-2, 3-4. Source: 0, Destination: 2.

1. Start at 0. Add to visited set.
2. Neighbors of 0: 1. Add 1 to queue.
3. Pop 1. Neighbors of 1: 0 (visited) and 2. Add 2 to queue.
4. Pop 2. 2 is the destination! Result: True.

If destination was 4:

1. Exhaust all nodes reachable from 0: {0, 1, 2}.
2. 4 is not in the set. Result: False.

Common mistakes candidates make

• No Visited Set: Forgetting to track visited nodes, leading to infinite loops in graphs with cycles.
• Adjacency Matrix: Using an $N imes N$ matrix for sparse graphs, which leads to $O(N^2)$ space and time—use an Adjacency List instead.
• Recursive DFS: Not considering the stack depth for extremely deep, linear graphs (leads to StackOverflowError).

Interview preparation tip

For simple reachability, BFS and DFS are functionally identical. However, mention Union Find if the graph is static and you expect many queries about different pairs of nodes—it shows you understand amortized complexity.