无向无权重图环检测代码异常排查：错误短环与大量重复结果

我正在尝试以[节点,节点]格式检测无向无权重图中的环，编写了如下Python代码：

def find_cycles(graph):
    cycles = []

    def dfs(node, visited, path):
        visited.add(node)
        path.append(node)

        neighbors = graph.get(node, [])

        for neighbor in neighbors:
            if neighbor in visited:
                # Cycle detected
                start_index = path.index(neighbor)
                cycle = path[start_index:]
                if cycle not in cycles:
                    cycles.append(cycle)
            else:
                dfs(neighbor, visited, path)

        visited.remove(node)
        path.pop()

    for node in graph.keys():
        dfs(node, set(), [])

    return cycles

graph = {
    # 'node': ['adjacent'],
}

n, m = map(int, input().split())

for _ in range(m):
    a, b = map(int, input().split())
    if b not in graph:
        graph[b] = []
    if a not in graph:
        graph[a] = []

    if a not in graph[b]:
        graph[b].append(a)
    if b not in graph[a]:
        graph[a].append(b)

ans = find_cycles(graph)
print(ans)
print(len(ans))

使用如下测试用例：

10 10
3 6
9 3
1 7
1 2
4 7
7 6
2 9
2 6
3 4
6 0

已知该测试用例中最短环长度为4，但代码输出了包含92个元素的错误列表，其中最短环长度为2。请问我的代码存在什么问题？

核心问题分析 #

• 误判直接边为环：无向图中两个节点的相邻边会被错误识别为环。比如节点A和B相连，DFS遍历到B时，发现邻居A在已访问集合中，就会生成[A,B,A]这类路径并判定为环，但这只是一条边，不是真正的环（无向图的环至少需要3个节点）。
• 重复检测同一环：代码会从每个节点出发启动DFS，同一个环会被多次检测到——比如环3-6-2-9-3会从3、6、2、9四个节点分别出发各被检测一次，甚至还会生成反向的同环（如6-2-9-3-6），导致结果中存在大量重复项。
• 未排除父节点干扰：DFS过程中未记录父节点（即上一步到达当前节点的节点），只要遇到已访问的节点就判定为环，而父节点本来就属于已访问集合，这是误判直接边的根本原因。

修正方案 #

关键调整点 #

1. 跳过父节点：在DFS函数中增加父节点参数，遍历邻居时直接跳过父节点，避免把相邻边误判为环。
2. 标准化环去重：将检测到的环标准化（比如旋转到以最小节点开头，同时处理反向环的情况），用集合存储标准化后的环，自动去重。
3. 过滤短环：直接排除长度小于3的路径，确保只保留真正的环。

修正后代码 #

def find_cycles(graph):
    cycles = set()  # 用集合存储标准化后的环，自动去重

    def dfs(node, visited, path, parent):
        visited.add(node)
        path.append(node)

        neighbors = graph.get(node, [])
        for neighbor in neighbors:
            if neighbor == parent:
                continue  # 跳过父节点，避免误判直接边
            if neighbor in visited:
                # 提取环并标准化
                start_idx = path.index(neighbor)
                cycle = path[start_idx:]
                if len(cycle) >= 3:
                    # 标准化：将环旋转到以最小节点开头
                    min_node = min(cycle)
                    idx = cycle.index(min_node)
                    normalized = tuple(cycle[idx:] + cycle[:idx])
                    # 处理反向环，确保同环只存一种形式
                    reversed_normalized = tuple(reversed(normalized))
                    cycles.add(normalized if normalized < reversed_normalized else reversed_normalized)
            else:
                dfs(neighbor, visited, path, node)

        visited.remove(node)
        path.pop()

    for node in graph.keys():
        dfs(node, set(), [], -1)  # 初始父节点设为不存在的标识

    return [list(cycle) for cycle in cycles]

# 输入读取部分保持不变
graph = {}
n, m = map(int, input().split())
for _ in range(m):
    a, b = map(int, input().split())
    if a not in graph:
        graph[a] = []
    if b not in graph:
        graph[b] = []
    if b not in graph[a]:
        graph[a].append(b)
    if a not in graph[b]:
        graph[b].append(a)

ans = find_cycles(graph)
print(ans)
print(len(ans))

修正效果 #

运行测试用例后，结果中将不再出现长度为2的错误环，所有环都是真正的无向图环，且每个环只会被记录一次。此时可以正确找到最短长度为4的环，结果列表的长度也会大幅减少。

内容的提问来源于stack exchange，提问作者Mani