847. 访问所有节点的最短路径
方法一：状态压缩 + 广度优先搜索
题目需要求出「访问所有节点的最短路径的长度」，并且图中每一条边的长度均为 1，可以考虑使用广度优先搜索的方法求出最短路径。
在常规的广度优先搜索中，会在队列中存储节点的编号。对于本题而言，最短路径的前提是「访问了所有节点」，因此除了记录节点的编号以外，还需要记录每一个节点的经过情况。因此，我们使用三元组 (u, mask, dist) 表示队列中的每一个元素，其中：
- u 表示当前位于的节点编号；
- mask 是一个长度为 n 的二进制数，表示每一个节点是否经过。如果 mask 的第 i 位是
1，则表示节点 i 已经过，否则表示节点 i 未经过； - dist 表示到当前节点为止经过的路径长度。
初始时，将所有的 (i, 2i, 0) 放入队列，表示可以从任一节点开始。在搜索的过程中，如果当前三元组中的 mask 包含 n 个 1（即 mask = 2n - 1），那么就可以返回dist 作为答案。
为了保证广度优先搜索时间复杂度的正确性，即同一个节点 u 以及节点的经过情况 mask 只被搜索到一次，可以使用数组或者哈希表记录 (u, mask) 是否已经被搜索过，防止无效的重复搜索。
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
方法二：预处理点对间最短路 + 状态压缩动态规划
由于题目中给定的图是连通图，那么可以计算出任意两个节点之间 u, v 间的最短距离，记为 d(u, v)。这样一来，就可以使用动态规划的方法计算出最短路径。
对于任意一条经过所有节点的路径，它的某一个子序列（可以不连续）一定是 0, 1, ?, n?1 的一个排列。我们称这个子序列上的节点为「关键节点」。在动态规划的过程中，我们也是通过枚举「关键节点」进行状态转移的。
我们用 f[u][mask] 表示从任一节点开始到节点 u 为止，并且经过的「关键节点」对应的二进制表示为 mask 时的最短路径长度。由于 u 是最后一个「关键节点」，那么在进行状态转移时，我们可以枚举上一个「关键节点」v，即：
其中 mask\u 表示将 mask 的第 u 位从 1 变为 0 后的二进制表示。也就是说，「关键节点」v 在 mask 中的对应位置必须为 1，将 f[v][mask\u] 加上从 v 走到 u 的最短路径长度为 d(v, u)，取最小值即为 f[u][mask]。
最终的答案即为：
当 mask 中只包含一个 1 时，我们无法枚举满足要求的上一个「关键节点」v。这里的处理方式与方法一中的类似：若 mask 中只包含一个 1，说明我们位于开始的节点，还未经过任何路径，因此状态转移方程直接写为：
f[u][mask] = 0
此外，在状态转移方程中，我们需要多次求出 d(v, u)，因此我们可以考虑在动态规划前将所有的 d(v, u) 预处理出来。这里有两种可以使用的方法，时间复杂度均为 O(n^3)：
我们可以使用 Floyd 算法求出所有点对之间的最短路径长度；
我们可以进行 n 次广度优先搜索，第 i 次从节点 i 出发，也可以得到所有点对之间的最短路径长度。
class Solution:
def shortestPathLength(self, graph: List[List[int]]) -> int:
n = len(graph)
d = [[n + 1] * n for _ in range(n)]
for i in range(n):
for j in graph[i]:
d[i][j] = 1
# 使用 floyd 算法预处理出所有点对之间的最短路径长度
for k in range(n):
for i in range(n):
for j in range(n):
d[i][j] = min(d[i][j], d[i][k] + d[k][j])
f = [[float("inf")] * (1 << n) for _ in range(n)]
for mask in range(1, 1 << n):
# 如果 mask 只包含一个 1，即 mask 是 2 的幂
if (mask & (mask - 1)) == 0:
u = bin(mask).count("0") - 1
f[u][mask] = 0
else:
for u in range(n):
if mask & (1 << u):
for v in range(n):
if (mask & (1 << v)) and u != v:
f[u][mask] = min(f[u][mask], f[v][mask ^ (1 << u)] + d[v][u])
ans = min(f[u][(1 << n) - 1] for u in range(n))
return ans
1、旅行商问题的一般形式
旅行商问题（TSP）：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。从图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的哈密顿回路。
本题是一道类似旅行商问题，区别在于：可以重复访问某些节点，且在遍历完最后一个节点后不用回到出发点。
2、广度优先搜索的原理
广度优先搜索（BFS）算法是一种盲目搜索算法，目的是系统地检查图中所有节点，直到找到结果为止。由于广度优先搜索的扩展原则是先生成的节点先扩展，所以可以求得最短路径。一般而言，利用一个队列 queue 来存储当前已经生成的节点，每次弹出队头元素进行下一步扩展。
例子：在以下图中寻找值为 8 的节点
首先将起点放入队列，这是第一个生成的节点。
开始第一轮循环，本轮队列中仅 1 个元素。
弹出队头元素 1，扩展，生成了 2, 3 两个节点，均放入队列。
队列中 1 个元素扩展完成，本次循环结束。开始新一轮循环，本轮队列中有 2 个元素
弹出队头元素 2，扩展，生成了 4, 5 两个节点，放入队列。
弹出队头元素 3，扩展生成 6, 7，放入队列。
队列中 2 个元素扩展完成，本次循环结束。开始新一轮循环，本轮队列中有 4 个元素
弹出队头元素 4，扩展生成 8，找到了答案，当前处在第 3 轮循环，所以最短路径为 3。此时本轮仍有 3 个元素未被扩展，但因为已经找到了答案，所以直接退出搜索。
但是 BFS 算法扩展的前提是，每个节点可以以任意顺序扩展，也即一个节点与所有它可以扩展的节点距离都相同。对于本题而言，需要求最短路径，且任意两个节点之间距离均为 1，所以可以使用 BFS 算法。
特别地，根据上述例子，我们需要每次记录本轮循环队列中的节点数量，以便最终判定最短路径长度；另一方面，对于已生成的节点，需要标记，防止重复被生成。**一般而言，为了写代码时更加方便直观，在扩展过程中不判断是否找到了答案，而是每次弹出队头元素时进行判断。**所以一般的 BFS 代码框架如下：
# 1.初始化队列及标记数组，存入起点
# 1.初始化队列及标记数组，存入起点
from collections import deque
q = deque()
# graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
graph = [[1,2],[0,3,4],[0,5,6],[1,7],[1,7],[2,7,8],[2,8],[3,4,5],[5,6]]
target = 4
vis = [False for i in graph] # vector
q.extend(graph[0]) # 存入起点，标记
vis[0] = True
# 2.开始搜索
while q:
cur = q.popleft() # 弹出队头元素
# 找到答案，退出搜索
if cur == target:
print("hello")
break
# action(cur) # 有些题目需要对当前元素做处理
for x in graph[cur]:
if not vis[x]:
q.append(x)
vis[x] = True
当然，我们也可以将当前扩展的距离作为一个变量一起存入队列：
from collections import deque
q = deque()
# graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
graph = [[1,2],[0,3,4],[0,5,6],[1,7],[1,7],[2,7,8],[2,8],[3,4,5],[5,6]]
target = 7
vis = [False for i in graph]
q.append((0,0))
vis[0] = True
while q:
cur, dist = q.popleft()
print(cur,dist)
if cur == target:
print("distance = ", dist)
break
# action(cur) # 有些题目需要对当前元素做处理
for x in graph[cur]:
if not vis[x]:
q.append((x, dist + 1))
vis[x] = True
3、状态压缩
本题与一般的图论题目不同的是，需要遍历完图内全部节点，且可以重复访问某些节点。所以需要在搜索过程中，记录当前已经遍历了哪些节点。如果利用数组来存储每个节点的状态，在传参时较为不方便，效率不高。本题数据范围 n ≤12，说明可以利用状态压缩。
状态压缩也即用一个变量来表示当前状态，比较常用的方式是利用一个 n 位 k 进制数 mask 表示当前 n 个节点的所处的 k 个不同状态。对于本题而言，某个节点只需要记录是否遍历过，所以利用二进制即可。
一般而言，mask 从低到高第 i 位为 0 表示第 i 个节点还未被访问过，为 1 则相反。例如，假设有 3 个点，点 1 遍历过，点 2, 3 未遍历，则 mask = 001；若点 3 遍历过，点 1, 2 未遍历，则 mask = 100 。特别地，三个点均未遍历时，mask = 000 = 0，均遍历过时，mask = 111 = 2 k
?1
一些状态压缩的基本操作如下：
- 访问第 i 个点的状态：state=(1 << i) & mask
- 更改第 i 个点状态为 1：mask = mask | (1 << i)
4、基于状态压缩的广度优先搜索算法
根据之前的介绍，本题可以通过广度优先搜索算法对图中节点进行扩展，并利用状态压缩记录节点的遍历情况。具体实现细节如下：
- BFS 参数：当前节点编号 idx，当前搜索状态 mask，当前扩展距离 dist
- BFS 起点：题目不限制起点，所以最开始可以将每个点都存入队列，对应状态为仅该点遍历。例如图中有 2 个点时，分别将第一个点及其对应的 mask = 01，第二个点和其对应的 mask = 10 存入。
- BFS 终点：最终要求所有点均遍历，所以当 mask = 2n - 1 时搜索结束。
- BFS 标记：尽管本题可以重复访问某些节点，但是在同一状态下重复访问某一节点必然是无用功。所以在实现时，利用一个二维标记数组记录某一状态下，某一节点的拓展情况，防止被重复扩展。
class Solution:
def shortestPathLength(self, graph: List[List[int]]) -> int:
n = len(graph)
# 1.初始化队列及标记数组，存入起点
# 三个属性分别为 idx, mask, dist；存入起点，起始距离 0
q = deque((i, 1 << i, 0) for i in range(n))
# 节点编号及当前状态
vis = {(i, 1 << i) for i in range(n)}
# 开始搜索
while q:
u, mask, dist = q.popleft() # 弹出队头元素
if mask == (1 << n) - 1: # 找到答案，返回结果
return dist
# 扩展
for x in graph[u]:
nextmask = mask | (1 << x)
if (x, nextmask) not in vis:
q.append((x, nextmask, dist + 1))
vis.add((x, nextmask))
return 0