LeetCode 847 Shortest Path Visiting All Nodes_综合

思路

由于是求简单图最小路径问题，所以可以用BFS来解决（最短路模版，每次遍历一层节点）。可以发现，一条路径的最终的长度只与最后一个经过的点有关系，跟访问前面节点的顺序没有关系。所以我们可以用一个二维visit数组记录每种路线终点所对应的路线，避免重复搜索；BFS的队列中存储一维数组node，node[0]:最后一个节点，node[1]：路线对应的整数【在这里将路线压缩成一个整数，原理是使用二进制的思想，从右向左代表0～n位，比如1101就是路线0-2-3】

在程序中一旦找到第一个能遍历所有节点的路线就返回步数，这保证了程序的正确性：寻找最短的步数。

位操作：（1）1<<len：所有可能的路线代表的整数=2^len
（2）(1<<len)-1：所有位都是1的情况，比如len=3，(1<<3) - 1 = (1000)₂ - 1 = (111)₂
（3）int nextState = state | (1 << next) ：将next那个节点加入到路线代表的整数中，比如当前state=(001)₂, next为节点2，于是加入后nextState = (101)₂.

复杂度

时间复杂度 $O(n*2^n)$ :从每一个节点(n)出发都有2^n种路径（从二进制可以看出）
空间复杂度 $O(n*2^n)$

代码

class Solution {
    public int shortestPathLength(int[][] graph) {
    // bfsint len = graph.length;// [endPoint][state]boolean[][] visit = new boolean[len][1 << len];Queue<int[]> queue = new LinkedList<>();int goal = (1 << len) - 1;for (int i = 0; i < len; i++) {
    queue.offer(new int[]{
    i, 1 << i});}int step = 0;while (!queue.isEmpty()) {
    int size = queue.size();while (size-- > 0) {
    int[] node = queue.poll();int endWith = node[0], state = node[1];if (goal == state) {
    return step;}for (int next : graph[endWith]) {
    int nextState = state | (1 << next);if (visit[next][nextState]) {
    continue;}queue.offer(new int[]{
    next, nextState});visit[next][nextState] = true;}}step++;}return step;}
}