Skip to content

Latest commit

 

History

History
111 lines (75 loc) · 4.89 KB

0847.md

File metadata and controls

111 lines (75 loc) · 4.89 KB

0847. 访问所有节点的最短路径

  • 标签：位运算、广度优先搜索、图、动态规划、状态压缩
  • 难度：困难

题目链接

题目大意

描述：存在一个由 $n$ 个节点组成的无向连通图，图中节点编号为 $0 \sim n - 1$。现在给定一个数组 $graph$ 表示这个图。其中，$graph[i]$ 是一个列表，由所有与节点 $i$ 直接相连的节点组成。

要求：返回能够访问所有节点的最短路径长度。可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边。

说明：

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

示例：

  • 示例 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]

解题思路

思路 1：状态压缩 + 广度优先搜索

题目需要求解的是「能够访问所有节点的最短路径长度」，并且每个节点都可以作为起始点。

如果对于一个特定的起点，我们可以将该起点放入队列中，然后对其进行广度优先搜索，并使用访问数组 $visited$ 标记访问过的节点，直到所有节点都已经访问过时，返回路径长度即为「从某点开始出发，所能够访问所有节点的最短路径长度」。

而本题中，每个节点都可以作为起始点，则我们可以直接将所有节点放入队列中，然后对所有节点进行广度优先搜索。

因为本题中节点数目 $n$ 的范围为 $[1, 12]$，所以我们可以采用「状态压缩」的方式，标记节点的访问情况。每个点的初始状态可以表示为 (u, 1 << u)。当状态 $state == 1 \text{ &lt;}\text{&lt; } n - 1$ 时，表示所有节点都已经访问过了，此时返回其对应路径长度即为「能够访问所有节点的最短路径长度」。

为了方便在广度优先搜索的同事，记录当前的「路径长度」以及「节点的访问情况」。我们可以使用一个三元组 $(u, state, dist)$ 来表示当前节点情况，其中：

  • $u$：表示当前节点编号。
  • $state$：一个 $n$ 位的二进制数，表示 $n$ 个节点的访问情况。$state$ 第 $i$ 位为 $0$ 时表示未访问过，$state$ 第 $i$ 位为 $1$ 时表示访问过。
  • $dist$ 表示当前的「路径长度」。

同时为了避免重复搜索同一个节点 $u$ 以及相同节点的访问情况，我们可以使用集合记录 $(u, state)$ 是否已经被搜索过。

整个算法步骤如下：

  1. 将所有节点的 (节点编号, 起始状态, 路径长度) 作为三元组存入队列，并使用集合 $visited$ 记录所有节点的访问情况。
  2. 对所有点开始进行广度优先搜索：
    1. 从队列中弹出队头节点。
    2. 判断节点的当前状态，如果所有节点都已经访问过，则返回答案。
    3. 如果没有全访问过，则遍历当前节点的邻接节点。
    4. 将邻接节点的访问状态标记为访问过。
    5. 如果节点即当前路径没有访问过，则加入队列继续遍历，并标记为访问过。
  3. 重复进行第 $2$ 步，直到队列为空。

思路 1：代码

import collections


class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        size = len(graph)

        queue = collections.deque([])
        visited = set()
        for u in range(size):
            queue.append((u, 1 << u, 0))            # 将 (节点编号, 起始状态, 路径长度) 存入队列
            visited.add((u, 1 << u))                # 标记所有节点的节点编号，以及当前状态

        while queue:                                # 对所有点开始进行广度优先搜索
            u, state, dist = queue.popleft()        # 弹出队头节点
            if state == (1 << size) - 1:            # 所有节点都访问完，返回答案
                return dist
            for v in graph[u]:                      # 遍历邻接节点
                next_state = state | (1 << v)       # 标记邻接节点的访问状态
                if (v, next_state) not in visited:  # 如果节点即当前路径没有访问过，则加入队列继续遍历，并标记为访问过
                    queue.append((v, next_state, dist + 1))
                    visited.add((v, next_state))

        return 0

思路 1：复杂度分析

  • 时间复杂度：$O(n^2 \times 2^n)$，其中 $n$ 为图的节点数量。
  • 空间复杂度：$O(n \times 2^n)$。