847. Shortest Path Visiting All Nodes.md

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. 1 <= graph.length <= 12(This means 2 ^ n level)
2. 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;
      }
  }

Amazon Session

• Method 1: bfs + bit manipulation

   class Solution {
   	public int shortestPathLength(int[][] graph) {
   		int len = graph.length;
   		boolean[][] visited = new boolean[len][1 << len];
   		int expect = (1 << len) - 1;
   		Queue<int[]> q = new LinkedList<>();
   		for(int i = 0; i < len; i++){
   			q.offer(new int[]{i, 1 << i});
   		}
   		int step = -1;
   		while(!q.isEmpty()){
   			step++;
   			int size = q.size();
   			for(int sz = 0; sz < size; sz++){
   				int[] cur = q.poll();
   				int node = cur[0];
   				int state = cur[1];
   				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 step;
   	}
   }

Reference

1. 花花酱 LeetCode 847. Shortest Path Visiting All Nodes