This is the 6th day of my participation in the August More Text Challenge

Shortest path to all nodes

There exists an undirected connected graph consisting of n nodes numbered from 0 to N-1.

I’m going to give you an array graph that represents this graph. Graph [I] is a list of all nodes directly connected to node I.

Returns the length of the shortest path that can access all nodes. You can start and stop at any node, revisit the node multiple times, and reuse edges.

Example 1:

Input: graph = [[1, 2, 3], [0], [0], [0]] output: 4: a possible path for,0,2,0,3 [1]Copy the code

Example 2:

Input: graph = [[1], [0, 4-trichlorobenzene], [1 4], [2], [1, 2]] output: 4: a possible path for,1,4,2,3 [0]Copy the code

Tip:

  • n == graph.length
  • 1 <= n <= 12
  • 0 <= graph[i].length < n
  • graph[i]Does not containi
  • ifgraph[a]containsb, thengraph[b]Also containsa
  • The input graph is always a connected graph

Methods a

State compression DP + BFS: this is a short-circuit problem, and the edge weight is 1, then the first thought of using BFS to solve; What we seek in the question is the shortest path after all nodes are visited, so our joining state should be a whole state of whether all points of the current whole graph are visited. So what do we call this whole state? When we see the data range given in the prompt, we think of using state compression to represent it, that is, 0~(1 << n) -1, where the ith bit is 1, indicating that the ith node has been accessed;

class Solution { public int shortestPathLength(int[][] graph) { LinkedList<int[]> q = new LinkedList<>(); int n = graph.length; Int [][] f = new int[1 << n][n]; int[] f = new int[1 << n][n]; int[] f = new int[1 << n]; for (int i = 0; i < 1 << n; i ++ ) for (int j = 0; j < n; j ++ ) f[i][j] = (int)1e8; for (int i = 0; i < n; i ++ ) { q.add(new int[]{(1 << i), i}); f[1 << i][i] = 0; } while(q.size() > 0) { int[] t = q.poll(); for (int x : graph[t[1]]) { int s = t[0] | (1 << x); if (f[s][x] > f[t[0]][t[1]] + 1) { f[s][x] = f[t[0]][t[1]] + 1; q.add(new int[]{s, x}); } } } int res = (int)1e8; for (int i = 0; i < n; i ++ ) res = Math.min(res, f[(1 << n) - 1][i]); return res; }}Copy the code

O(n*(1<

O(n*(1<