这是一个经典的图遍历问题，要求找到一条访问所有节点的最短路径（路径长度按边数计算，节点可重复访问）。由于节点数不超过 12，可以使用 状态压缩 + BFS 高效求解。

算法思路

· 状态定义：(当前节点 u, 已访问节点集合 mask)，其中 mask 是一个整数的二进制位表示哪些节点已经被访问过（第 i 位为 1 表示节点 i 已访问）。
· BFS 过程：

1. 初始时，可以从任意节点出发，因此将所有节点 i 对应的状态 (i, 1<<i) 加入队列，距离为 0。
2. 进行广度优先搜索，每一步从队列中取出一个状态，如果其 mask 等于 (1<<n)-1（所有节点都已访问），则当前距离就是最短路径长度。
3. 否则，遍历当前节点 u 的所有邻居 v，生成新状态 (v, mask | (1<<v))。如果该状态未被访问过，则加入队列，距离加 1。
   · 正确性：BFS 保证第一次到达目标状态时路径最短（每条边权为 1）。
   · 复杂度：状态总数为 n * 2^n，每个状态扩展邻居最多 n 次，时间复杂度 O(n^2 * 2^n)，空间复杂度 O(n * 2^n)，对于 n ≤ 12 完全可行。

Java 实现

import java.util.*;

class Solution {
    public int shortestPathLength(int[][] graph) {
        int n = graph.length;
        if (n == 1) return 0; // 只有一个节点，不需要移动

        int targetMask = (1 << n) - 1; // 所有节点都已访问的掩码
        boolean[][] visited = new boolean[n][1 << n];
        Queue<int[]> queue = new LinkedList<>(); // 队列元素：[node, mask]

        // 初始状态：从每个节点出发，已访问自身
        for (int i = 0; i < n; i++) {
            int mask = 1 << i;
            queue.offer(new int[]{i, mask});
            visited[i][mask] = true;
        }

        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            // 逐层遍历
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                int node = cur[0];
                int mask = cur[1];

                if (mask == targetMask) {
                    return steps;
                }

                for (int neighbor : graph[node]) {
                    int newMask = mask | (1 << neighbor);
                    if (!visited[neighbor][newMask]) {
                        visited[neighbor][newMask] = true;
                        queue.offer(new int[]{neighbor, newMask});
                    }
                }
            }
            steps++; // 每层遍历完步数加 1
        }

        return -1; // 理论上不会执行到这里
    }
}

关键点说明

· visited 数组：visited[node][mask] 用于防止重复访问同一状态，避免无限循环。
· 队列初始多源：从所有节点出发，因为不知道从哪个节点开始路径最短。
· BFS 层数：steps 记录当前已经走过的边数。当某一层中出现目标状态时，steps 即为答案。

示例验证

以题目示例 graph = [[1,2,3],[0],[0],[0]] 为例：

· n = 4，目标掩码为 1111（二进制 15）。
· BFS 会找到一条最短路径长度为 3，例如 0 → 1 → 0 → 2 → 0 → 3 实际上边数为 6？需要再确认。但根据题目示例，答案为 4？让我们回忆 LeetCode 847 示例：
· 输入：[[1,2,3],[0],[0],[0]]，输出应为 4。因为路径 1→0→2→0→3 需要 4 条边（1-0, 0-2, 2-0, 0-3）。我们的 BFS 会正确计算出 4。
· 算法能够正确求解。

其他解法

也可先用 Floyd-Warshall 求出所有点对最短距离，再用动态规划 dp[mask][last] 求解，但 BFS 更直观且适合本题的无权图。