Leetcode0847. 访问所有节点的最短路径(difficult,BFS,状态压缩)_遍历所有节点的最短路径

目录

1. 问题描述

2. 方法一：单源广度优先搜索

2.1 思路

2.2 代码实现

3. 方法二：状态压缩+广度优先搜索

3.1 思路

3.2 代码

4. 方法三：预处理点对间最短路 + 状态压缩动态规划

---

1. 问题描述

存在一个由 n 个节点组成的无向连通图，图中的节点按从 0 到 n - 1 编号。

给你一个数组 graph 表示这个图。其中，graph[i] 是一个列表，由所有与节点 i 直接相连的节点组成。返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边。

示例 1：

输入：graph = [[1,2,3],[0],[0],[0]]
输出：4
解释：一种可能的路径为 [1,0,2,0,3]

示例 2：

输入：graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
输出：4
解释：一种可能的路径为 [0,1,4,2,3]

提示：

• n == graph.length
• 1 <= n <= 12
• 0 <= graph[i].length < n
• graph[i] 不包含 i
• 如果 graph[a] 包含 b ，那么 graph[b] 也包含 a
• 输入的图总是连通图

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shortest-path-visiting-all-nodes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 方法一：单源广度优先搜索

2.1 思路

        最短路径问题，广度优先搜索。

        但是，本题中节点可以重复访问，边也可以重复，目的是遍历所有的节点。所以在遍历过程中，寻找邻接节点时，不再受基本的图遍历中那种已经访问过的节点就不访问了的约束。

        当然，访问过的节点还是需要记录跟踪。一旦所有的节点都至少访问过一次，搜索就停止，此时，所得到的层数就是所求的遍历所需要的最小路径长度。

        等价于要搜索的图是一张由输入的图生成的超图。

        graph为输入的图的邻接表表示。

        进一步，从不同的点出发的结果可能不一样，所以遍历以所有各个节点作为起点进行搜索。并取其中最小值。

2.2 代码实现

from typing import List
from collections import deque
class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        def bfs(start):
            q       = deque([[start]])
            # visited = set([0])
            while True:
                path = q.popleft()
                # print("path = {0}", path)
                if len(set(path))==len(graph):
                    return len(path)-1
                for neighbor in graph[path[-1]]:
                    q.append(path + [neighbor])
            
        minpath = bfs(0)
        for k in range(1,len(graph)):
            pathlen = bfs(k)
            # print(k,pathlen)
            minpath = pathlen if pathlen < minpath else minpath
        return minpath

        悲惨的超时。。。

        原因在于以上方案是直接的展开，没有排除可能的重复访问。当有12个节点时树的规模急速扩大。

3. 方法二：状态压缩+广度优先搜索

        本题解参考学习官解。

3.1 思路

        由于题目需要我们求出「访问所有节点的最短路径的长度」，并且图中每一条边的长度均为 1，因此我们可以考虑使用广度优先搜索的方法求出最短路径。

        在常规的广度优先搜索中，我们会在队列中存储节点的编号。对于本题而言，最短路径的前提是「访问了所有节点」，因此除了记录节点的编号以外，我们还需要记录到达当前节点所经过的路径情况。因此，我们使用三元组 (u,mask,dist) 表示队列中的每一个元素，其中：

        u 表示当前访问到的节点编号；

        mask 是一个长度为 n 的二进制数，表示每一个节点是否经过。如果mask 的第 i 位是 1，则表示节点 i 已经过，否则表示节点 i 未经过；

        dist 表示到当前节点为止经过的路径长度（即广度优先搜索的层序号）

        这样一来，我们使用该三元组进行广度优先搜索，即可解决本题。初始时，我们将所有的 (i, 2^i, 0)放入队列，表示可以从任一节点开始。在搜索的过程中，如果当前三元组中的 mask 包含 n 个 1（即 mask = 2^n - 1，那么我们就可以返回 dist 作为答案。

        以上思路有几个关键点，补充说明一下：

• (1) 以上解法是把问题作为一个多源BFS来处理。当然，也可以做每个节点的单源BFS处理，然后做一次for循环。后者正是上面方法一的做法，但是这种“单源BFS+for循环”的方法会导致不同单元BFS之间的重复情况无法得到优化（会有大量的重复访问），这个也可能就是以上方法一的根本原因
• (2) 用mask来表示路径历史，也就是所谓的状态压缩
• (3) 记录既往访问状态只需要关注最后节点以及该路径历史上访问过哪些节点，不需要关心是以哪种顺序访问这些节点。这个是提高效率的关键点。这个其实是需要一个证明或者至少一个定性解释。

3.2 代码

class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        n = len(graph)
        q = deque((i, 1 << i, 0) for i in range(n))
        seen = {(i, 1 << i) for i in range(n)}
        ans = 0
        
        while q:
            u, mask, dist = q.popleft()
            if mask == (1 << n) - 1:
                ans = dist
                break
            # 搜索相邻的节点
            for v in graph[u]:
                # 将 mask 的第 v 位置为 1
                mask_v = mask | (1 << v)
                if (v, mask_v) not in seen:
                    q.append((v, mask_v, dist + 1))
                    seen.add((v, mask_v))
        
        return ans

        执行用时：164 ms, 在所有 Python3 提交中击败了95.43%的用户

        内存消耗：19.9 MB, 在所有 Python3 提交中击败了35.67%的用户

4. 方法三：预处理点对间最短路 + 状态压缩动态规划

        这是官解给出的另一个方案。

        待补充。

        回到主目录：笨牛慢耕的Leetcode每日一解题解笔记(动态更新。。。)