Loading... # 问题 [LeetCode #847][1] 在一个无向连通图中寻找一个最短路径，这个路径通过图中的所有节点。这个路径的起点、终点任意，可以重复访问节点。 # 分析 此题由于可以重复访问节点，因此并不同于旅行商（TSP）问题。 下面使用BFS解决问题。此题的关键在于BFS的“状态节点”是什么，如何不重复状态。 因为需要知道到某状态时是否访问了所有的节点，因此需要记录N个节点的访问状态。这里可以用bool数组，可以用bitset。而由于N<12，2^12在int范围内，实际上我们可以用一个int来记录N个点的访问情况（二进制意义）。由于之前没有用过bitset，故下面使用的是bitset。 如何才能不走没有意义的多余的路呢？显然，不重复访问节点是不行的，因为有的图必须这样才能访问到所有的点，如样例1。考虑“状态”包含的信息，有：现在处于的点、已经访问过的点、当前状态已经走过的长度。举一些例子可以发现，如果要求前二者组成的“状态”不重复，就能保证不遗漏最优解，并且去掉很多没有意义的走法。这里应该是用到了BFS时队列前面的状态走过的边数一定不大于后面的状态这一特点，并且本题每条边长度都是1。因此位于同一点，并且访问过了相同的点的状态，肯定是前面的要比后面的好。 最后是何时结束BFS的问题。上面已经说过，因为前面的状态一定比后面的好，因此第一个走完全部点的状态就是最好的状态。因此只要找到第一个完成的状态就可以返回答案了。 # 代码 ```cpp class Solution { struct State { int now; bitset<12> visited; int length; State(): now(0), length(0) {}; }; public: int shortestPathLength(vector<vector<int>>& graph) { // BFS const int N = graph.size(); string completed_str(""); for (int i = 0; i < N; i++) completed_str += '1'; const bitset<12> completed_state(completed_str); int ans = 0x7fffffff; bool visited_state[N][1 << N]; memset(visited_state, 0, sizeof(visited_state)); queue<State> q; for (int i = 0; i < N; i++) { State tmp; tmp.now = i; tmp.visited[i] = 1; q.push(tmp); visited_state[i][tmp.visited.to_ulong()] = 1; } while (q.size()) { State nowsta = q.front(); q.pop(); if (nowsta.visited == completed_state) { ans = nowsta.length; break; } for (int j = 0; j < graph[nowsta.now].size(); j++) { int& nxt = graph[nowsta.now][j]; if (nowsta.length + 1 < ans) { // move to j State newsta; newsta.now = nxt; newsta.length = nowsta.length + 1; newsta.visited = nowsta.visited; newsta.visited[nxt] = 1; if (visited_state[nxt][newsta.visited.to_ulong()]) continue; q.push(newsta); visited_state[nxt][newsta.visited.to_ulong()] = 1; } } // end of for } return ans; } }; ``` [1]: https://leetcode.com/problems/shortest-path-visiting-all-nodes/ Last modification：June 24th, 2020 at 03:52 pm © 允许规范转载 Support 如果觉得我的文章对你有用，请随意赞赏 Appreciate the author