LeetCode-2608. 图中的最短环【广度优先搜索 图，腾讯面试真题】

题目描述：

现有一个含 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

题解参考

问：为什么说发现一个已经入队的点，就说明有环？

答：这说明到同一个点有两条不同的路径，这两条路径组成了一个环。

class Solution:def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:g = [[] for _ in range(n)]for x, y in edges:g[x].append(y)g[y].append(x) # 建图def bfs(start):ans = infdis = [-1] * n # dis[i] 表示从start到i的最短路径长度dis[start] = 0q = deque([(start, -1)])while q:x, fa = q.popleft()for y in g[x]:if dis[y] < 0: # 第一次遇到dis[y] = dis[x] + 1q.append((y, x))elif y != fa: # 第二次遇到ans = min(ans, dis[x] + dis[y] + 1)return ansans = min(bfs(i) for i in range(n))return ans if ans < inf else -1

时间复杂度：O(nm)
空间复杂度：O(n+m)

解题思路二：背诵版

class Solution:def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:g = [[] for _ in range(n)]for u, v in edges:g[u].append(v)g[v].append(u)def bfs(start):ans = infdis = [-1] * nq = deque([(start, -1)])dis[start] = 0while q:x, fa = q.popleft()for y in g[x]:if dis[y] < 0:dis[y] = dis[x] + 1q.append((y, x))elif y != fa:ans = min(ans, dis[x] + dis[y] + 1)return ansans = min(bfs(i) for i in range(n))return ans if ans < inf else -1

时间复杂度：O(nm)
空间复杂度：O(n+m)

解题思路三：

时间复杂度：O(n)
空间复杂度：O(n)

---

创作不易，观众老爷们请留步… 动起可爱的小手，点个赞再走呗 (๑◕ܫ￩๑) 欢迎大家关注笔者，你的关注是我持续更博的最大动力

原创文章，转载告知，盗版必究

---

---

---

♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