问题
在一个无向连通图中寻找一个最短路径,这个路径通过图中的所有节点。这个路径的起点、终点任意,可以重复访问节点。
分析
此题由于可以重复访问节点,因此并不同于旅行商(TSP)问题。
下面使用BFS解决问题。此题的关键在于BFS的“状态节点”是什么,如何不重复状态。
因为需要知道到某状态时是否访问了所有的节点,因此需要记录N个节点的访问状态。这里可以用bool数组,可以用bitset。而由于N<12,2^12在int范围内,实际上我们可以用一个int来记录N个点的访问情况(二进制意义)。由于之前没有用过bitset,故下面使用的是bitset。
如何才能不走没有意义的多余的路呢?显然,不重复访问节点是不行的,因为有的图必须这样才能访问到所有的点,如样例1。考虑“状态”包含的信息,有:现在处于的点、已经访问过的点、当前状态已经走过的长度。举一些例子可以发现,如果要求前二者组成的“状态”不重复,就能保证不遗漏最优解,并且去掉很多没有意义的走法。这里应该是用到了BFS时队列前面的状态走过的边数一定不大于后面的状态这一特点,并且本题每条边长度都是1。因此位于同一点,并且访问过了相同的点的状态,肯定是前面的要比后面的好。
最后是何时结束BFS的问题。上面已经说过,因为前面的状态一定比后面的好,因此第一个走完全部点的状态就是最好的状态。因此只要找到第一个完成的状态就可以返回答案了。
代码
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;
}
};