#1971

Easy

auto_awesomeGraph traversal with depth-first search

LeetCode Problem Workspace

Find if Path Exists in Graph

Determine if a valid path exists between two vertices in a bi-directional graph using traversal techniques.

depth first search breadth first search union find graph

Problem Statement

You are given an undirected graph with n vertices labeled from 0 to n - 1. The graph is represented as a list of bi-directional edges, where each edge connects two distinct vertices. No edge appears more than once, and no vertex connects to itself.

Given the graph edges and two vertices, source and destination, determine if a valid path exists from the source vertex to the destination vertex. Return true if such a path exists, otherwise return false.

Examples

Example 1

Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2

Output: true

There are two paths from vertex 0 to vertex 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

There is no path from vertex 0 to vertex 5.

Constraints

1 <= n <= 2 * 105
0 <= edges.length <= 2 * 105
edges[i].length == 2
0 <= ui, vi <= n - 1
ui != vi
0 <= source, destination <= n - 1
There are no duplicate edges.
There are no self edges.

Solution Approach

Depth-First Search (DFS)

Implement DFS starting from the source vertex. Recursively visit all connected neighbors while marking visited vertices. If the destination is reached during traversal, return true; otherwise, return false after exploring all reachable nodes.

Breadth-First Search (BFS)

Use a queue to perform BFS from the source vertex. Add neighbors of each vertex to the queue while tracking visited vertices. If the destination vertex is dequeued, return true. If the queue empties without reaching destination, return false.

Union-Find Approach

Initialize a union-find structure to group connected components. Union vertices for each edge. After processing all edges, check if the source and destination belong to the same connected component. If yes, return true; otherwise, return false.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

DFS and BFS both run in O(V + E) time and O(V + E) space, where V is vertices and E is edges. Union-Find with path compression and union by rank runs in near O(V + E) time and O(V) space. All approaches efficiently handle sparse or dense graphs without redundant traversal.

What Interviewers Usually Probe

Expect optimized traversal without revisiting nodes in DFS or BFS.
Union-Find may indicate awareness of connected components instead of explicit search.
Handling edge cases with disconnected nodes is important to confirm correct path detection.

Common Pitfalls or Variants

Common pitfalls

Failing to mark visited nodes, causing infinite recursion in cycles.
Confusing directed and undirected edges, leading to missing valid paths.
Assuming all nodes are connected, resulting in incorrect true returns for disconnected graphs.

Follow-up variants

Check for shortest path existence or length between source and destination.
Detect if multiple distinct paths exist between two vertices.
Handle directed graphs instead of undirected graphs for path existence.

FAQ

What is the best approach for 'Find if Path Exists in Graph' for large graphs?

DFS or BFS are straightforward for connected components, while Union-Find efficiently checks connectivity without full traversal.

Does the graph being undirected change the traversal method?

Yes, both DFS and BFS treat edges as bi-directional, so neighbors are explored in both directions.

How do I avoid infinite loops in DFS on this graph problem?

Track visited vertices to prevent revisiting nodes, which is critical in graphs with cycles.

Can I use BFS instead of DFS for this problem?

Absolutely, BFS is equally valid and may find the shortest path faster if required.

What are typical constraints I need to consider?

Vertex count up to 2*10^5, no duplicate edges, no self-loops, and edges can be zero length.

terminal

Solution

Solution 1: DFS

We first convert $\textit{edges}$ into an adjacency list $g$, then use DFS to determine whether there is a path from $\textit{source}$ to $\textit{destination}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def validPath(
        self, n: int, edges: List[List[int]], source: int, destination: int
    ) -> bool:
        def dfs(i: int) -> bool:
            if i == destination:
                return True
            vis.add(i)
            for j in g[i]:
                if j not in vis and dfs(j):
                    return True
            return False

        g = [[] for _ in range(n)]
        for u, v in edges:
            g[u].append(v)
            g[v].append(u)
        vis = set()
        return dfs(source)

Solution 2: BFS

We can also use BFS to determine whether there is a path from $\textit{source}$ to $\textit{destination}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def validPath(
        self, n: int, edges: List[List[int]], source: int, destination: int
    ) -> bool:
        def dfs(i: int) -> bool:
            if i == destination:
                return True
            vis.add(i)
            for j in g[i]:
                if j not in vis and dfs(j):
                    return True
            return False

        g = [[] for _ in range(n)]
        for u, v in edges:
            g[u].append(v)
            g[v].append(u)
        vis = set()
        return dfs(source)

Solution 3: Union-Find

Union-Find is a tree-like data structure that, as the name suggests, is used to handle some disjoint set **merge** and **query** problems. It supports two operations:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def validPath(
        self, n: int, edges: List[List[int]], source: int, destination: int
    ) -> bool:
        def dfs(i: int) -> bool:
            if i == destination:
                return True
            vis.add(i)
            for j in g[i]:
                if j not in vis and dfs(j):
                    return True
            return False

        g = [[] for _ in range(n)]
        for u, v in edges:
            g[u].append(v)
            g[v].append(u)
        vis = set()
        return dfs(source)

Continue Practicing

#2092 find all people with secret #2316 count unreachable pairs of nodes in an undirected graph #2368 reachable nodes with restrictions