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 0x3f3f3f3fint 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. 从每个顶点出发 BFSfor (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²)邻接表存储图所需的额外空间。