來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/shortest-path-visiting-all-nodes
題目描述:
存在一個由 n 個節(jié)點組成的無向連通圖答倡，圖中的節(jié)點按從 0 到 n - 1 編號使鹅。
給你一個數(shù)組 graph 表示這個圖。其中，graph[i] 是一個列表含思，由所有與節(jié)點 i 直接相連的節(jié)點組成。
返回能夠訪問所有節(jié)點的最短路徑的長度纱意。你可以在任一節(jié)點開始和停止俐东，也可以多次重訪節(jié)點，并且可以重用邊痘系。
示例 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]
題目分析:
- 等權(quán)(權(quán)可以看作1)無向圖求最短路徑問題
- 可以從任意節(jié)點開始
- 節(jié)點可以重復(fù)訪問
- 最多12個節(jié)點,1 <= n <= 12
思路分析:
因為n最大只有12菲嘴，且是等權(quán)圖求最短路徑,很容易想到bfs+狀態(tài)壓縮點方法.
- 訪問第 i 個點的狀態(tài)(1表示已經(jīng)訪問過) : state = 1 & (i >>1)
- 更改第 i 個點狀態(tài)為1 : mark = mark | (1 << i)
- 判斷row個節(jié)點是否已經(jīng)全部遍歷:mark = 2^n - 1;
代碼實現(xiàn):
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}); // 可以任意起點，將所有節(jié)點初始化到queue.
flag[i][1 << i] = true;
}
while (!queue.isEmpty()) {
int[] temp = queue.poll();
int node = temp[0]; // 當(dāng)前節(jié)點
int mark = temp[1]; // 當(dāng)前節(jié)點狀態(tài)
int result = temp[2]; // 當(dāng)前走過的路徑(權(quán)值和)
if (mark == (1 << row) - 1) return result; // 節(jié)點已經(jīng)全部遍歷.
for (int num : graph[node]) {
int nextMark = mark | (1 << num); // 修改num節(jié)點點狀態(tài)
if (!flag[num][nextMark]) {
queue.offer(new int[]{num, nextMark, result + 1}); // 擴展下一輪節(jié)點.
flag[num][nextMark] = true; // 標(biāo)記已經(jīng)訪問的節(jié)點.
}
}
}
return 0;
}
}
