Find if Path Exists in Graph
Problem
Given an undirected graph with n nodes labeled from 0 to n-1 and a list of edges, determine if there is a valid path from the source node to the destination node.
- 1 ≤ n ≤ 2 * 10⁵
- 0 ≤ edges.length ≤ 2 * 10⁵
- edges[i].length == 2
- 0 ≤ ui, vi < n
- ui != vi
- 0 ≤ source, destination < n
- There are no duplicate edges.
Example
n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2trueThe edges create a connected cycle among nodes {0,1,2}, so every node is reachable from every other node. Starting from 0, a DFS (or BFS) marks reachable nodes by following edges while avoiding revisits via a visited set. Node 2 is reachable from 0 (either directly via edge (2,0) or through 0 → 1 → 2), so the search will eventually visit 2 and return true.
Approach
Straightforward Solution
A brute-force approach might attempt to enumerate all possible paths between source and destination, which is exponential and infeasible for large graphs.
Core Observation
The problem reduces to checking connectivity between two nodes in an undirected graph. This is a classic graph traversal problem where the existence of a path corresponds to reachability in the graph.
Path to Optimal
Recognizing that the problem is about reachability, a Depth-First Search (DFS) or Breadth-First Search (BFS) can efficiently explore the graph starting from the source node. DFS explores as deep as possible along each branch before backtracking, and can terminate early upon reaching the destination. This approach avoids enumerating all paths and runs in linear time relative to the number of nodes and edges.
Optimal Approach
Build an adjacency list representation of the graph for O(1) neighbor access. Use a recursive DFS starting from the source node, marking visited nodes to avoid cycles. If the destination node is encountered during traversal, return true immediately. If DFS completes without finding the destination, return false. This guarantees O(n + m) time complexity, where n is the number of nodes and m is the number of edges.
Time
O(n + m)
Each node is visited at most once, and each edge is explored at most twice (once from each endpoint) during the DFS traversal, resulting in linear time relative to the graph size.
Space
O(n + m)
The adjacency list requires O(n + m) space to store all edges, and the visited set requires O(n) space to track visited nodes. The recursion stack can go as deep as O(n) in the worst case.
Pattern Spotlight
DFS (Graph Connectivity)
When checking if a path exists between two nodes in an unweighted graph, use DFS to explore reachable nodes from the source, marking visited nodes to avoid cycles, and terminate early upon reaching the destination.
Solution
| 1 | from collections import defaultdict |
| 2 | |
| 3 | class Solution: |
| 4 | def validPath(self, n: int, edges: [[int]], source: int, destination: int) -> bool: |
| 5 | graph = defaultdict(list) |
| 6 | |
| 7 | for u, v in edges: |
| 8 | graph[u].append(v) |
| 9 | graph[v].append(u) |
| 10 | |
| 11 | visited = set() |
| 12 | |
| 13 | def dfs(node): |
| 14 | if node == destination: |
| 15 | return True |
| 16 | visited.add(node) |
| 17 | |
| 18 | for neighbor in graph[node]: |
| 19 | if neighbor not in visited and dfs(neighbor): |
| 20 | return True |
| 21 | return False |
| 22 | |
| 23 | return dfs(source) |
| 1 | import java.util.*; |
| 2 | |
| 3 | class Solution { |
| 4 | public boolean validPath(int n, int[][] edges, int source, int destination) { |
| 5 | Map<Integer, List<Integer>> graph = new HashMap<>(); |
| 6 | for (int i = 0; i < n; i++) { |
| 7 | graph.put(i, new ArrayList<>()); |
| 8 | } |
| 9 | for (int[] edge : edges) { |
| 10 | graph.get(edge[0]).add(edge[1]); |
| 11 | graph.get(edge[1]).add(edge[0]); |
| 12 | } |
| 13 | Set<Integer> visited = new HashSet<>(); |
| 14 | |
| 15 | return dfs(source, destination, graph, visited); |
| 16 | } |
| 17 | |
| 18 | private boolean dfs(int node, int destination, Map<Integer, List<Integer>> graph, Set<Integer> visited) { |
| 19 | if (node == destination) { |
| 20 | return true; |
| 21 | } |
| 22 | visited.add(node); |
| 23 | for (int neighbor : graph.get(node)) { |
| 24 | if (!visited.contains(neighbor) && dfs(neighbor, destination, graph, visited)) { |
| 25 | return true; |
| 26 | } |
| 27 | } |
| 28 | return false; |
| 29 | } |
| 30 | } |
| 1 | #include <vector> |
| 2 | #include <unordered_map> |
| 3 | #include <unordered_set> |
| 4 | |
| 5 | using namespace std; |
| 6 | |
| 7 | class Solution { |
| 8 | public: |
| 9 | bool validPath(int n, vector<vector<int>>& edges, int source, int destination) { |
| 10 | unordered_map<int, vector<int>> graph; |
| 11 | for (int i = 0; i < n; ++i) { |
| 12 | graph[i] = vector<int>(); |
| 13 | } |
| 14 | for (const auto& edge : edges) { |
| 15 | graph[edge[0]].push_back(edge[1]); |
| 16 | graph[edge[1]].push_back(edge[0]); |
| 17 | } |
| 18 | unordered_set<int> visited; |
| 19 | return dfs(source, destination, graph, visited); |
| 20 | } |
| 21 | |
| 22 | private: |
| 23 | bool dfs(int node, int destination, unordered_map<int, vector<int>>& graph, unordered_set<int>& visited) { |
| 24 | if (node == destination) { |
| 25 | return true; |
| 26 | } |
| 27 | visited.insert(node); |
| 28 | for (int neighbor : graph[node]) { |
| 29 | if (visited.find(neighbor) == visited.end() && dfs(neighbor, destination, graph, visited)) { |
| 30 | return true; |
| 31 | } |
| 32 | } |
| 33 | return false; |
| 34 | } |
| 35 | }; |
| 1 | var validPath = function(n, edges, source, destination) { |
| 2 | const graph = new Map(); |
| 3 | for (let i = 0; i < n; i++) { |
| 4 | graph.set(i, []); |
| 5 | } |
| 6 | for (const [u, v] of edges) { |
| 7 | graph.get(u).push(v); |
| 8 | graph.get(v).push(u); |
| 9 | } |
| 10 | const visited = new Set(); |
| 11 | |
| 12 | function dfs(node) { |
| 13 | if (node === destination) { |
| 14 | return true; |
| 15 | } |
| 16 | visited.add(node); |
| 17 | for (const neighbor of graph.get(node)) { |
| 18 | if (!visited.has(neighbor) && dfs(neighbor)) { |
| 19 | return true; |
| 20 | } |
| 21 | } |
| 22 | return false; |
| 23 | } |
| 24 | |
| 25 | return dfs(source); |
| 26 | }; |
Step-by-Step Solution
Construct Adjacency List to Represent the Undirected Graph
| 5 | graph = defaultdict(list) |
| 7 | for u, v in edges: |
| 8 | graph[u].append(v) |
| 9 | graph[v].append(u) |
Objective
To build a graph representation that allows efficient neighbor lookups for each node.
Key Insight
An adjacency list is the most efficient way to represent sparse graphs, enabling O(1) average-time access to neighbors. Since the graph is undirected, each edge is added to both nodes' adjacency lists, ensuring bidirectional traversal during DFS.
Interview Quick-Check
Core Logic
Building the adjacency list from edges allows the DFS to quickly access all neighbors of a node without scanning the entire edge list.
Common Pitfalls & Bugs
Forgetting to add both directions for undirected edges leads to incomplete graph representation and incorrect traversal.
Track Visited Nodes to Avoid Revisiting and Cycles
| 11 | visited = set() |
Objective
To maintain a record of nodes already explored to prevent infinite recursion and redundant work.
Key Insight
Without tracking visited nodes, DFS can revisit nodes endlessly in cyclic graphs, causing infinite loops. The visited set ensures each node is processed once, preserving correctness and efficiency.
Interview Quick-Check
Core Logic
The visited set acts as a memory of explored nodes, preventing cycles and repeated work during DFS.
Common Pitfalls & Bugs
Failing to mark nodes as visited before recursive calls can cause infinite recursion or stack overflow.
Recursively Explore Nodes Using DFS and Terminate Early on Destination
| 13 | def dfs(node): |
| 14 | if node == destination: |
| 15 | return True |
| 16 | visited.add(node) |
| 18 | for neighbor in graph[node]: |
| 19 | if neighbor not in visited and dfs(neighbor): |
| 20 | return True |
| 21 | return False |
Objective
To traverse the graph depth-first from the source, returning true immediately upon reaching the destination.
Key Insight
DFS explores neighbors recursively, diving deep into each path. The early return upon finding the destination avoids unnecessary exploration, improving efficiency. The recursion unwinds as soon as a valid path is found, ensuring minimal traversal.
Interview Quick-Check
Core Logic
DFS recursively explores neighbors, returning true immediately when the destination node is found, enabling early termination.
State & Boundaries
The base case checks if the current node is the destination, ensuring correctness and termination.
Common Pitfalls & Bugs
Not returning the result of recursive calls or failing to check visited nodes before recursion can cause incorrect results or infinite loops.
Initiate DFS from Source and Return Final Reachability Result
| 23 | return dfs(source) |
Objective
To start the DFS traversal from the source node and return whether a path to the destination exists.
Key Insight
The initial call triggers the entire recursive exploration. The returned boolean directly answers the problem by indicating if the destination is reachable from the source.
Interview Quick-Check
Core Logic
Starting DFS from the source node explores all reachable nodes, and the returned boolean indicates path existence.
Line Analysis
This solution has 5 Critical lines interviewers watch for.
if node == destination:Check if the current node is the destination.
This line is the critical early-exit condition that allows the DFS to stop searching as soon as the destination is reached, preventing unnecessary exploration and ensuring efficiency.
visited = set()Create a set to track visited nodes.
The visited set prevents revisiting nodes, which is critical to avoid infinite loops in cyclic graphs and to ensure linear time complexity.
visited.add(node)Mark the current node as visited.
Adding the node to visited before exploring neighbors prevents revisiting it in future recursive calls, avoiding cycles and redundant work.
if neighbor not in visited and dfs(neighbor):Recursively call DFS on unvisited neighbors and check if destination is reachable.
This recursive call explores deeper paths, and the conditional ensures that only unvisited nodes are explored, maintaining correctness and efficiency.
return TrueReturn true immediately if a path to destination is found through a neighbor.
This early return propagates success up the call stack, enabling the algorithm to stop searching once a valid path is found.
graph[u].append(v)Add the edge's second node to the first node's adjacency list.
This step records the connection from u to v, enabling traversal from u to v.
graph[v].append(u)Add the edge's first node to the second node's adjacency list.
Because the graph is undirected, this step ensures traversal from v to u is possible, maintaining bidirectional connectivity.
return TrueReturn true if the destination is reached.
Returning true here propagates the success signal up the recursive call stack, enabling early termination of all ancestor calls.
return FalseReturn false if no neighbors lead to the destination.
Returning false here correctly signals that the current path does not lead to the destination, allowing backtracking to explore alternative paths.
return dfs(source)Start DFS from the source node and return whether a path exists.
This call initiates the entire traversal and returns the final answer to the problem, encapsulating the solution.
graph = defaultdict(list)Initialize the adjacency list as a default dictionary of lists.
Using a defaultdict simplifies graph construction by automatically creating empty neighbor lists for new nodes, enabling efficient edge insertion.
def dfs(node):Define the recursive DFS function to explore nodes.
Encapsulating DFS logic in a helper function allows clean recursion and state management for graph traversal.
for neighbor in graph[node]:Iterate over all neighbors of the current node.
Exploring neighbors is the core of DFS traversal, enabling the search to proceed through the graph.
for u, v in edges:Iterate over each edge to build the graph.
Processing each edge ensures the graph representation includes all connections, which is essential for accurate traversal.
Test Your Understanding
Why does marking nodes as visited during DFS prevent infinite loops and ensure correctness?
Marking nodes as visited prevents revisiting the same node multiple times, which avoids infinite cycles in graphs with cycles and ensures that each node is processed only once, maintaining linear time complexity.
Related Problems
DFS pattern
Don't just read it. Drill it.
Reconstruct Find if Path Exists in Graph from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Find if Path Exists in Graph drill