847 Shortest Path Visiting All Nodes

847. Shortest Path Visiting All Nodes

1. Question

An undirected, connected graph of N nodes (labeled 0, 1, 2, ..., N-1) is given asgraph.

graph.length = N, andj != i is in the list graph[i] exactly once, if and only if nodesiandjare connected.

Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.

Example 1:

Input: [[1,2,3],[0],[0],[0]]

Output: 4

Explanation: One possible path is [1,0,2,0,3]

Example 2:

Input: [[1],[0,2,4],[1,3,4],[2],[1,2]]

Output: 4

Explanation: One possible path is [0,1,4,2,3]

Note:

1. 1 <= graph.length <= 12

2. 0 <= graph[i].length < graph.length

2. Implementation

(1) BFS + BIt Manipulation

思路: 用Bit Manipulation表示记录已经访问过的node的状态，以每个node作为起点做BFS，找出其中的最短路径即可

class Solution {
    public int shortestPathLength(int[][] graph) {
        int n = graph.length;
        int total = (1 << n) - 1;

        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});
        }

        int step = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                int[] curInfo = queue.remove();
                int curNode = curInfo[0];
                int curState = curInfo[1];

                if (curState == total) {
                    return step;
                }

                for (int nextNode : graph[curNode]) {
                    int nextState = curState | (1 << nextNode);
                    if (!visited[nextNode][nextState]) {
                        queue.add(new int[] {nextNode, nextState});
                        visited[nextNode][nextState] = true;
                    }
                }
            }
            ++step;
        }
        return -1;
    }
}

3. Time & Space Complexity

时间复杂度O(n * 2^n), n为node的个数，因为我们会尝试从每个node作为起点找最短路径，而从每个node出发，最多会有2^n个状态，所以时间复杂度是n * 2^n, 空间复杂度O(n * 2^n)