LeetCode 面试题 04.01. 节点间通路

2022-07-06 HGNULB 约 9 分钟

文章信息 7 个分类 3 个标签

分类

LeetCode CodeTop 中等未解决 1-2 虾皮程序员面试金典（第 6 版）

题目描述

✅ 面试题 04.01. 节点间通路

题意分析

给定一个 n 个节点的有向图（节点编号 0..n-1）和边列表 graph，其中 graph[i] = [u, v] 表示存在一条 u → v 的有向边，判断从 start 出发能否沿着有向边走到 target。只要回答"能/不能"，不需要给出路径，也不需要最短路径。

约束里有三个必须读出来的信号。第一，边是有向的，所以建图时只能加 u → v 一个方向，把它当无向图处理会把不可达误判成可达。第二，题目明确说明图中可能存在自环和平行边，自环意味着搜索必须有访问标记否则会死循环，平行边意味着同一对节点可能被重复加入邻接表（这不影响正确性，只影响常数）。第三，边数可能远大于节点数，因此不能用邻接矩阵（$O(n^2)$ 空间在 n 较大时不可接受），要用邻接表。

边界上要覆盖：start == target（应当返回 true，即使没有任何边）；target 是孤立点；从 start 出发能走很远但绕不到 target；图中有环导致的重复访问。

解法：BFS（邻接表）

核心思路

暴力想法是枚举所有从 start 出发的路径，看有没有一条终点是 target。瓶颈非常明显：路径数量随图的规模指数增长，而且一旦图里有环，枚举根本不会终止。

观察到的关键点是：这题问的是可达性，而可达性只和"节点集合"有关，与走法无关。如果某个节点 x 已经被证明"从 start 可达"，那么从 x 继续往外走能到的所有节点，无论沿哪条路径抵达 x，结论都一样。所以完全没必要区分不同路径——每个节点只需要被处理一次。这就把"枚举路径"降维成"遍历节点"，规模从指数直接压到 $O(V + E)$。

由此定义状态与不变量：用 visited[] 标记"已经确认从 start 可达且已经（或即将）展开其出边"的节点，用队列 queue 存放"已确认可达但出边还没展开"的节点。不变量是：visited 为真的节点集合，恒等于"从 start 可达且已被发现"的集合；队列中的节点是这个集合里尚未展开的部分。每次从队首取出一个节点展开它的出边，把新发现的节点标记并入队，这个不变量就被保持。

队列空时，意味着所有从 start 可达的节点都已经被发现并展开过，如果其间没有碰到 target，就可以断言不可达。这里选 BFS 而不是 DFS 有个实际好处：递归 DFS 在链状图上会把栈压到 n 层，n 大时有爆栈风险，BFS 用显式队列不存在这个问题；当然改写成显式栈的迭代 DFS 也同样安全，两者在本题的复杂度完全一致。

解题步骤

先把边列表转成邻接表 adj。原始输入是散落的边，每次要找"某个节点的所有出边"都得扫一遍整个 graph，那是 $O(E)$ 一次、总共 $O(VE)$。建一次邻接表是 $O(E)$，之后每次取邻居都是 $O(1)$，这是把重复查询的代价一次性付清。建表时只写 adj[e[0]].add(e[1])，不写反向，因为边是有向的。

初始化 visited 数组、队列，把 start 入队并立刻标记为已访问。标记必须在入队时完成，而不是出队时。若留到出队才标记，同一个节点可能被多个前驱同时推进队列，导致重复展开；在有大量平行边或稠密图时，队列规模会成倍膨胀。

循环取出队首节点，先判断它是不是 target。把判断放在出队时而不是入队时，可以让 start == target 这个边界自然成立——start 一入队就会被取出并命中，不需要在函数开头额外写一条特判。

遍历该节点的所有出边，未访问过的邻居标记并入队。visited 检查同时承担了两件事：防止环导致的死循环，以及避免同一节点被重复展开。缺了它，只要图里有环，队列就永远不会空。

队列耗尽仍未命中 target，返回 false。此时不变量保证"可达集合已经被完整枚举"，所以这个否定结论是可靠的。

以 n = 5，graph = [[0,1],[0,2],[1,2],[1,3],[2,3],[3,4]]，start = 0，target = 4 走一遍：

建表得到 adj[0] = [1, 2]，adj[1] = [2, 3]，adj[2] = [3]，adj[3] = [4]，adj[4] = []。

初始化：queue = [0]，visited = [T, F, F, F, F]。

第 1 轮：出队 0，不是 4；邻居 1 未访问 → 标记入队；邻居 2 未访问 → 标记入队。此时 queue = [1, 2]，visited = [T, T, T, F, F]。

第 2 轮：出队 1，不是 4；邻居 2 已访问跳过（这一步正是标记生效的地方，否则 2 会被展开两次）；邻居 3 未访问 → 标记入队。queue = [2, 3]，visited = [T, T, T, T, F]。

第 3 轮：出队 2，不是 4；邻居 3 已访问跳过。queue = [3]。

第 4 轮：出队 3，不是 4；邻居 4 未访问 → 标记入队。queue = [4]。

第 5 轮：出队 4，等于 target，立刻返回 true。

再看反例 start = 4, target = 0：adj[4] 为空，第一轮出队 4 不等于 0，没有邻居可扩展，队列变空，返回 false——正确，因为边是有向的，从 4 出发无路可走。如果建图时误加了反向边，这里会错误地返回 true。

代码实现

class Solution {
    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        List<Integer>[] adj = new List[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] e : graph) {
            adj[e[0]].add(e[1]);
        }

        boolean[] visited = new boolean[n];
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int node = queue.poll();
            if (node == target) {
                return true;
            }
            for (int next : adj[node]) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.offer(next);
                }
            }
        }
        return false;
    }
}

