当前位置：首页 > news >正文

Qwen模型 LeetCode 2608. 图中的最短环 Java实现

news 2026/5/25 0:36:40

哎呀，2608. 图中的最短环！这题可有意思了～我第一次做时也卡了好一会儿，后来发现用 **BFS 枚举每条边 + 临时删除** 的思路特别清爽！

### 🌟 核心思想：
- 对于每一条边 `(u, v)`，我们**暂时把它删掉**，然后从 `u` 出发 BFS 找到 `v` 的最短路径。
- 如果能找到，那么 `这条路径长度 + 1`（加回那条边）就是一个环的长度！
- 遍历所有边，取最小值就行啦～

> 💡 为什么不用 DFS？因为我们要**最短环**，BFS 天然保证第一次遇到就是最短路径！

---

### ✅ Java 实现（清晰 + 高效）

```java
import java.util.*;

public class Solution {
public int findShortestCycle(int n, int[][] edges) {
// 建图：邻接表
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] e : edges) {
graph.get(e[0]).add(e[1]);
graph.get(e[1]).add(e[0]);
}

int minCycle = Integer.MAX_VALUE;

// 枚举每一条边
for (int[] edge : edges) {
int u = edge[0], v = edge[1];

// 临时删除边 (u, v)
graph.get(u).remove(Integer.valueOf(v));
graph.get(v).remove(Integer.valueOf(u));

// 从 u 开始 BFS，找 v 的最短距离
int dist = bfs(u, v, graph, n);

if (dist != -1) {
minCycle = Math.min(minCycle, dist + 1); // +1 是加回被删的边
}

// 恢复边（其实也可以不恢复，但为了逻辑清晰）
graph.get(u).add(v);
graph.get(v).add(u);
}

return minCycle == Integer.MAX_VALUE ? -1 : minCycle;
}

// BFS 返回从 start 到 target 的最短距离，找不到返回 -1
private int bfs(int start, int target, List<List<Integer>> graph, int n) {
Queue<Integer> queue = new LinkedList<>();
int[] dist = new int[n];
Arrays.fill(dist, -1);

queue.offer(start);
dist[start] = 0;

while (!queue.isEmpty()) {
int u = queue.poll();
if (u == target) {
return dist[u];
}
for (int neighbor : graph.get(u)) {
if (dist[neighbor] == -1) {
dist[neighbor] = dist[u] + 1;
queue.offer(neighbor);
}
}
}
return -1;
}
}
```

---

### ⚠️ 注意细节

1. **删除边要用 `Integer.valueOf(v)`**
因为 `List.remove(int index)` 和 `List.remove(Object o)` 重载不同！直接传 `v` 会被当成下标，必须包装成 `Integer`。

2. **时间复杂度**
- 边数最多 1000（题目限制），每次 BFS 最多 O(n + m) ≈ O(1000)
- 总体 O(m × (n + m)) ≈ 1e6，完全 OK！

3. **为什么能保证是最短环？**
因为我们枚举的是**环上的一条边**，剩下的部分用 BFS 找最短路径，所以整体就是包含这条边的最短环。遍历所有边，自然得到全局最短环。

---

### 🧪 举个例子

比如图：`0—1—2—0`（三角形）
- 枚举边 (0,1)：删掉后，BFS 从 0 到 1 的路径是 `0→2→1`，长度 2 → 环长 = 3
- 其他边同理，最终答案就是 3 ✅

---

我超爱这种“暴力但聪明”的解法！虽然看起来是枚举，但利用了 BFS 的最优性，既简单又可靠～

你现在是在刷图论专题吗？这题和“无向图最小环”、“检测环”那些题都是一家子～要不要我再给你讲讲怎么用 Floyd 找最小环？（虽然这题用不上，但面试可能会问😉）

查看全文