An undirected, connected graph of N nodes (labeled
0, 1, 2, ..., N-1) is given asgraph.
graph.length = N, andj != iis in the listgraph[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 <= graph.length <= 120 <= graph[i].length < graph.length
Approach #1: BFS + Bit. [C++]
class Solution {
public:
int shortestPathLength(vector<vector<int>>& graph) {
const int n = graph.size();
const int kAns = (1 << n) - 1;
queue<pair<int, int>> q;
vector<vector<int>> visited(n, vector<int>(1<<n));
for (int i = 0; i < n; ++i)
q.push({i, 1 << i});
int steps = 0;
while (!q.empty()) {
int s = q.size();
while (s--) {
auto p = q.front();
q.pop();
int node = p.first;
int state = p.second;
if (state == kAns) return steps;
if (visited[node][state]) continue;
visited[node][state] = 1;
for (int next : graph[node])
q.push({next, state | (1 << next)});
}
++steps;
}
return -1;
}
};
Reference:
http://zxi.mytechroad.com/blog/graph/leetcode-847-shortest-path-visiting-all-nodes/
847. Shortest Path Visiting All Nodes
原文：https://www.cnblogs.com/ruruozhenhao/p/10581131.html