Hard

题目描述

给定一个包含 n 个顶点的双向图，每个顶点的标号从 0 到 n - 1。图中的边由给定的二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示顶点 ui 和 vi 之间的一条边。每对顶点之间最多只有一条边，且没有顶点与自身相连。

返回图中最短环的长度。如果不存在环，返回 -1。

环是指从某个节点开始，又回到该节点的路径，且路径中的每条边只使用一次。

示例 1：

输入：n = 7, edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,6],[6,3]]
输出：3
解释：最短的环是：0 -> 1 -> 2 -> 0

示例 2：

输入：n = 4, edges = [[0,1],[0,2]]
输出：-1
解释：图中不存在环。

约束条件：

  • 2 <= n <= 1000
  • 1 <= edges.length <= 1000
  • edges[i].length == 2
  • 0 <= ui, vi < n
  • ui != vi
  • 没有重复的边

解题思路

这道题要求找到图中的最短环，可以使用 BFS 来解决。

核心思路： 对于图中的每个顶点，从该顶点开始进行 BFS，寻找包含该顶点的最短环。

算法步骤：

  1. 构建邻接表表示图
  2. 对每个顶点进行 BFS：
    • 初始化距离数组，记录从起始点到各点的距离
    • 使用队列进行 BFS 遍历
    • 当遇到已访问的邻接点时，说明找到了环
    • 环的长度 = 当前距离 + 邻接点距离 + 1

关键点：

  • 需要跳过父节点，避免立即回到上一个节点造成的假环
  • 当发现环时，立即更新最小环长度
  • 使用 -1 表示未访问的节点

时间复杂度优化： 由于我们要找最短环，可以在找到当前环后进行剪枝，避免不必要的搜索。

代码实现

class Solution {
public:
    int findShortestCycle(int n, vector<vector<int>>& edges) {
        vector<vector<int>> graph(n);
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        
        int minCycle = INT_MAX;
        
        for (int start = 0; start < n; start++) {
            vector<int> dist(n, -1);
            vector<int> parent(n, -1);
            queue<int> q;
            
            dist[start] = 0;
            q.push(start);
            
            while (!q.empty()) {
                int u = q.front();
                q.pop();
                
                for (int v : graph[u]) {
                    if (dist[v] == -1) {
                        dist[v] = dist[u] + 1;
                        parent[v] = u;
                        q.push(v);
                    } else if (parent[u] != v) {
                        minCycle = min(minCycle, dist[u] + dist[v] + 1);
                    }
                }
            }
        }
        
        return minCycle == INT_MAX ? -1 : minCycle;
    }
};

class Solution:
    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:
        from collections import defaultdict, deque
        
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        
        min_cycle = float('inf')
        
        for start in range(n):
            dist = [-1] * n
            parent = [-1] * n
            queue = deque([start])
            dist[start] = 0
            
            while queue:
                u = queue.popleft()
                
                for v in graph[u]:
                    if dist[v] == -1:
                        dist[v] = dist[u] + 1
                        parent[v] = u
                        queue.append(v)
                    elif parent[u] != v:
                        min_cycle = min(min_cycle, dist[u] + dist[v] + 1)
        
        return min_cycle if min_cycle != float('inf') else -1

public class Solution {
    public int FindShortestCycle(int n, int[][] edges) {
        List<int>[] graph = new List<int>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        
        foreach (var edge in edges) {
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }
        
        int minCycle = int.MaxValue;
        
        for (int start = 0; start < n; start++) {
            int[] dist = new int[n];
            int[] parent = new int[n];
            Array.Fill(dist, -1);
            Array.Fill(parent, -1);
            
            Queue<int> queue = new Queue<int>();
            dist[start] = 0;
            queue.Enqueue(start);
            
            while (queue.Count > 0) {
                int u = queue.Dequeue();
                
                foreach (int v in graph[u]) {
                    if (dist[v] == -1) {
                        dist[v] = dist[u] + 1;
                        parent[v] = u;
                        queue.Enqueue(v);
                    } else if (parent[u] != v) {
                        minCycle = Math.Min(minCycle, dist[u] + dist[v] + 1);
                    }
                }
            }
        }
        
        return minCycle == int.MaxValue ? -1 : minCycle;
    }
}

var findShortestCycle = function(n, edges) {
    const graph = Array.from({ length: n }, () => []);
    
    for (const [u, v] of edges) {
        graph[u].push(v);
        graph[v].push(u);
    }
    
    let minCycle = Infinity;
    
    for (let start = 0; start < n; start++) {
        const dist = new Array(n).fill(-1);
        const parent = new Array(n).fill(-1);
        const queue = [start];
        dist[start] = 0;
        
        while (queue.length > 0) {
            const u = queue.shift();
            
            for (const v of graph[u]) {
                if (dist[v] === -1) {
                    dist[v] = dist[u] + 1;
                    parent[v] = u;
                    queue.push(v);
                } else if (parent[u] !== v) {
                    minCycle = Math.min(minCycle, dist[u] + dist[v] + 1);
                }
            }
        }
    }
    
    return minCycle === Infinity ? -1 : minCycle;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n × (n + m))对每个节点进行一次 BFS，每次 BFS 的时间复杂度为 O(n + m)
空间复杂度O(n + m)邻接表存储图需要 O(n + m) 空间，BFS 过程中的数组和队列需要 O(n) 空间

相关题目