Find if Path Exists in Graph

Difficulty: Easy | Acceptance: 55.10% | Paid: No Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory

There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). You are given a 2D integer array edges where edges[i] = [ui, vi] denotes that there is an edge between ui and vi. 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 source to 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.

• Examples
• Constraints
• Approach 1: Depth-First Search (DFS)
• Approach 2: Breadth-First Search (BFS)
• Approach 3: Union-Find (Disjoint Set Union)

Examples

Example 1:

Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: true
Explanation: There are two paths from 0 to 2:
- 0 → 1 → 2
- 0 → 2

Example 2:

Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Output: false
Explanation: There is no path from 0 to 5.

Constraints

1 <= n <= 2 * 10⁵
0 <= edges.length <= 2 * 10⁵
edges[i].length == 2
0 <= uᵢ, vᵢ <= n - 1
uᵢ != vᵢ
0 <= source, destination <= n - 1
There are no duplicate edges.
There are no self edges.

Approach 1: Depth-First Search (DFS)

Intuition We can treat the graph as a tree-like structure and explore it recursively. Starting from the source node, we visit all unvisited neighbors. If we encounter the destination node during this traversal, a path exists.

Steps

• Build an adjacency list to represent the graph.
• Initialize a set to keep track of visited nodes to prevent cycles.
• Define a recursive DFS function that takes the current node as input.
• In the DFS function, if the current node is the destination, return true.
• Mark the current node as visited and recursively call DFS on all unvisited neighbors.
• If the recursion completes without finding the destination, return false.

from typing import List
from collections import defaultdict

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        if source == destination:
            return True
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        visited = set()
        def dfs(node):
            if node == destination:
                return True
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    if dfs(neighbor):
                        return True
            return False
        return dfs(source)

Complexity

• Time: O(V + E), where V is the number of vertices and E is the number of edges. We visit each node and edge at most once.
• Space: O(V + E) to store the adjacency list and the visited set/recursion stack.
• Notes: Recursive DFS may cause a stack overflow for very deep graphs (e.g., a linked list of 2*10⁵ nodes). An iterative stack-based DFS is safer for such cases.

Approach 2: Breadth-First Search (BFS)

Intuition BFS explores the graph layer by layer. Starting from the source, we visit all immediate neighbors before moving to their neighbors. This guarantees that we find the shortest path in terms of the number of edges, though for this problem, we only need to know if a path exists.

Steps

• Build an adjacency list.
• Initialize a queue with the source node and a visited set.
• While the queue is not empty, dequeue a node.
• If the node is the destination, return true.
• Otherwise, mark the node as visited and enqueue all its unvisited neighbors.
• If the loop finishes, return false.

from typing import List
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
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        visited = set([source])
        queue = deque([source])
        while queue:
            node = queue.popleft()
            if node == destination:
                return True
            for neighbor in graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        return False

Complexity

• Time: O(V + E), as we process each vertex and edge once.
• Space: O(V + E) for the graph and O(V) for the queue and visited set.
• Notes: BFS is generally preferred over recursive DFS for large graphs to avoid stack overflow errors.

Approach 3: Union-Find (Disjoint Set Union)

Intuition We can model the problem as connecting components. Initially, every node is its own component. By iterating through the edges, we merge the components of the connected nodes. Finally, if the source and destination nodes belong to the same component (have the same root), a path exists.

Steps

• Initialize a parent array where parent[i] = i.
• Define a find function to locate the root of a node with path compression.
• Define a union function to merge the roots of two nodes.
• Iterate through all edges and perform union(u, v).
• After processing all edges, check if find(source) == find(destination).

from typing import List

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        parent = list(range(n))
        
        def find(i):
            if parent[i] != i:
                parent[i] = find(parent[i])
            return parent[i]
        
        def union(i, j):
            root_i = find(i)
            root_j = find(j)
            if root_i != root_j:
                parent[root_i] = root_j
        
        for u, v in edges:
            union(u, v)
            
        return find(source) == find(destination)

Complexity

• Time: O(E * α(V)), where α is the inverse Ackermann function. This is effectively linear time, O(E), as α(V) grows extremely slowly.
• Space: O(V) to store the parent array.
• Notes: Union-Find is highly efficient for dynamic connectivity problems and is often faster than DFS/BFS for this specific use case because it avoids the overhead of building an explicit adjacency list and recursion/stack management.