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

存在一个由 n 个节点组成的无向连通图，图中的节点按从 0 到 n - 1 编号。
给你一个数组 graph 表示这个图。其中，graph[i] 是一个列表，由所有与节点 i 直接相连的节点组成。
返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边。

提示：

• n == graph.length

• 1 <= n <= 12

• 0 <= graph[i].length < n

• graph[i] 不包含 i

• 如果 graph[a] 包含 b ，那么 graph[b] 也包含 a

• 输入的图总是连通图

  思路：BFS + 状态压缩

• BFS写法，大致的思路是，由于我们需要折返， 所以不能像标准bfs算法一样，根据一个节点或一条边是否被访问去修剪。

• 问题就变成了如何去修剪，既不会不必要地重复访问，又不会把正解修剪掉。

• 我们可以记录当我们位于一个节点时整个图被访问的状态，试想我们在当前节点知道目前整个图的状态state，我们要决定是否要访问一个邻节点v，只需要看一下元组(v, state)是否已经被访问过，如果是的话，证明这条路已经被遍历过了，不需要再访问。

• 至于如何表示state，第一时间想到可以用一个HashSet，但是我们要快速检查一个状态是否被访问过，用HashSet效率太低。恰好题目最多只有12个节点，所以可以用位运算进行状态压缩。

class Solution {
    public int shortestPathLength(int[][] graph) {
        int n = graph.length;
        // Store tuple: (vertex, bit_mask)
        Queue<Pair<Integer, Integer>> q = new LinkedList<>();
        Set<Pair<Integer, Integer>> visited = new HashSet<>();
        for (int i = 0; i < n; ++i) {
            q.offer(new Pair<>(i, 1 << i));
            visited.add(new Pair<>(i, 1 << i));
        }

        // BFS
        int dis = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                Pair<Integer, Integer> p = q.poll();
                if (p.getValue() == (1 << n) - 1) {
                    return dis;
                } 
                for (int v: graph[p.getKey()]) {
                    Pair<Integer, Integer> pv = new Pair<>(v, p.getValue() | 1 << v);
                    if (!visited.contains(pv)) {
                        q.offer(pv);
                        visited.add(pv);
                    }
                }
            }
            ++dis;
        }
        return 0;
    }
}

解法二：

class Solution {
    public int shortestPathLength(int[][] graph) {
        int len=graph.length;
        if(graph==null || graph.length==0){
            return 0;
        }
        boolean[][] visited=new boolean[len][1<<len]; // 标记是否访问过,用于避免重复访问
        int finishState=(1<<len)-1;  // 用于检查是否访问完所有的节点,每个位代表一个节点的状态,形如1111
        Queue<int[]> queue=new LinkedList<>(); // 队列里的数组,第一个记录的是标号,第二个是状态
        for(int i=0; i<len; i++){
            queue.offer(new int[]{i,1<<i});
        }
        int step=0;
        while(!queue.isEmpty()){
            for(int i=queue.size(); i>0; i--){
                int[] node=queue.poll();
                if(finishState==node[1]){ // 如果标记的节点访问状态是结束,那么返回步长
                    return step;
                }
                for(int next:graph[node[0]]){
                    int nextState=node[1]|(1<<next); // 2个节点相或,标记着访问了这条边的2个点
                    if(visited[next][nextState]){
                        continue;
                    }
                    visited[next][nextState]=true;
                    queue.offer(new int[]{next,nextState}); // 将该节点和边的信息加入bfs对列
                }
            }
            step++;
        }
        return step;
    }
}