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

【每日力扣中医养生】力扣2608. 图中的最短环

news 2025/12/2 19:10:23

2608. 图中的最短环

文章目录

【每日力扣&中医养生】力扣2608. 图中的最短环
题目描述
示例
示例 1
示例 2

输入输出说明
解题思路
Python代码
复杂度分析
总结

【每日力扣&中医养生】力扣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]]

输出：

解释：

最短的环是 0 -> 1 -> 2 -> 0，长度为 3。

示例 2

输入：

n = 4
edges = [[0, 1], [0, 2]]

输出：

-1

解释：

图中不存在环。

输入输出说明

输入：
- 整数 n，表示图中的顶点数。
- 二维整数数组 edges，表示图中的边。
输出：
- 返回最短环的长度，若不存在环，则返回 -1。

解题思路

为了解决这个问题，我们可以采用 广度优先搜索（BFS） 算法。具体思路如下：

图的表示： 使用邻接表来表示图结构。将所有的边记录下来，并为每个节点创建一个邻接表。
BFS搜索： 对于每个节点，以该节点为起点进行广度优先搜索，检测是否存在环。具体来说，我们从一个节点出发，遍历与其直接相连的节点。对于相邻节点，如果相邻节点未访问过，则继续向下遍历；如果相邻节点已经访问过且不是父节点（不存在两个点的环），则说明从start到相邻节点，还有从start到当前节点的最短距离都已经有了，那么就能计算出对应的环的最短长度。
更新最短环： 在每次找到一个环时，更新当前已知的最短环的长度。
特殊情况处理： 如果最终没有找到任何环，则返回 -1。

Python代码

class Solution:def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:# 邻接表，建图graph = [[] for _ in range(n)]for x, y in edges:graph[x].append(y)graph[y].append(x)def bfs(start):# 记录从start出发，到达各点的最短的距离distance = [-1] * ndistance[start] = 0# 记录最短的环长度res = inf# 队列中，按照[当前节点，父节点]为一组queue = deque([[start, -1,]])while queue:cur, fa = queue.popleft()for nxt in graph[cur]:# 如果到达nxt的最短距离还没计算，则说明未访问过nxtif  distance[nxt] == -1:distance[nxt] = distance[cur] + 1queue.append([nxt, cur])# 如果访问过nxt，且nxt不为父节点（两个点不能构成环）# 则考虑是否为最短环elif nxt != fa:res = min(res, distance[cur] + distance[nxt] + 1)return resans = min((bfs(i) for i in range(n)))if ans != inf:return anselse:return -1

复杂度分析

时间复杂度：
- 构建邻接表的时间复杂度为 $O (E)$ ，其中 $E$ 是边的数量。
- 对每个节点执行 BFS 的时间复杂度为 $O(V^2)$ ，其中 $V$ 是节点的数量。
空间复杂度：
- 需要存储邻接表，占用 $O(V^2)$ 的空间，最坏情况下是稠密图。
- BFS 队列和距离数组的空间复杂度为 $O (V)$ 。
- 因此，空间复杂度为 $O (V + E)$ 。