847. Shortest Path Visiting All Nodes

Question

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

graph.length = N, and j != i is in the list graph[i] exactly once, if and only if nodes i and j are 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 <= graph.length <= 12(This means 2 ^ n level)
0 <= graph[i].length < graph.length

Solution:

Method 1: bfs time complexity O(n * 2 ^ n)

Since we can visit a node multiple times, we need to have 2 variables to record breaking condition for a node:

cur_node
state: for current node, how many nodes were visited.

for a single node, if that state is visited means it is a duplicate condition and we can continue.

class Solution {
public int shortestPathLength(int[][] graph) {
    int len = graph.length;
    int expect = (1 << len) - 1; //This set all bits to 1.
    Queue<int[]> q = new LinkedList<>();    // int[] saves current node, visited states
    for(int i = 0; i < len; i++)
        q.offer(new int[]{i, 1 << i});  // We could start from any points.
    // if for current node and state, we visit it again will be dulplicate, we can continue.
    boolean[][] visited = new boolean[len][1 << len];
    int step = -1;
    while(!q.isEmpty()){
        int size = q.size();
        ++step;
        for(int i = 0; i < size; i++){
            int[] pair = q.poll();
            int node = pair[0];
            int state = pair[1];
            // We've visited all of the nodes
            if(state == expect) return step;
            if(visited[node][state]) continue;
            visited[node][state] = true;
            for(int next : graph[node]){
                q.offer(new int[]{next, state | (1 << next)});
            }
        }
    }
    return -1;
}
}

Reference

花花酱 LeetCode 847. Shortest Path Visiting All Nodes