LeetCode 847. 访问所有节点的最短路径 题目描述 存在一个由 n 个节点组成的无向连通图，节点编号从 0 到 n - 1。给定一个数组 graph 表示图的邻接表，其中 graph[ i ] 是一个列表，列出与节点 i 直接相连的所有节点。返回能够访问所有节点的最短路径的长度。路径可以从任意节点开始和结束，并且可以多次访问同一个节点或重复使用边。 示例： 输入：graph = [ [ 1,2,3],[ 0],[ 0],[ 0] ] 输出：4 解释：一种最短路径是 [ 0,1,0,2,0,3] 或 [ 1,0,2,0,3,0 ]，长度为 4（3 条边，但路径长度按节点数计为 4）。 解题过程 问题分析 本题要求从任意起点出发，访问所有节点的最短路径。由于可以重复访问节点和边，传统 BFS 无法直接应用（会陷入循环）。 关键点：需要记录已访问的节点集合，但允许重复访问。因此，状态应包含当前节点和已访问的节点组合。 状态设计 使用位掩码（bitmask）表示已访问的节点集合。例如，n=4 时，掩码 1111（二进制）表示所有节点已访问。 状态定义为 (当前节点, 掩码)，其中掩码的二进制第 i 位为 1 表示节点 i 已访问。 例如：状态 (2, 1011) 表示当前在节点 2，已访问节点 0、1、3。 BFS 初始化 起点可以是任意节点。初始时，从每个节点 i 出发，掩码为仅包含 i 的状态（即 1< <i）。 BFS 队列存储 (节点, 掩码)，同时记录到达该状态的步数。 使用 visited 字典或集合，避免重复处理相同状态。 BFS 过程 从队列中取出当前状态 (node, mask)。 若 mask 等于全 1（即 (1< <n) - 1），说明已访问所有节点，返回当前步数。 遍历 node 的邻居 next_ node： 计算新掩码 new_ mask = mask | (1 << next_ node)。 若 (next_ node, new_ mask) 未访问过，则加入队列。 步数每层递增 1。 复杂度分析 时间：O(n * 2^n)，状态数为 n * 2^n。 空间：O(n * 2^n)，用于存储 visited 和队列。 示例演示 以 graph = [ [ 1,2,3],[ 0],[ 0],[ 0] ] 为例： n=4，目标掩码为 1111（十进制 15）。 初始：队列包含 (0,1)、(1,2)、(2,4)、(3,8)，步数=0。 第一步：从 (0,1) 到邻居 1、2、3，新掩码分别为 1|2=3、1|4=5、1|8=9，加入队列。 后续 BFS 中，当某状态掩码=15 时终止。最短路径为 4 个节点（3 条边），对应步数=3（BFS 层数）。 通过这种状态压缩的 BFS，可高效解决带重复访问的图遍历问题。