问题

LeetCode #847

在一个无向连通图中寻找一个最短路径,这个路径通过图中的所有节点。这个路径的起点、终点任意,可以重复访问节点。

分析

此题由于可以重复访问节点,因此并不同于旅行商(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;
    }
};
Last modification:June 24th, 2020 at 03:52 pm
如果觉得我的文章对你有用,请随意赞赏