难度: Hard
存在一个由 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.length1 <= n <= 120 <= graph[i].length < ngraph[i] 不包含 igraph[a] 包含 b ，那么 graph[b] 也包含 a运行时间: 101 ms
内存: 17.7 MB
class Solution:
def shortestPathLength(self, graph: List[List[int]]) -> int:
n = len(graph)
queue = []
vis = [[False for _ in range(1<<n)] for _ in range(n)] #1<<n就是2^N次方，转换成二进制
#print(vis)
for i in range(n):
queue.append([i, 1<<i])
vis[i][1<<i] = True #第i个的第2^i个变成True i个点时2^i已经被访问
#print(queue)
#print(vis)
step = 0
while queue:
next = []
for x, mask in queue:
if mask == (1 << n) - 1: #如果是最后一个点，那最短路径是0
return step
for y in graph[x]:
next_mask = mask | (1<<y)
if vis[y][next_mask]:
continue
vis[y][next_mask] = True
next.append([y, next_mask])
queue = next
step += 1
return 0
该题解采用了广度优先搜索（BFS）结合位掩码技术来解决问题。每个节点的状态由节点编号和一个整数表示，这个整数的二进制表示中，每个位的开闭状态代表对应节点是否被访问过。初始化时，将每个节点自身作为起点，放入队列，并标记为已访问。然后进行层次遍历，每次从队列中取出节点和对应状态，检查是否所有节点都已访问（位掩码中所有位都为1），如果是，则返回当前步数作为答案。否则，将当前节点的所有邻居节点按新的访问状态加入队列，继续遍历。这种方法有效地遍历了所有可能的路径，并在找到最短路径时立即停止。
时间复杂度: O(n^2 * 2^n)
空间复杂度: O(n * 2^n)
class Solution:
def shortestPathLength(self, graph: List[List[int]]) -> int:
n = len(graph)
queue = []
vis = [[False for _ in range(1<<n)] for _ in range(n)] # 创建一个二维数组来记录每个节点的每种状态是否被访问过
for i in range(n):
queue.append([i, 1<<i])
vis[i][1<<i] = True # 初始化，将每个节点自身设为已访问
step = 0
while queue:
next = []
for x, mask in queue:
if mask == (1 << n) - 1:
return step # 如果所有节点都已访问，返回步数
for y in graph[x]:
next_mask = mask | (1<<y)
if vis[y][next_mask]:
continue
vis[y][next_mask] = True
next.append([y, next_mask])
queue = next
step += 1
return 0
位掩码在处理节点访问状态时具有多个优势。首先，它允许我们在一个整数中压缩存储所有节点的访问情况，这样可以节省空间，并且访问和修改状态都非常快速，只需要简单的位操作即可。其次，位掩码使得比较状态和检查是否所有节点都已访问（即所有位都为1）变得非常高效。最后，位掩码很适合与图的遍历算法结合使用，特别是在需要追踪访问历史的场景中。
这是因为广度优先搜索（BFS）从多个起点同时开始，保证了我们在最先到达某个状态（即所有节点都被访问过的状态）时，所用的步数是最少的。BFS层次性的特点确保了每一层的遍历都是基于最短路径原则进行的。因此，一旦我们在某个状态下发现所有节点都被访问过，我们可以确信这个状态所对应的路径是最短的，从而可以立即返回这个步数作为最终答案。
这种初始化方法是基于考虑图可能不是完全连通的，或者即使是连通的，不同的起点可能导致不同的访问路径长度。通过从每个节点分别开始搜索，我们可以确保探索所有可能的路径组合，以找到真正的最短路径到达所有节点的方法。此外，这也符合问题的要求，即从任何一个节点开始，找到包含所有节点的最短环路。这种方法确保了算法的全面性和准确性。