DeepSeek LeetCode 2608. 图中的最短环 C语言实现
解题思路
LeetCode 2608「图中的最短环」要求在无向图中找出最短环的长度，如果不存在环则返回 -1。BFS（广度优先搜索） 是解决这类问题最直观有效的方法，因为 BFS 天然适合在无权图中寻找最短路径。
核心思想：从每个顶点出发进行 BFS，记录每个节点的层数（即与起点的距离）。当 BFS 过程中遇到一个已经访问过的节点，且该节点不是当前节点的父节点时，就找到了一个环。环的长度等于 dist[x] + dist[y] + 1，其中 x 和 y 是 BFS 树中形成环的两个端点。
为什么这样能确保找到最短环？BFS 按层展开，第一次检测到的环一定是经过起点的最短环。由于我们枚举了所有起点，全局最优解必然出现在某次 BFS 中。只需遍历所有顶点作为起点，对每个起点跑一次 BFS，取所有环的最小值即可。
---
C语言实现
```c
#define MAXN 1005
#define INF 0x3f3f3f3f
int findShortestCycle(int n, int** edges, int edgesSize, int* edgesColSize) {
// 1. 构建邻接表
int** g = (int**)malloc(sizeof(int*) * n);
int* deg = (int*)calloc(n, sizeof(int));
for (int i = 0; i < n; i++) {
g[i] = NULL;
}
for (int i = 0; i < edgesSize; i++) {
int u = edges[i][0], v = edges[i][1];
deg[u]++;
deg[v]++;
g[u] = (int*)realloc(g[u], sizeof(int) * deg[u]);
g[v] = (int*)realloc(g[v], sizeof(int) * deg[v]);
g[u][deg[u] - 1] = v;
g[v][deg[v] - 1] = u;
}
int ans = INF;
// 2. 从每个顶点出发 BFS
for (int start = 0; start < n; start++) {
int* dist = (int*)malloc(sizeof(int) * n);
int* parent = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++) {
dist[i] = -1;
}
int* queue = (int*)malloc(sizeof(int) * n);
int* pqueue = (int*)malloc(sizeof(int) * n);
int front = 0, rear = 0;
dist[start] = 0;
parent[start] = -1;
queue[rear] = start;
pqueue[rear] = -1;
rear++;
while (front < rear) {
int u = queue[front];
int fa = pqueue[front];
front++;
for (int i = 0; i < deg[u]; i++) {
int v = g[u][i];
if (dist[v] == -1) { // 未访问：加入队列
dist[v] = dist[u] + 1;
parent[v] = u;
queue[rear] = v;
pqueue[rear] = u;
rear++;
} else if (v != fa && v != parent[u]) { // 已访问且不是父节点：发现环
int cycleLen = dist[u] + dist[v] + 1;
if (cycleLen < ans) {
ans = cycleLen;
}
}
}
}
free(dist);
free(parent);
free(queue);
free(pqueue);
}
// 3. 释放邻接表内存
for (int i = 0; i < n; i++) {
if (g[i] != NULL) {
free(g[i]);
}
}
free(g);
free(deg);
return ans == INF ? -1 : ans;
}
```
---
代码说明
1. 构建邻接表：遍历所有边，用 g 数组存储每个顶点的邻接点，deg 记录度数用于动态分配内存。
2. BFS 遍历：对每个起点 start 执行 BFS，使用 dist 记录到起点的距离，parent 记录父节点。当遇到已访问的邻接点 v 且 v 不是当前节点的父节点也不是祖父节点时，说明形成了一个环。
3. 环长计算：dist[u] + dist[v] + 1 是经过 start 的环的长度，取所有搜索结果的最小值。
4. 边界处理：如果 ans 保持初始值 INF，说明图中不存在环，返回 -1。
---
复杂度分析
· 时间复杂度：O(n²)，n 为顶点数量（n ≤ 1000）。对每个顶点执行一次 BFS，每次 BFS 复杂度为 O(n)，总体 O(n²) 在实际约束下可行。
· 空间复杂度：O(n²)，邻接表存储图所需的额外空间。