LeetCode 847. 访问所有节点的最短路径【困难】 BFS加状态压缩

╰半橙微兮° 2022-09-03 12:10 113阅读 0赞

**题目链接：** 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]
    
    提示：
    n == graph.length
    1 <= n <= 12
    0 <= graph[i].length < n
    graph[i] 不包含 i
    如果 graph[a] 包含 b ，那么 graph[b] 也包含 a
    输入的图总是连通图
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/shortest-path-visiting-all-nodes
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

**整体思路：** 图最短路径在搜索过程中常用算法为广度优先算法(BFS)，而在BFS中我们一般是不会有回溯的现象，即结点已经访问过了则不再访问，但题目中显然我们是需要再次去访问某一个结点的，那么就会出现一个死循环的问题，如何去避免呢，那么我们就应该去记录到达当前点时已经走过的路径，如例子1->0->2->0->3，如果我们使用这样的字符串是作为唯一标识，由于其是无向图，会有2->0->1->0->3这样顺序变化，导致其不可行。再观察其结点数不超过12，所以考虑使用位运算的方式来记录在到达当前结点时，他经过的路径是怎样的，比如1->0->2可以表示为1110，这样的话不论其实际走的顺序如何，都不会影响其唯一性的判断；  
**循环退出条件：** 其所有位的置均为1，说明所有的点都已经走完，结束；  
**流程：**  
（1）使用队列，Int【3】=\{当前结点，已走路径，路径长度\};  
（2）建立visited数组，第一维表示当前结点，第二维表示当前路径（位运算）；  
（3）遍历队列，如果当前的节点已走路径值的各位均为1，说明最短路径已经找到，返回即可；  
（4）如果当前的节点已走路径值的各位不均为1，则与下一跳的位运算结果相或，得到下一跳的已走路径值，并生成相应队列节点，更新visited数组；返回（3）；

class Solution {
        
        public int shortestPathLength(int[][] graph) {
        
            int n=graph.length;
            Queue<int []> queue=new LinkedList<>();
            boolean visited[][]=new boolean[n][1<<n];
            for (int i=0;i<n;i++){
        
                queue.add(new int[]{
        i,1<<i,0});
                visited[i][1<<i]=true;
            }
            int res=0;
            while(!queue.isEmpty()){
        
                int head[]=queue.poll();
                int index=head[0];
                int mask=head[1];
                int dist=head[2];
                if(mask==(1<<n)-1) {
        
                    res=dist;
                    break;
                }
                for(int i=0;i<graph[index].length;i++){
        
                    int nextMask=mask|(1<<graph[index][i]);
                    if(!visited[graph[index][i]][nextMask]){
        
                        queue.add(new int[] {
        graph[index][i],nextMask,dist+1});
                        visited[graph[index][i]][nextMask]=true;
                    }
                }
    
            }
            return res;
        }
    }