在无向图中寻找最短环

1. 概述

在本文中，我们将探讨如何在一个无向图中找出最短的环。这个问题在图论中很常见，常用于网络分析、图算法优化等领域。

我们将从问题定义开始，接着介绍一种基于深度优先搜索（DFS）的解决方案，并分析其实现逻辑与时间复杂度。

2. 问题定义

给定一个包含 V 个顶点和 E 条边的无向图 G，我们需要找出图中长度最短的环。所谓“环”，是指从一个顶点出发，经过若干个顶点后又回到起点的路径。

以下是一个示例图：

图中存在多个环：

1 → 2 → 3 → 5 → 4 → 1，长度为 5
1 → 2 → 3 → 4 → 1，长度为 4
3 → 4 → 5 → 3，长度为 3

因此，这个图中最短环的长度为 3。

3. 解决方案

3.1. 核心思想

本方案采用深度优先搜索（DFS）进行遍历。对于每个访问到的节点，我们记录其访问深度。当遇到已经访问过的节点且该节点不是当前节点的父节点时，说明我们找到了一个环，其长度为当前深度减去该节点之前记录的深度。

整个图中最短的环长度即为所有 DFS 调用中找到的最小值。

⚠️ 注意：我们跳过了对父节点的判断，否则会误将来回遍历边的情况当作环。

3.2. 算法实现

int shortestCycle = Integer.MAX_VALUE;
int[] depth;

int findShortestCycle(int[][] graph, int node, int parent, int currentDepth) {
    if (depth[node] != -1) {
        return currentDepth - depth[node];
    }

    depth[node] = currentDepth;
    int minCycle = Integer.MAX_VALUE;

    for (int neighbor : graph[node]) {
        if (neighbor != parent) {
            int cycleLength = findShortestCycle(graph, neighbor, node, currentDepth + 1);
            minCycle = Math.min(minCycle, cycleLength);
        }
    }

    return minCycle;
}

参数说明：

graph：图的邻接表表示
node：当前访问的节点
parent：当前节点的父节点（用于避免回溯）
currentDepth：当前 DFS 的深度
depth：记录每个节点访问深度的数组，初始值为 -1

✅ 调用示例：

depth = new int[V]; // V 为图中节点总数
Arrays.fill(depth, -1);
int result = Integer.MAX_VALUE;

for (int i = 0; i < V; i++) {
    if (depth[i] == -1) {
        int cycleLength = findShortestCycle(graph, i, -1, 0);
        result = Math.min(result, cycleLength);
    }
}

System.out.println("最短环长度为：" + result);

3.3. 时间与空间复杂度分析

✅ 时间复杂度：O(V + E)
每个节点最多被访问两次，每条边最多被访问一次。
✅ 空间复杂度：O(V)
主要用于存储每个节点的访问深度。

4. 小结

本文介绍了如何在无向图中找出最短环的问题。通过 DFS 遍历并记录节点访问深度，我们可以在合理的时间复杂度内高效求解该问题。

虽然这个算法看似简单，但在实际编码过程中需要注意以下几点：

避免将边的来回访问误判为环
多次调用 DFS 以覆盖所有连通分量
初始化 depth 数组，确保每个节点都未被访问过

掌握这些技巧，可以有效避免踩坑。

Persistence

REST

Security