LeetCode 847. 访问所有节点的最短路径

2021-10-10 HGNULB 约 10 分钟

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

分类

题目描述

✅ 847. 访问所有节点的最短路径

题意分析

给一张无向连通图，用邻接表 graph 描述，graph[i] 是节点 $i$ 的邻居列表。要找一条最短的行走路线，使得每个节点都至少被经过一次，返回这条路线的边数。

题面里有三处松绑，每一处都在改变问题的性质。第一，起点任选、终点任选，所以这不是单源问题。第二，节点可以重复访问，边也可以重复走，所以这不是哈密顿路径。第三，图保证连通，所以一定有解，不需要考虑返回 $-1$。

「可以重复访问」是最关键的一条。它意味着单纯记录「我现在在哪个节点」是不够的——同一个节点可以在不同时刻、带着不同的「已访问集合」被经过，这两次到访的后续代价完全不同。所以位置本身不构成完整的状态。

反过来，「已访问过哪些节点」是需要记住的，因为终止条件正是「集合等于全集」。而具体的访问顺序不需要记，因为后续能走哪里只取决于当前站在哪、还缺哪些，跟怎么走到这一步无关。

规模给了决定性的暗示：$n \le 12$。$2^{12} = 4096$，乘上 12 个节点也不过五万个状态。这个数字几乎是在直说「把子集编码进状态里」。

边界上，$n = 1$ 时起点自身就已经覆盖全集，答案是 $0$，不能因为「一步都没走」而误判。

解法：状态 BFS

核心思路

先看朴素想法。既然要经过所有点，能不能枚举访问顺序，也就是全排列？$12!$ 约等于 $4.8 \times 10^8$，还得对每一对相邻节点求最短路，代价太高；更麻烦的是，最优路线可能在同一个节点上来回穿插，「访问顺序」这个概念本身就不足以刻画一条允许重复的行走。

那就退回到最短路的框架里想。普通最短路的状态是「当前在哪个节点」，用 BFS 一层层扩展。这里为什么不行？因为终止条件不是「到达某个节点」，而是「覆盖了所有节点」，而覆盖情况是路径的历史信息，普通 BFS 的状态里没有它。

瓶颈定位清楚了：状态维度不足。补上它——把状态定义为二元组 $(u, S)$，含义是「当前站在节点 $u$，历史上已经访问过的节点集合恰好是 $S$」，其中 $S$ 是一个 $n$ 位的二进制掩码，第 $i$ 位为 1 表示节点 $i$ 已被访问。状态总数是 $n \cdot 2^n$，$n = 12$ 时不到五万，完全可控。

状态之间的转移很自然：从 $(u, S)$ 出发，沿一条边走到邻居 $v$，就到达 $(v, S \mid 2^v)$，代价为 1 步。所有转移代价相同，所以求最短步数用 BFS 就够，不需要 Dijkstra。

起点任选这一条，用多源 BFS 处理：对每个节点 $i$，把 $(i, 2^i)$ 都作为起点压进初始队列，距离设为 $0$。这等价于在原状态图外面挂一个虚拟超级源点，向所有这些起点连零权边；由于它们全都在第 0 层，BFS 的层序性质不受破坏。

于是不变量是标准的 BFS 不变量：队列中的状态按距离非递减排列，且任何状态第一次被写入 dist 时，写入的值就是它到某个起点的最短距离。终止条件是弹出的状态满足 $S = 2^n - 1$，此刻的距离就是答案；因为 BFS 按层推进，第一个被弹出的全集状态一定对应最短的那条路线。

解题步骤

计算全集掩码 full = (1 << n) - 1，开一个 $n \times 2^n$ 的距离表，全部初始化为 $-1$ 表示未访问。为什么用二维表而不是一维 visited：同一个节点带着不同的已访问集合是不同的状态，只按节点去重会把大量合法路径误杀。

对每个节点 $i$，把状态 $(i, 1 \ll i)$ 的距离设为 $0$ 并压入队列。为什么所有起点同层入队：题目允许从任意节点出发，多源 BFS 一次就能覆盖全部选择，比枚举起点跑 $n$ 次 BFS 快 $n$ 倍。

循环弹出队首状态 $(u, S)$。先检查 $S$ 是否等于 full，是则直接返回该状态的距离。为什么在出队时检查而不是入队时：出队顺序严格按距离非递减，第一个被弹出的全集状态一定是最优的；不过入队时检查也正确且更早返回，两者都可接受，关键是不能只在扩展完所有邻居后才检查。

