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

解题思路

这是一道经典的状态压缩动态规划题目，结合了 BFS 和位掩码技巧。

核心思路：

由于题目要求访问所有节点，且节点数量不超过 12，我们可以使用位掩码来表示已访问的节点集合。状态可以用 (当前节点, 访问状态) 来表示，其中访问状态是一个整数的二进制表示。

算法步骤：

  1. 使用 BFS 搜索，队列中存储 (当前节点, 访问状态, 路径长度)
  2. 初始化：每个节点都可以作为起点，初始状态为只访问该节点
  3. 对于每个状态，尝试移动到相邻节点，更新访问状态
  4. 当访问状态包含所有节点时（即状态为 (1<<n)-1），返回当前路径长度
  5. 使用访问数组避免重复访问相同的 (节点, 状态) 组合

优化要点：

  • 使用位运算快速判断和更新访问状态
  • 通过记忆化避免重复计算相同状态
  • BFS 保证找到的第一个完整访问状态对应最短路径

时间复杂度主要取决于状态数量（节点数 × 2^节点数）和每个状态的转移次数。

代码实现

class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int n = graph.size();
        if (n == 1) return 0;
        
        int target = (1 << n) - 1;
        queue<tuple<int, int, int>> q; // node, mask, dist
        set<pair<int, int>> visited;
        
        // 初始化，每个节点都可以作为起点
        for (int i = 0; i < n; i++) {
            q.push({i, 1 << i, 0});
            visited.insert({i, 1 << i});
        }
        
        while (!q.empty()) {
            auto [node, mask, dist] = q.front();
            q.pop();
            
            for (int next : graph[node]) {
                int newMask = mask | (1 << next);
                if (newMask == target) {
                    return dist + 1;
                }
                
                if (visited.find({next, newMask}) == visited.end()) {
                    visited.insert({next, newMask});
                    q.push({next, newMask, dist + 1});
                }
            }
        }
        
        return -1;
    }
};

class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        n = len(graph)
        if n == 1:
            return 0
        
        target = (1 << n) - 1
        queue = collections.deque()
        visited = set()
        
        # 初始化，每个节点都可以作为起点
        for i in range(n):
            queue.append((i, 1 << i, 0))
            visited.add((i, 1 << i))
        
        while queue:
            node, mask, dist = queue.popleft()
            
            for next_node in graph[node]:
                new_mask = mask | (1 << next_node)
                if new_mask == target:
                    return dist + 1
                
                if (next_node, new_mask) not in visited:
                    visited.add((next_node, new_mask))
                    queue.append((next_node, new_mask, dist + 1))
        
        return -1

public class Solution {
    public int ShortestPathLength(int[][] graph) {
        int n = graph.Length;
        if (n == 1) return 0;
        
        int target = (1 << n) - 1;
        var queue = new Queue<(int node, int mask, int dist)>();
        var visited = new HashSet<(int, int)>();
        
        // 初始化，每个节点都可以作为起点
        for (int i = 0; i < n; i++) {
            queue.Enqueue((i, 1 << i, 0));
            visited.Add((i, 1 << i));
        }
        
        while (queue.Count > 0) {
            var (node, mask, dist) = queue.Dequeue();
            
            foreach (int next in graph[node]) {
                int newMask = mask | (1 << next);
                if (newMask == target) {
                    return dist + 1;
                }
                
                if (!visited.Contains((next, newMask))) {
                    visited.Add((next, newMask));
                    queue.Enqueue((next, newMask, dist + 1));
                }
            }
        }
        
        return -1;
    }
}

var shortestPathLength = function(graph) {
    const n = graph.length;
    if (n === 1) return 0;
    
    const target = (1 << n) - 1;
    const queue = [];
    const visited = new Set();
    
    // Start from each node
    for (let i = 0; i < n; i++) {
        const state = `${i}-${1 << i}`;
        queue.push([i, 1 << i, 0]);
        visited.add(state);
    }
    
    while (queue.length > 0) {
        const [node, mask, dist] = queue.shift();
        
        if (mask === target) {
            return dist;
        }
        
        for (const neighbor of graph[node]) {
            const newMask = mask | (1 << neighbor);
            const newState = `${neighbor}-${newMask}`;
            
            if (!visited.has(newState)) {
                visited.add(newState);
                queue.push([neighbor, newMask, dist + 1]);
            }
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n² × 2ⁿ)n 个节点，2ⁿ 种访问状态，每个状态最多转移到 n 个相邻节点
空间复杂度O(n × 2ⁿ)visited 集合和队列的存储空间，最多存储 n × 2ⁿ 个状态

相关题目