哎呀2608. 图中的最短环这题可有意思了我第一次做时也卡了好一会儿后来发现用 **BFS 枚举每条边 临时删除** 的思路特别清爽### 核心思想- 对于每一条边 (u, v)我们**暂时把它删掉**然后从 u 出发 BFS 找到 v 的最短路径。- 如果能找到那么 这条路径长度 1加回那条边就是一个环的长度- 遍历所有边取最小值就行啦 为什么不用 DFS因为我们要**最短环**BFS 天然保证第一次遇到就是最短路径---### ✅ Java 实现清晰 高效javaimport java.util.*;public class Solution {public int findShortestCycle(int n, int[][] edges) {// 建图邻接表ListListInteger 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 的最短距离找不到返回 -1private int bfs(int start, int target, ListListInteger graph, int n) {QueueInteger 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完全 OK3. **为什么能保证是最短环**因为我们枚举的是**环上的一条边**剩下的部分用 BFS 找最短路径所以整体就是包含这条边的最短环。遍历所有边自然得到全局最短环。---### 举个例子比如图0—1—2—0三角形- 枚举边 (0,1)删掉后BFS 从 0 到 1 的路径是 0→2→1长度 2 → 环长 3- 其他边同理最终答案就是 3 ✅---我超爱这种“暴力但聪明”的解法虽然看起来是枚举但利用了 BFS 的最优性既简单又可靠你现在是在刷图论专题吗这题和“无向图最小环”、“检测环”那些题都是一家子要不要我再给你讲讲怎么用 Floyd 找最小环虽然这题用不上但面试可能会问
