图中的最短环
难度:
标签:
题目描述
There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1. The edges in the graph are represented by a given 2D integer array edges, where edges[i] = [ui, vi] denotes an edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.
Return the length of the shortest cycle in the graph. If no cycle exists, return -1.
A cycle is a path that starts and ends at the same node, and each edge in the path is used only once.
Example 1:
Input: n = 7, edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,6],[6,3]] Output: 3 Explanation: The cycle with the smallest length is : 0 -> 1 -> 2 -> 0
Example 2:
Input: n = 4, edges = [[0,1],[0,2]] Output: -1 Explanation: There are no cycles in this graph.
Constraints:
2 <= n <= 10001 <= edges.length <= 1000edges[i].length == 20 <= ui, vi < nui != vi- There are no repeated edges.
代码结果
运行时间: 52 ms, 内存: 16.8 MB
/*
题目思路：
1. 使用Stream API构建图的邻接表。
2. 采用广度优先搜索（BFS）查找最短环。
3. 使用OptionalInt来处理可能不存在环的情况。
*/
import java.util.*;
import java.util.stream.*;
public class ShortestCycleStream {
public int findShortestCycle(int n, int[][] edges) {
List<List<Integer>> graph = IntStream.range(0, n)
.mapToObj(i -> new ArrayList<Integer>())
.collect(Collectors.toList());
Arrays.stream(edges).forEach(edge -> {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
});
return IntStream.range(0, n)
.map(i -> bfs(i, graph, n))
.filter(len -> len != Integer.MAX_VALUE)
.min()
.orElse(-1);
}
private int bfs(int start, List<List<Integer>> graph, int n) {
int[] dist = new int[n];
Arrays.fill(dist, -1);
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
dist[start] = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neighbor : graph.get(node)) {
if (dist[neighbor] == -1) {
dist[neighbor] = dist[node] + 1;
queue.offer(neighbor);
} else if (dist[neighbor] >= dist[node]) {
return dist[neighbor] + dist[node] + 1;
}
}
}
return Integer.MAX_VALUE;
}
}
解释
方法:
这个题解首先利用了邻接表来表示图的结构。使用并查集来检测边的添加是否会形成环。如果在添加一条边时，该边连接的两个顶点已经在同一个集合中，说明添加这条边会形成一个环。然后，题解利用广度优先搜索（BFS）来寻找最短环。搜索从某个顶点开始，尝试找到通过该点的最短环。如果在过程中发现一个顶点已经访问过（即在当前BFS层次中再次访问），则可以计算形成环的长度。题解中逐个处理每条边，检查其是否形成环，并使用BFS确定环的最短长度。对于每个已经检测过的点，为了减少计算，会从图中断开其连接，避免重复计算。
时间复杂度:
O(n^3)
空间复杂度:
O(V + E)
代码细节讲解
🦆
在题解中，为何选择使用并查集来检测环的形成，这种方法与通过邻接表直接搜索环的方法相比有什么优势或劣势？
▷🦆
题解提到在检测到环后会‘断开已检测点的连接’，这样做的目的是什么？是否可能导致某些环被错误地忽略或未能检测到？
▷🦆
在使用BFS搜索最短环时，为什么要记录每个节点的访问距离，且在再次遇到已访问节点时立即计算环的长度？
▷🦆
题解中说明，如果dist[j] < d，则返回(dist[j] << 1 | 1)，这个表达式的意义是什么？如何理解这个计算过程？
▷