本文详解欧拉回路（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]
注意事项：
- 此实现返回顶点序列（长度为边数+1），相邻顶点构成一条边，首尾顶点自动闭合；
- 时间复杂度为 O(E)，每条边仅被访问和删除一次；
- 若图不连通但满足度数条件，算法可能只返回某连通分量的回路——实际应用中建议先做连通性检查；
- 对有向图，需验证每个顶点入度等于出度，并调整邻接表为有向映射。
掌握 Hierholzer 算法的核心思想——“深度优先走到底，回溯时记录，遇岔路则绕行插入”——才能真正理解欧拉回路的构造本质，而非陷入边拼接的逻辑泥潭。