func findWhetherExistsPath(n int, graph [][]int, start int, target int) bool {
    adj := make([][]int, n)
    for _, e := range graph {
        adj[e[0]] = append(adj[e[0]], e[1])
    }

    visited := make([]bool, n)
    queue := []int{start}
    visited[start] = true

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        if node == target {
            return true
        }
        for _, next := range adj[node] {
            if !visited[next] {
                visited[next] = true
                queue = append(queue, next)
            }
        }
    }
    return false
}

复杂度分析

时间复杂度：$O(V + E)$，V = n 为节点数，E 为边数。建邻接表遍历一次边列表是 $O(E)$；BFS 阶段每个节点最多入队出队一次（靠 visited 保证），每条出边最多被检查一次，合计 $O(V + E)$。

空间复杂度：$O(V + E)$。邻接表存下了全部边是 $O(E)$，visited 数组是 $O(V)$，队列最坏同时容纳所有节点也是 $O(V)$。

关键点总结

"问可达性"就把路径枚举降维成节点遍历。只要答案只关心"能不能到"而不关心"怎么到"，每个节点就只需处理一次，指数级的路径搜索立刻塌缩成线性的图遍历。反过来，一旦题目要求列出所有路径（如 797），visited 就必须改成沿路径回溯的形式。

访问标记要在入队/入栈的瞬间打上，而不是出队时。这是 BFS 最经典的性能陷阱：延后标记不会导致答案错误，但会让同一节点被重复推进队列，稠密图上队列规模成倍膨胀。

边的方向必须逐字对齐题面。有向图只加单向边，无向图要加两条。这一处写错既不会报错也不会死循环，只会静默地给出错误答案，是图论题里最难自查的 bug。

散落的边列表先转邻接表，是所有图论题的固定前置动作。它把"查某点的邻居"从 $O(E)$ 降到 $O(deg)$，一次 $O(E)$ 的预处理换来后续全部查询的常数复杂度。

面试视角：主动说明为什么选 BFS 而不是递归 DFS。两者复杂度相同，但递归深度在链状图上会达到 $O(n)$ 有爆栈风险；同时可以补一句"如果这题改成无向图的静态多次查询，并查集会更合适，预处理后单次查询接近 $O(1)$"，展示对不同工具适用边界的判断。

易错点总结

错误写法：建图时同时写 adj[e[0]].add(e[1]) 和 adj[e[1]].add(e[0]) → 用例 n = 2，graph = [[0,1]]，start = 1，target = 0：正确答案是 false（只有 0→1 的边），加了反向边后返回 true。

错误写法：不用 visited 数组 → 用例 n = 2，graph = [[0,1],[1,0]]，start = 0，target = 3 这类目标不可达的环图：0 和 1 互相入队，队列永远不空，程序死循环直到超时。

错误写法：visited[next] = true 挪到出队之后再标记 → 用例 n = 3，graph = [[0,1],[0,1],[0,2],[1,2]]（含平行边）：1 会因为两条平行边被入队两次、2 被入队两次，队列长度翻倍；在稠密图上这会退化成指数级入队，实测直接 TLE。

错误写法：把 node == target 的判断放在入队时而不是出队时，同时删掉起点的特判 → 用例 n = 1，graph = []，start = 0，target = 0：start 从未作为"邻居"被入队，判断逻辑一次也没触发，返回 false，正确答案是 true。

错误写法：函数开头写 if (graph.length == 0) return false; → 用例 n = 1，graph = []，start = 0，target = 0：边集为空但起点等于终点，正确答案是 true，这条特判把它误判成 false。

错误写法：用 int[][] adj = new int[n][n] 邻接矩阵建图 → 用例 n = 10^5：矩阵需要 $10^{10}$ 个格子，直接 OutOfMemoryError。节点多而边稀疏时必须用邻接表。

错误写法：Java 里 List<Integer>[] adj = new List[n]; 之后忘记逐个 new ArrayList<>() → 用例任意输入：adj[i] 全是 null，第一次 adj[e[0]].add(...) 就抛 NPE。数组的元素默认是 null，必须显式初始化每一格。

错误写法：Go 里 queue = queue[1:] 之后又用 queue[0] 取值 → 用例 n = 1，graph = []，start = 0，target = 1：出队后队列为空，再取 queue[0] 越界 panic。必须先取值再截断。

错误写法：改写成递归 DFS 时把 visited[node] = true 写在递归返回后（回溯式撤销标记） → 用例是一张有多条路径通向同一节点的稠密图：撤销标记会让同一节点沿不同路径被反复访问，复杂度退化成指数级。判可达性时标记只能设不能撤；只有枚举所有路径时才需要回溯撤销。

错误写法：把 start、target 当成 1-based 编号，访问时写 visited[start - 1] → 用例 n = 2，graph = [[0,1]]，start = 0：下标 -1 越界抛异常。题目节点编号从 0 开始，不需要任何偏移。

相似题目

题目	难度	考察点
797. 所有可能的路径	中等	要输出全部路径而非可达性，`visited` 必须改成回溯式撤销
323. 无向图中连通分量的数目	中等	无向图要加双向边，且需对每个未访问点起一轮遍历来计数
547. 省份数量	中等	输入是邻接矩阵而非边列表，更适合直接上并查集做连通性合并
133. 克隆图	中等	遍历的同时要建新节点，`visited` 升级成"原节点 → 新节点"的映射
207. 课程表	中等	判的是有向图是否有环，需要入度统计或三色标记而非单纯可达性
1129. 颜色交替的最短路径	中等	状态要扩展成"节点 + 上一条边颜色"，访问标记随之变成二维