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.

#1971

Easy

auto_awesome图·DFS·traversal

LeetCode 题解工作台

寻找图中是否存在路径

有一个具有 n 个顶点的双向图，其中每个顶点标记从 0 到 n - 1 （包含 0 和 n - 1 ）。图中的边用一个二维整数数组 edges 表示，其中 edges[i] = [u i , v i ] 表示顶点 ui 和顶点 vi 之间的双向边。每个顶点对由最多一条边连接，并且没有顶点存…

深度优先搜索广度优先搜索并查集图

题目描述

有一个具有 n 个顶点的双向图，其中每个顶点标记从 0 到 n - 1（包含 0 和 n - 1）。图中的边用一个二维整数数组 edges 表示，其中 edges[i] = [u_i, v_i] 表示顶点 ui 和顶点 vi 之间的双向边。每个顶点对由 最多一条 边连接，并且没有顶点存在与自身相连的边。

请你确定是否存在从顶点 source 开始，到顶点 destination 结束的 有效路径 。

给你数组 edges 和整数 n、source 和 destination，如果从 source 到 destination 存在 有效路径 ，则返回 true，否则返回 false 。

示例 1：

输入：n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
输出：true
解释：存在由顶点 0 到顶点 2 的路径:
- 0 → 1 → 2 
- 0 → 2

示例 2：

输入：n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
输出：false
解释：不存在由顶点 0 到顶点 5 的路径.

提示：

1 <= n <= 2 * 10⁵
0 <= edges.length <= 2 * 10⁵
edges[i].length == 2
0 <= u_i, v_i <= n - 1
u_i != v_i
0 <= source, destination <= n - 1
不存在重复边
不存在指向顶点自身的边

lightbulb

解题思路

方法一：DFS

我们首先将 $\textit{edges}$ 转换成邻接表 $g$ ，然后使用 DFS，判断是否存在从 $\textit{source}$ 到 $\textit{destination}$ 的路径。

过程中，我们用数组 $\textit{vis}$ 记录已经访问过的顶点，避免重复访问。

时间复杂度 $O(n + m)$ ，空间复杂度 $O(n + m)$ 。其中 $n$ 和 $m$ 分别是节点数和边数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

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)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2092 找出知晓秘密的所有专家 #2316 统计无向图中无法互相到达点对数 #2368 受限条件下可到达节点的数目