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

题目描述：

存在一个由 n 个节点组成的无向连通图，节点编号从 0 到 n - 1。给你一个数组 graph 表示这个图，其中 graph[i] 是一个列表，由与节点 i 直接相连的所有节点组成。

你需要找到能够访问所有节点的最短路径的长度。路径可以从任意节点开始和结束，也可以重复访问节点多次，并且每条边也可以重复经过多次。

要求返回访问所有节点的最短路径的长度。其中 n 的范围是 1 <= n <= 12。

示例：

输入：graph = [[1,2,3],[0],[0],[0]]
输出：4
解释：一种可能的路径为 [1,0,2,0,3]

解题过程循序渐进讲解：

步骤1：问题理解与难点分析

• 这是一个在无向连通图中寻找最短路径的问题，但目标不是从一点到另一点，而是要访问所有节点。
• 关键约束：节点可以重复访问，边可以重复经过。这意味着单纯的最短路算法（如BFS）不能直接套用，因为BFS通常假设每个节点只访问一次。
• 节点数 n <= 12 很小，提示我们可以用状态压缩的技巧来表示“已经访问过哪些节点”。
• 这本质上是一个最短路径问题，但状态不是单一的节点，而是“当前位于哪个节点” + “已经访问过的节点集合”。

步骤2：状态定义

• 因为需要记录访问过的节点集合，且 n ≤ 12，我们可以用一个二进制位掩码（bitmask）表示集合。
• 例如，mask = 1011（二进制）表示节点 0、1、3 已经访问过（从低位到高位对应节点 0,1,2,...）。
• 定义状态 (u, mask)：
  • u：当前所在节点编号（0 ≤ u < n）
  • mask：已经访问过的节点集合（二进制掩码）
• 初始状态：可以从任意节点开始，那么对于每个节点 i，初始状态是 (i, 1 << i)，表示从 i 出发，且已访问过 i。
• 目标状态：对于任意节点 u，当 mask == (1 << n) - 1 时，表示所有 n 个节点都已访问过。

步骤3：搜索方法选择

• 由于我们要求最短路径长度（即经过的边数最少），且图是无权图（每条边权为1），我们可以使用BFS（广度优先搜索）。
• BFS保证当我们第一次到达目标状态时，走过的步数就是最短的。
• 每个状态 (u, mask) 相当于图中的一个“超级节点”，状态之间的转移就是：从当前节点 u 走到它的邻居 v，并且更新访问集合（将 v 加入 mask）。

步骤4：BFS状态转移

• 队列中存储 (u, mask) 以及当前步数 dist。
• 从队列取出 (u, mask) 后，遍历 u 的所有邻居节点 v：
  • 新 mask' = mask | (1 << v) （将 v 加入已访问集合）
  • 新状态 (v, mask')
• 如果 mask' 已经等于全 1（即访问所有节点），则返回当前步数 +1。
• 如果 (v, mask') 这个状态之前没有访问过，就加入队列。

步骤5：去重与访问记录

• 我们需要记录哪些 (u, mask) 已经访问过，避免重复入队。
• 因为 n ≤ 12，所以 mask 范围是 0 到 2^n - 1，可以用一个二维数组 visited[u][mask] 来标记是否访问过。
• 数组大小：n * (1 << n)，最大为 12 * 4096 = 49152，完全可以接受。

步骤6：算法步骤详细展开

1. 初始化队列 queue，初始化 visited[n][1<<n] 为 false。
2. 对于每个节点 i（0 ≤ i < n）：
   • 初始状态 (i, 1 << i)，步数 dist = 0。
   • 将 (i, 1<<i) 加入队列，并标记 visited[i][1<<i] = true。
3. 开始 BFS 循环：
   • 弹出队首 (u, mask, dist)。
   • 遍历 u 的每个邻居 v：
     • 计算新 mask' = mask | (1 << v)。
     • 如果 mask' == (1<<n)-1，说明所有节点都访问到了，返回 dist+1。
     • 如果 visited[v][mask'] 为 false，则标记为 true，并将 (v, mask', dist+1) 入队。
4. 如果 BFS 结束还没有返回，理论上无向连通图一定能访问所有节点，所以最终一定会返回。

步骤7：示例推导（以题目示例为例）

• graph = [[1,2,3],[0],[0],[0]], n=4。
• 初始：可以从节点0开始，状态 (0, 0001) 入队，步数0。
• 第一步：
  • 弹出 (0,0001,0)，邻居 1,2,3：
    • 到1：mask' = 0001 | 0010 = 0011，不是全1，入队 (1,0011,1)。
    • 到2：mask' = 0001 | 0100 = 0101，入队 (2,0101,1)。
    • 到3：mask' = 0001 | 1000 = 1001，入队 (3,1001,1)。
• 第二步：
  • 弹出 (1,0011,1)，邻居 0：
    • 到0：mask' = 0011 | 0001 = 0011（不变），visited[0][0011] 未访问过，入队 (0,0011,2)。
  • 弹出 (2,0101,1)，邻居 0：
    • 到0：mask' = 0101 | 0001 = 0101，入队 (0,0101,2)。
  • 弹出 (3,1001,1)，邻居 0：
    • 到0：mask' = 1001 | 0001 = 1001，入队 (0,1001,2)。
• 第三步：
  • 弹出 (0,0011,2)，邻居 1,2,3：
    • 到1：mask' = 0011 | 0010 = 0011，重复不入。
    • 到2：mask' = 0011 | 0100 = 0111，不是全1，入队 (2,0111,3)。
    • 到3：mask' = 0011 | 1000 = 1011，入队 (3,1011,3)。
  • 类似地，从 (0,0101,2) 会得到到1的新mask=0111，到3的新mask=1101等。
• 第四步：
  • 从状态 (2,0111,3) 到邻居0：mask' = 0111 | 0001 = 0111，重复不入。
  • 到其他邻居（这里2的邻居只有0）无新状态。
  • 从状态 (3,1011,3) 到邻居0：mask' = 1011 | 0001 = 1011，重复不入。
  • 从其他状态可能得到 mask=1110 等。
• 直到某一步，例如从状态 (u, 0111) 到 v=3：mask' = 0111 | 1000 = 1111（全1），此时步数为3+1=4，返回4。

步骤8：复杂度分析

• 状态总数：O(n * 2^n)
• 每个状态最多扩展 n 次（邻居数）
• 总时间复杂度：O(n^2 * 2^n)，n=12 时约为 144*4096 ≈ 5.9e5，可接受。
• 空间复杂度：O(n * 2^n) 用于 visited 和队列。

总结：
这道题是状态压缩 BFS 的经典应用。核心在于将“已访问节点集合”压缩为一个二进制数，与当前节点编号一起构成状态，然后用BFS求从任意初始状态到任意全1状态的最短路径。这种方法在 n 较小（≤20）的“访问所有节点”问题中非常有效。