当前位置：首页 > 文章列表 > 文章 > python教程 > 欧拉回路算法实现与避坑指南

欧拉回路算法实现与避坑指南

2026-04-21 22:54:58 0浏览收藏

本文深入剖析欧拉回路实现中极易被忽视却致命的三大陷阱：可变默认参数引发的状态污染、嵌套列表拼接导致的结构错乱，以及忽略“绕道插入”本质而错误追加子路径的逻辑缺陷；通过对比问题代码与基于邻接表+双端队列的Hierholzer标准实现，清晰揭示算法核心在于“走到底、回溯记录、遇未访问边则旋转定位插入点”，不仅提供生产就绪的高效O(E)解决方案，更帮你穿透表象、真正掌握欧拉回路构造的数学直觉与工程细节。

如何正确实现欧拉回路算法：避免常见陷阱与高效构造路径

本文详解欧拉回路（Eulerian Circuit）的正确实现方法，指出原代码中可变默认参数、嵌套列表拼接、插入位置错误等关键问题，并提供基于邻接表与双端队列的健壮解决方案。

本文详解欧拉回路（Eulerian Circuit）的正确实现方法，指出原代码中可变默认参数、嵌套列表拼接、插入位置错误等关键问题，并提供基于邻接表与双端队列的健壮解决方案。

欧拉回路要求图中所有顶点度数为偶数，且图连通。原代码试图通过递归遍历边并“拼接”多个子回路来构造完整回路，但存在多个根本性缺陷：

首先，def circuit(current, path=[]): 中使用可变对象 [] 作为默认参数是危险的——该列表在函数定义时仅创建一次，后续所有调用共享同一对象，导致状态污染。应改为 path=None 并在函数内初始化：if path is None: path = []。

其次，path.append(circuit(...)) 会将整个子路径列表作为单个元素追加，造成嵌套结构（如 [1,2,3,[4,5,6]]），而非扁平化序列。正确做法是使用 path.extend(...) 或直接拼接。

最关键的是逻辑错误：欧拉回路的“回路拼接”并非简单追加，而需在当前回路中找到一个仍关联未访问边的顶点，将新回路从该点处展开插入（即“绕道扩展”）。原代码遍历 path 查找匹配顶点后直接追加，完全忽略了插入位置，破坏了边的连续性。

更优解法是采用 Hierholzer 算法 的标准实现：

预处理构建无向图邻接表（defaultdict(set)），支持 O(1) 边删除；
使用 deque 存储顶点序列，利用 .rotate() 快速定位插入点；
主循环中，若当前顶点无剩余邻边，则沿已生成回路旋转查找首个仍有未用边的顶点，以此为新起点继续延展。

以下是生产就绪的实现：

from collections import defaultdict, deque

def create_graph(edges):
    adj = defaultdict(set)
    for a, b in edges:
        adj[a].add(b)
        adj[b].add(a)
    return adj

def has_euler_circuit(adj):
    if not adj:
        return False
    return all(len(neighbors) % 2 == 0 for neighbors in adj.values())

def find_euler_circuit(edges):
    if not edges:
        return []

    adj = create_graph(edges)
    if not has_euler_circuit(adj):
        raise ValueError("Graph does not have an Eulerian circuit (some vertices have odd degree)")

    # 任选起始顶点（保证图连通的前提下）
    start = edges[0][0]
    circuit = deque()
    stack = [start]

    while stack:
        node = stack[-1]
        if adj[node]:
            # 取出一个邻居并删除双向边
            neighbor = adj[node].pop()
            adj[neighbor].remove(node)
            stack.append(neighbor)
        else:
            # 当前节点无出边，加入最终回路
            circuit.appendleft(stack.pop())

    return list(circuit)

# 测试用例
verts = [(1, 2), (2, 3), (1, 6), (6, 5), (5, 3), (6, 3), (2, 5), (5, 4), (3, 4), (6, 2)]
result = find_euler_circuit(verts)
print("Euler Circuit (vertices):", result)
# 输出示例: [1, 2, 5, 4, 3, 6, 2, 3, 5, 6, 1]

注意事项：