遍历 $u$ 的每个邻居 $v$，算出新掩码 nextMask = S | (1 << v)。若 dist[v][nextMask] 仍为 $-1$，就把它设成当前距离加一并入队。为什么用 v 而不是循环下标去移位：掩码的第几位由邻居的编号决定，用错变量会把访问标记打到别的节点头上。

为什么距离要在入队时赋值而不是出队时：一个状态可能被多个前驱同时发现，出队时才标记会让它重复入队，队列规模从 $O(n2^n)$ 膨胀，虽然答案仍对但会超时。

图保证连通，所以循环一定会在某一刻命中全集状态；末尾的返回 $-1$ 只是形式上的兜底。

以 graph = [[1,2,3],[0],[0],[0]] 走一遍：这是一张星形图，节点 0 是中心，1、2、3 是叶子，full = 0b1111。初始队列里有四个状态：$(0, 0001)$、$(1, 0010)$、$(2, 0100)$、$(3, 1000)$，距离都是 0。

距离 0 层：弹出 $(0,0001)$，掩码不是全集，扩展出 $(1, 0011)$、$(2, 0101)$、$(3, 1001)$，距离 1。弹出 $(1,0010)$，唯一邻居是 0，扩展出 $(0, 0011)$，距离 1。同理 $(2,0100)$ 扩展出 $(0,0101)$，$(3,1000)$ 扩展出 $(0,1001)$。

距离 1 层：$(1,0011)$、$(2,0101)$、$(3,1001)$ 的邻居都只有 0，分别指向 $(0,0011)$、$(0,0101)$、$(0,1001)$，这三个状态已被标记过，不再入队。$(0,0011)$ 扩展出 $(2, 0111)$ 和 $(3, 1011)$，距离 2；$(0,0101)$ 扩展出 $(1, 0111)$ 和 $(3, 1101)$，距离 2；$(0,1001)$ 扩展出 $(1, 1011)$ 和 $(2, 1101)$，距离 2。

距离 2 层：这六个状态当前都停在叶子上，唯一出边回到中心，于是产生 $(0, 0111)$、$(0, 1011)$、$(0, 1101)$，距离 3。

距离 3 层：弹出 $(0,0111)$，掩码缺第 3 位，扩展到邻居 3 得到 $(3, 1111)$，距离 4；另两个状态同理各补上自己缺的那一位，也得到距离 4 的全集状态。

距离 4 层：弹出 $(3, 1111)$，掩码等于 full，返回 $4$。对应的实际路线是 $1 \to 0 \to 2 \to 0 \to 3$，恰好 4 条边。注意如果强行从节点 0 出发，最优也要 $0 \to 1 \to 0 \to 2 \to 0 \to 3$ 共 5 步，这正是「起点必须任选」的价值所在。

代码实现

// 以所有节点为起点做多源 广度优先搜索，首次到达全 1 mask 即为最短路径。
class Solution {
    public int shortestPathLength(int[][] graph) {
        int n = graph.length;
        int full = (1 << n) - 1;
        int[][] dist = new int[n][1 << n];
        Queue<int[]> queue = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            for (int mask = 0; mask < (1 << n); mask++) {
                dist[i][mask] = -1;
            }
        }

        for (int i = 0; i < n; i++) {
            int mask = 1 << i;
            dist[i][mask] = 0;
            queue.offer(new int[]{i, mask});
        }

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int node = cur[0];
            int mask = cur[1];

            if (mask == full) {
                return dist[node][mask];
            }

            for (int nei : graph[node]) {
                int nextMask = mask | (1 << nei);
                if (dist[nei][nextMask] == -1) {
                    dist[nei][nextMask] = dist[node][mask] + 1;
                    queue.offer(new int[]{nei, nextMask});
                }
            }
        }

        return -1;
    }
}

// 以所有节点为起点做多源 广度优先搜索，首次到达全 1 mask 即为最短路径。
func shortestPathLength(graph [][]int) int {
    n := len(graph)
    full := (1 << n) - 1

    dist := make([][]int, n)
    for i := 0; i < n; i++ {
        dist[i] = make([]int, 1<<n)
        for j := 0; j < (1 << n); j++ {
            dist[i][j] = -1
        }
    }

    queue := make([][2]int, 0)
    for i := 0; i < n; i++ {
        mask := 1 << i
        dist[i][mask] = 0
        queue = append(queue, [2]int{i, mask})
    }

    for head := 0; head < len(queue); head++ {
        node := queue[head][0]
        mask := queue[head][1]
        if mask == full {
            return dist[node][mask]
        }

        for _, nei := range graph[node] {
            nextMask := mask | (1 << nei)
            if dist[nei][nextMask] == -1 {
                dist[nei][nextMask] = dist[node][mask] + 1
                queue = append(queue, [2]int{nei, nextMask})
            }
        }
    }

    return -1
}

