欧拉路径与欧拉回路算法：邮递员小王的一笔画地图

可视化演示

欧拉路径和欧拉回路是经过每条边恰好一次的路径和回路，Hierholzer算法可高效求解。本文讲解欧拉路径与回路... 切换模式查看不同维度。

基本概念：路口的度与一笔画

清晨，小王摊开古镇街道图，他要找一条路线，每条街只走一次，最后回到邮局。他发现，每个路口都连着几条街，有的路口连着三条街，有的连着两条。这个“连着几条街”的数字，正是图论里最朴素的度量——度。小王的直觉是：能不能一笔画，和这些度有很大关系。

把地图抽象成图 \(G=(V,E)\)，\(V\) 是路口集合，\(E\) 是街道集合。一段从某个路口出发、沿着街道走到另一个路口的连续轨迹，如果每条街道恰好被经过一次，就称为欧拉路径；如果还能回到出发路口，就是欧拉回路。这里的关键不是顶点出现几次，而是边不重复。

小王恍然大悟：他在意的是每一条街，而不是每个路口。欧拉路径，就是“每条街道恰好走过一次”的行走方案。

判定条件：连通是第一道门槛

小王发现，古镇被一条河隔成两个片区，两片之间没有桥。就算每个路口度数都正常，他也没法从东岸走到西岸。所以，判断一笔画之前，首先要确认地图是“连通的”——所有含街道的路口必须在一个连通块内，孤零零的空院子可以忽略不计。

在无向图中，每一条街道都会给两个端点的度各加 1。把所有路口的度加起来，恰好等于边数的两倍，这就是握手定理。于是，一个连通无向图存在欧拉回路，当且仅当每个顶点的度都是偶数。这个判据简洁又优雅，是小王判断自己能不能回邮局的黄金法则。

小王的结论是：先看地图是否连通，再数每个路口的街道数是否为偶数。两个条件都满足，他就能不重复地走完所有街道，回到邮局。

奇度顶点：入口和出口的秘密

小王继续研究，发现有些路口特别“别扭”：它们连着的街道数是奇数。比如一个三岔路口，无论从哪个方向进来，想要离开时总会发现少一条街。这类奇度顶点，就像一扇只能进不能出（或只能出不能进）的门。

图论里的判定规则更精确：如果一个连通图有 0 个奇度顶点，那么存在欧拉回路；如果有恰好 2 个奇度顶点，那么存在欧拉路径，而且这两个奇度顶点恰好是起点和终点；如果奇度顶点多于 2 个，则不存在欧拉路径，一笔画无解。

小王拿着地图数了一圈：如果只有两个“别扭”的路口，那就从一个奇度路口出发，从另一个奇度路口收工，正好完成一笔画。这条规律，是他规划邮路的第一张决策表。

Hierholzer算法：拆环再拼项链

小王发现，古镇的街道网很像一串项链：由好几个小环在路口处互相串在一起。他灵机一动，只要先走完一个环回到老地方，再插到另一个环里继续走，最后把所有环串成一条完整路线，不就完成了？这就是 Hierholzer 算法的核心思想——拆环、走环、拼环。

算法具体怎么做？从起点出发，选择一条还没走过的边就走，走完立刻删掉。走到某个路口发现无路可走时，就把这个路口压入栈中并回退，直到遇到一个还有未走边的路口，再从那里出发找新的子环。最终所有子环在公共顶点处拼接成完整欧拉回路。整个过程每条边只处理一次，时间复杂度为 \(O(E)\)。

小王把地图上的街道网拆成一堆小铁环，再一个一个串起来。Hierholzer 的栈，正是他手里那根穿项链的线。

Fleury算法：过桥前先看看能不能回来

小王走着走着，遇到了一座独木桥。他很清楚，如果提前过了这座桥，桥对岸的街道没走完，他就再也回不来了。所以每次选择下一条街道前，他都会问：这条街是不是桥？如果是桥，就尽量留到没有别的路可走时再过。

