来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shortest-path-visiting-all-nodes
题目描述:
存在一个由 n 个节点组成的无向连通图，图中的节点按从 0 到 n - 1 编号。
给你一个数组 graph 表示这个图。其中，graph[i] 是一个列表，由所有与节点 i 直接相连的节点组成。
返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边。
示例 1：
输入：graph = [[1,2,3],[0],[0],[0]]
输出：4
解释：一种可能的路径为 [1,0,2,0,3]
示例 2：
输入：graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
输出：4
解释：一种可能的路径为 [0,1,4,2,3]
题目分析:
- 等权(权可以看作1)无向图求最短路径问题
- 可以从任意节点开始
- 节点可以重复访问
- 最多12个节点,1 <= n <= 12
思路分析:
因为n最大只有12，且是等权图求最短路径,很容易想到bfs+状态压缩点方法.
- 访问第 i 个点的状态(1表示已经访问过) : state = 1 & (i >>1)
- 更改第 i 个点状态为1 : mark = mark | (1 << i)
- 判断row个节点是否已经全部遍历:mark = 2^n - 1;
代码实现:
class Solution {
public int shortestPathLength(int[][] graph) {
int row = graph.length;
boolean[][] flag = new boolean[row][1 << row];
Queue<int[]> queue = new LinkedList();
for (int i = 0; i < row; i++) {
queue.offer(new int[]{i, 1 << i, 0}); // 可以任意起点，将所有节点初始化到queue.
flag[i][1 << i] = true;
}
while (!queue.isEmpty()) {
int[] temp = queue.poll();
int node = temp[0]; // 当前节点
int mark = temp[1]; // 当前节点状态
int result = temp[2]; // 当前走过的路径(权值和)
if (mark == (1 << row) - 1) return result; // 节点已经全部遍历.
for (int num : graph[node]) {
int nextMark = mark | (1 << num); // 修改num节点点状态
if (!flag[num][nextMark]) {
queue.offer(new int[]{num, nextMark, result + 1}); // 扩展下一轮节点.
flag[num][nextMark] = true; // 标记已经访问的节点.
}
}
}
return 0;
}
}