复杂度分析

时间复杂度：$O(2^n \cdot n^2)$，其中 $n$ 是节点数。状态共 $n \cdot 2^n$ 个，每个状态至多入队一次；从状态 $(u, S)$ 扩展的代价是 $u$ 的度数，把所有节点的度数加起来是 $2 E = O(n^2)$，因此每个掩码对应的一整轮扩展是 $O(n^2)$，乘上 $2^n$ 个掩码即得上界。$n \le 12$ 时实际运算量在百万级以内。

空间复杂度：$O(n \cdot 2^n)$，距离表就有这么多格子，队列在最坏情况下也可能同时容纳同一数量级的状态，两者同阶。

关键点总结

当终止条件依赖「历史上做过什么」而不只是「现在在哪里」时，说明状态维度不够，需要把历史信息压进状态。子集用二进制掩码编码是最常见的做法，代价是状态数乘以 $2^n$，所以只在 $n \le 20$ 左右时可行。

看到 $n \le 12$、$n \le 15$、$n \le 20$ 这类小得反常的上界，几乎可以直接判定是状态压缩题。这是最可靠的题型识别信号之一。

「起点任选」用多源 BFS 处理，把所有候选起点在第 0 层一次性入队，等价于挂一个虚拟超级源。这比枚举起点跑 $n$ 遍 BFS 干净得多。

边权全为 1 时 BFS 就是最短路，不必上 Dijkstra；反过来，如果这题给边加了不同权重，状态定义不变，但搜索框架要换成优先队列。

访问标记必须在入队时打上。出队时才标记不会让答案出错，但会让同一状态被重复入队，队列规模和运行时间都会显著恶化。

面试视角：这题的得分点在于能否说清「为什么节点编号不足以作为状态」。举一个具体的例子——同一个中心节点被经过两次，两次身上背的已访问集合不同，后续代价也不同——比抽象地说「要记历史」更有说服力。

易错点总结

错误写法：只从节点 0 单源 BFS。用例 graph = [[1,2,3],[0],[0],[0]] 从中心出发最少要走 5 步，而从任一叶子出发只需 4 步，答案会偏大。

错误写法：访问标记用一维的 visited[node]。节点 0 在这个用例里必须被经过三次，一维标记会在第一次访问后就封死它，搜索永远到不了全集状态，最终返回 $-1$。

错误写法：全集掩码写成 1 << n 而不是 (1 << n) - 1。这个值的第 $n$ 位为 1、低 $n$ 位全为 0，任何合法状态都不可能等于它，循环会跑空并返回 $-1$。

错误写法：起点状态的掩码写成 $0$ 而不是 $1 \ll i$。站在节点 $i$ 上却不把它记为已访问，会导致每个节点都要被「再走到一次」才算数，用例的答案会变成 5。

错误写法：起点距离初始化为 1。所有状态的距离整体偏移，用例会返回 5。

错误写法：距离在出队时才写入 dist。同一状态会被多个前驱重复入队，$n = 12$ 的稠密图上队列规模成倍膨胀，容易超时。

错误写法：位移时用循环下标而不是邻居编号，写成 mask | (1 << i)。标记打在了错误的节点上，掩码含义彻底混乱，答案随机偏小或偏大。

错误写法：用带记忆化的 DFS 求最短步数。状态转移图有环（节点可以来回走），记忆化会在环上取到尚未收敛的中间值，结果不是最短距离。

错误写法：距离表按 dist[mask][node] 分配却按 dist[node][mask] 访问。$n = 12$ 时第一维只有 12 而掩码能到 4095，第一次访问就越界。

错误写法：忘记 $n = 1$ 的情形，先把状态 $(0, 0)$ 入队再要求走一步才算访问。正确答案是 $0$，这么写会返回 1 或陷入无法终止的搜索。

相似题目

题目	难度	考察点
1129. 颜色交替的最短路径	中等	同样往状态里多加一维（上一条边的颜色）来补足信息，但附加维度只有两种取值，是状态扩维最轻量的入门形态
1494. 并行课程 II	困难	同为子集状压，但用的是动态规划而非 BFS，需要枚举掩码的子集来决定这一学期修哪些课
752. 打开转盘锁	中等	同为隐式图上的 BFS 最短步数，状态是四位数字串而非「位置 + 集合」，难点在于把死亡列表转成访问标记