算法题 访问所有节点的最短路径

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

问题描述

给你一个无向连通图，包含n个节点，编号从0到n-1。给你一个二维数组graph，其中graph[i]是与节点i相连的节点列表。

返回访问所有节点的最短路径长度。你可以从任意节点开始和结束，可以多次访问同一节点和边。

注意：

• 图是连通的（任意两个节点之间都有路径）
• 节点数1 <= n <= 12
• 可以重复访问节点和边

示例：

输入:graph=[[1,2,3],[0],[0],[0]]输出:4解释:一种最短路径是[1,0,2,0,3]

输入:graph=[[1],[0,2,4],[1,3,4],[2],[1,2]]输出:4解释:一种最短路径是[0,1,4,2,3]

算法思路

状态压缩BFS：

1. 核心：

   • 带状态的最短路径问题
   • 状态 = (当前节点, 已访问的节点集合)
   • 由于 n ≤ 12，可以用位掩码表示已访问的节点集合

2. 状态：

   • 使用整数mask表示已访问的节点集合
   • 第i位为1表示节点i已访问
   • 状态 =(node, mask)

3. BFS：

   • 从每个节点作为起点开始BFS
   • 队列存储(当前节点, 访问状态, 路径长度)
   • 目标状态：mask == (1 << n) - 1（所有节点都已访问）

4. 去重：

   • 使用visited[node][mask]避免重复访问相同状态
   • 求最短路径，第一次到达某个状态就是最优的

5. 为什么用BFS而不是DFS？
   BFS保证第一次到达目标状态时路径最短。

代码实现

importjava.util.*;classSolution{/** * 计算访问所有节点的最短路径长度 * 使用状态压缩BFS，状态 = (当前节点, 已访问节点的位掩码) * * @param graph 无向连通图的邻接表 * @return 访问所有节点的最短路径长度 */publicintshortestPathLength(int[][]graph){intn=graph.length;// 特殊情况：只有一个节点if(n==1){return0;}// 目标状态：所有n个节点都被访问inttargetMask=(1<<n)-1;// visited[node][mask] 表示是否已经访问过状态(node, mask)boolean[][]visited=newboolean[n][1<<n];// BFS队列：存储 [当前节点, 访问状态, 路径长度]Queue<int[]>queue=newLinkedList<>();// 初始化：从每个节点开始BFSfor(inti=0;i<n;i++){intstartMask=1<<i;// 只访问了节点iqueue.offer(newint[]{i,startMask,0});visited[i][startMask]=true;}// BFS搜索while(!queue.isEmpty()){int[]current=queue.poll();intnode=current[0];intmask=current[1];intdistance=current[2];// 遍历当前节点的所有邻居for(intneighbor:graph[node]){// 更新访问状态：将neighbor标记为已访问intnewMask=mask|(1<<neighbor);// 检查是否达到目标状态if(newMask==targetMask){returndistance+1;}// 如果状态未访问过，加入队列if(!visited[neighbor][newMask]){visited[neighbor][newMask]=true;queue.offer(newint[]{neighbor,newMask,distance+1});}}}return-1;}}

算法分析

• 时间复杂度：O(n² × 2ⁿ)
  • 状态数量：n个节点 × 2ⁿ种访问状态 = O(n × 2ⁿ)
  • 每个状态需要遍历其所有邻居，最多n个邻居
  • 总体：O(n² × 2ⁿ)
• 空间复杂度：O(n × 2ⁿ)
  • visited数组大小：n × 2ⁿ
  • BFS队列最多存储 O(n × 2ⁿ) 个状态

算法过程

1：graph = [[1,2,3],[0],[0],[0]]

图结构：

1 | 0 / \ 2 3

BFS：

1. 初始状态（距离0）：

   • (0, 0001),(1, 0010),(2, 0100),(3, 1000)

2. 距离1：

   • 从0:(1, 0011),(2, 0101),(3, 1001)
   • 从1:(0, 0011)
   • 从2:(0, 0101)
   • 从3:(0, 1001)

3. 距离2：

   • 从(1,0011):(0,0011)（已访问）
   • 从(2,0101):(0,0101)（已访问）
   • 从(3,1001):(0,1001)（已访问）
   • 从(0,0011):(2,0111),(3,1011)
   • 从(0,0101):(1,0111),(3,1101)
   • 从(0,1001):(1,1011),(2,1101)

4. 距离3：

   • 从(2,0111):(0,0111)（已访问）
   • 从(3,1011):(0,1011)（已访问）
   • 从(1,0111):(0,0111)（已访问）
   • 从(3,1101):(0,1101)（已访问）
   • 从(1,1011):(0,1011)（已访问）
   • 从(2,1101):(0,1101)（已访问）

5. 距离4：

   • 从(0,0111):(3,1111)→目标状态！返回4
   • 从(0,1011):(2,1111)→目标状态！返回4
   • 从(0,1101):(1,1111)→目标状态！返回4

结果：4

测试用例

publicclassMain{publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：星形图int[][]graph1={{1,2,3},{0},{0},{0}};System.out.println("Test 1: "+solution.shortestPathLength(graph1));// 4// 测试用例2：复杂图int[][]graph2={{1},{0,2,4},{1,3,4},{2},{1,2}};System.out.println("Test 2: "+solution.shortestPathLength(graph2));// 4// 测试用例3：两个节点int[][]graph3={{1},{0}};System.out.println("Test 3: "+solution.shortestPathLength(graph3));// 1// 测试用例4：三个节点线性int[][]graph4={{1},{0,2},{1}};System.out.println("Test 4: "+solution.shortestPathLength(graph4));// 2// 测试用例5：完全图（3个节点）int[][]graph5={{1,2},{0,2},{0,1}};System.out.println("Test 5: "+solution.shortestPathLength(graph5));// 2// 测试用例6：单节点int[][]graph6={{}};System.out.println("Test 6: "+solution.shortestPathLength(graph6));// 0// 测试用例7：四个节点环int[][]graph7={{1,3},{0,2},{1,3},{0,2}};System.out.println("Test 7: "+solution.shortestPathLength(graph7));// 3// 测试用例8：链状图（4个节点）int[][]graph8={{1},{0,2},{1,3},{2}};System.out.println("Test 8: "+solution.shortestPathLength(graph8));// 3// 测试用例9：复杂连通图int[][]graph9={{1,2,3,4},{0,2,3,4},{0,1,3,4},{0,1,2,4},{0,1,2,3}};System.out.println("Test 9: "+solution.shortestPathLength(graph9));// 2}}

关键点

1. 状态压缩：

   • 用位掩码表示集合处理"访问过哪些节点"问题

2. 多源BFS：

   • 可以从任意节点开始，需要将所有节点作为起点

3. 状态去重：

   • 同一状态(node, mask)只需要访问一次
   • 重复访问不会产生更短的路径

常见问题

1. 为什么不用Dijkstra算法？
   所有边的权重都是1，BFS就是最短路径算法。Dijkstra适用于带权重的图。