图论中，桥（割边）是指删除后会让图变得不连通的边。Fleury 算法每一步都优先选择非桥边，只有在没有选择时才过桥，从而保证剩余街道始终连通，最终一定能走完欧拉路径。代价是每一步都要判断桥边，算法复杂度为 \(O(E^2)\)。

小王把独木桥当作最后的退路，只要还能绕路，就绝不提前过桥。Fleury 的每次犹豫，都是对“回头路”的珍惜。

欧拉与哈密顿：走遍每条街 vs 走遍每间屋

小王后来听说，还有一个问题叫“旅行商问题”，要求访问镇上的每一户人家。他觉得这和自己的送信工作很像，但仔细一想又完全不同：邮递员要走的是一条条街道，而推销员要访问的是一户户人家。前者对应欧拉回路，后者对应哈密顿回路。

欧拉回路要求走遍图中每条边恰好一次；哈密顿回路要求经过每个顶点恰好一次。判定的难度也天差地别：欧拉回路只需检查度数和连通性，是多项式时间；哈密顿回路则是最著名的 NP 完全问题之一，至今没有快速算法。

小王终于明白，邮局和旅行社是两本账。想判断能不能回邮局，数街道；想走遍每个村庄，可能要算到天荒地老。

实际应用：从DNA到邮局

小王的邮递员日常，竟然在计算机科学里遍地开花。遇到“如何不重复走完所有街道”的问题，本质就是在找欧拉路径。儿童玩的“一笔画”游戏，正是欧拉路径在大众生活中的投影。而更严肃的应用，是 DNA 片段拼接。

在基因组组装中，测序仪会得到大量短的 DNA 片段。研究人员把 k-mer 当作边、k-1-mer 当作顶点，构建 de Bruijn 图，然后寻找一条覆盖所有边的欧拉路径，就能拼出完整序列。另一个经典应用是中国邮递员问题：街道可能必须重复走，需要先给奇度顶点配对补边，让全图变“欧拉化”，再求最短重复路线。

小王的邮递路线，一路延伸到基因测序实验室和物流调度中心。欧拉路径不仅是一笔画游戏，更是一张连接数学与现实世界的隐形地图。

AI 应用场景

Python 演示

from collections import defaultdict def hierholzer(edges):    """返回无向图的欧拉路径/回路顶点序列；不存在时返回 None。"""    adj = defaultdict(list)    for u, v in edges:        adj[u].append(v)        adj[v].append(u)     odd = [v for v, d in adj.items() if len(d) % 2]    if len(odd) not in (0, 2):        return None     start = odd[0] if odd else edges[0][0]    stack = [start]    path = []     while stack:        v = stack[-1]        if adj[v]:            u = adj[v].pop()            adj[u].remove(v)            stack.append(u)        else:            path.append(stack.pop())     path.reverse()    if len(path) - 1 != len(edges):        return None    return path if __name__ == '__main__':    # 两个三角形共用一个顶点，所有顶点度数都是偶数    edges = [(0, 1), (1, 2), (2, 0), (0, 3), (3, 4), (4, 0)]    route = hierholzer(edges)    print("欧拉回路:", route)

1. adj = defaultdict(list)给每个路口建一个“可走的街道列表”。
2. odd = [v for v, d in adj.items() if len(d) % 2]找出所有奇度路口，判断一笔画是否可能。
3. if len(odd) not in (0, 2): return None奇度顶点超过 2 个，直接判定无解。
4. start = odd[0] if odd else edges[0][0]若有两个奇度顶点，任选一个当起点；否则从任意路口出发。
5. u = adj[v].pop()从当前路口选择一条未走街道并删除，模拟“走过即划掉”。
6. adj[u].remove(v)无向图还要删掉反向的那条边，确保同一条街不会被走两次。
7. else: path.append(stack.pop())走不动时把路口记入路径，相当于拆下一个小环的端点。
8. if len(path) - 1 != len(edges): return None如果路径边数对不上，说明图不连通，返回无解。

常见误区

面试题