说到欧拉图多数人第一反应是柯尼斯堡七桥问题但真正动手建模、写代码验证欧拉路径时遇到的细节远不止“数一数奇度点”那么简单。这篇文章我从欧拉图的底层判定条件讲起再到两种构造欧拉路径的算法最后聊聊当图不是欧拉图时的工程补救方案属于一篇能直接抄作业的实操向笔记。适合刚接触图论的学生、准备算法面试的开发者以及需要在路线规划类项目里使用欧拉路径的工程师参考。1. 从七桥问题说起欧拉图到底在解决什么问题1.1 柯尼斯堡七桥的图论建模1736年欧拉面对的是这样一个生活化的问题柯尼斯堡城里有两条河汇合河中有两座小岛七座桥连接着岛屿和两岸的陆地。当地流传着一个趣味谜题——能不能设计一条散步路线让人们从某块陆地出发每座桥恰好经过一次最后回到出发点很多人在纸上画了半天始终找不到答案却说不清为什么找不到。欧拉做的第一件事就是把桥和陆地抽象成简洁的数学结构把每块陆地当成一个点把每座桥当成连接两个点的一条边。这就是现代图论里“图”的最初模样。四块陆地变成四个顶点七座桥变成七条边问题随之转化为一个更纯粹的数学命题这个由四个点和七条边组成的图是否存在一条经过每条边恰好一次又回到起点的闭合路线这个转换看似简单却改变了问题的性质把空间散步变成了纯粹的拓扑判断。你不再需要关心陆地的面积、桥的长度只需要关心连接关系。欧拉最终给出了否定答案同时提出了这一大类问题的完整理论也就是欧拉图和欧拉路径的雏形。今天我们把“经过每条边恰好一次”的路径称为欧拉路径把能回到起点的闭合版本称为欧拉回路而把存在欧拉回路的图称为欧拉图。1.2 欧拉路径、欧拉回路与欧拉图的区分这三个词在中文资料里经常混用实际含义差别很大尤其是面试或写论文时概念不清很容易闹笑话。我先把定义列清楚术语定义对图的要求欧拉路径经过每条边恰好一次的开放路径不要求回到起点欧拉回路经过每条边恰好一次的闭合路径必须回到起点欧拉图存在欧拉回路的图拥有闭合欧拉路径半欧拉图存在欧拉路径但不存在欧拉回路的图开放路径举个例子一个“日”字形的图形你能不抬笔、不重复地画出它但不能回到起点这就是半欧拉图一个正方形加两条对角线在某些情况下可以画成一笔闭合回路那就是欧拉图。工程里我们更多关心欧拉图因为很多巡航、巡检类任务要求设备从驻点出发遍历全部目标路段后回到驻点补能这种情况下闭合回路是刚需。判断一个图是否为欧拉图看似只需要数一下顶点度数实际落地时还要考虑图是否连通、孤立点怎么处理、有向图怎么办。这些问题我放在后文一一展开。2. 判定条件为什么成立度数、奇偶点与一笔画直觉2.1 顶点的度数到底意味着什么“度数”是理解欧拉图的第一把钥匙。无向图中一个顶点的度数就是连接到它身上的边的数量。你可以把它想象成一个中转站的进出通道数每次经过这个顶点必然是从一条边进来、从另一条边出去也就是一次“路过”会消耗掉该顶点的两条边。如果我们要构造一条经过所有边恰好一次的闭合路线那么每个顶点被“路过”的次数乘以二就等于它拥有的边数。这样一想每个顶点的度数必须是偶数这个结论就非常自然了。如果某个顶点的度数是奇数说明它至少有一次是“只进不出”或者“只出不进”的在闭合路线里这是不可能的。这个“进出配对”的视角比死记硬背“所有顶点度数为偶数”要有用得多。我之前辅导过一些学生他们能把定理倒背如流但遇到一个包含孤立零度点的图就懵了。实际上零度点不参与任何路径它存在与否不影响欧拉回路的判定关键是看非零度点所在的连通分量是否满足条件。2.2 无向图所有顶点度数为偶数才有回路无向图欧拉回路的存在定理其实包含两个条件一是所有非零度顶点的度数都为偶数二是所有非零度顶点必须在同一个连通分量里。第一条保证“每一步都有路可走”第二条保证“所有边能被一次性串起来”。为什么度数为偶数就一定存在回路一种理解方式是归纳构造从任意一个非零度顶点出发沿着没用过的边一直走由于每个顶点度数都是偶数只要进入某个顶点就一定能找到一条未用过的边离开除非回到起点。最终你会得到一个闭合回路。如果这个回路已经覆盖了所有边就完成了如果没有就把这个回路上的某个顶点作为“换乘点”从那里出发在剩余的子图里再找新的闭合回路然后拼接到原回路上。重复这个过程所有边最终都会被纳入同一条欧拉回路。单开路径的情况略有不同当图里恰好有两个顶点的度数为奇数时这两个奇度点就是路径的两个端点其余顶点度数仍为偶数。原因是开放路径的两个端点在处理时相当于“多了一条边”或者“少了一条边”从而把所有偶数度顶点变成奇数度顶点。2.3 有向图出入度条件要背牢有向图的情况更严格。整条路径是有方向性的路径上的每条边都有一个固定的走向因此每个顶点都要满足一个类似“收支平衡”的条件。对于存在欧拉回路的有向图每个顶点的入度必须等于出度也就是进入这个顶点的边的数量和离开这个顶点的边的数量必须完全一致。这就像记账收入多少就得支出多少否则某一笔账会卡死。对于存在欧拉路径但不一定闭合的有向图则放宽为一个顶点可以出度比入度多1作为起点一个顶点可以入度比出度多1作为终点其余所有顶点的出入度要相等。注意最多只能有一个“起点型”顶点和一个“终点型”顶点。如果出现了两个以上不平衡的顶点那就没有欧拉路径。有向图的连通性检查也很关键不是看强连通而是看“忽略方向后的弱连通”。也就是说把有向边当成无向边来看所有非零度顶点要连成一片。只有出入度条件配合连通性条件都成立才能断言存在欧拉路径。2.4 容易被忽略的边界孤立点孤立点是欧拉图判定里最容易翻车的地方。严格说一个图只要有一个非零度顶点同时又有一个度数为零的孤立顶点依然可以被判定为欧拉图因为欧拉回路本来就不需要经过孤立点。有些教材在描述定理时会说“图连通”这里的“图连通”容易让人误解为整个图包括孤立点在内必须全连通实际上应该理解为“所有非零度顶点互相连通”。我把这一点单独拿出来是因为真有一批人在写代码时用全局连通性做判断结果把一个本来是欧拉图的图给否定了。更隐蔽的错误出现在“多个连通分量”的检查上。比如一个图有两块互不连通的子图每块子图都各自满足欧拉回路条件但整个图不是欧拉图因为你不可能通过一条路径跨越两个分量。这时候应该报“不属于欧拉图”而不是误判为欧拉图。3. 实战用两种算法构造欧拉路径3.1 Fleury算法走一步看一步的保守策略判定一个图是否为欧拉图之后下一步就是把这个路径真的构造出来。最早出现且最符合直觉的算法是Fleury算法它的策略非常像“过河怕桥塌”每一步在选择下一条边之前先判断这条边是不是当前剩余子图中的桥。如果一条边是桥也就是删掉它会把剩余图分成两个不连通的部分那就尽量别走它除非没有其他选择。这个策略的核心思想是走完这条边之后不能让剩余的边变得不可达否则路径就断了走不完。Fleury算法的复杂度大约是O(E²)因为每走一条边都要重新判断一次“桥”的性质而判断桥又需要遍历当前剩余子图。这种做法教学意义很强但放到工程项目里不太划算尤其当图的边数上万时平方复杂度会很吃力。不过它的可解释性特别好用来验证自己的思路非常合适。一个值得注意的细节是如果当前顶点有一条非桥的边就应该优先走非桥的边只有当所有可选边都是桥时才不得不走桥。这保证了路径不会在某个局部把自己走进死胡同。3.2 Hierholzer算法贪心拼环主流高效做法真正在实际工程里常用的是复杂度为O(E)的Hierholzer算法。我第一次看到这个算法的时候觉得它有点“不讲武德”不管三七二十一先随便走能走多远走多远直到走回起点得到一个闭合环路然后检查这个环路上还有没有剩余边的顶点如果有就从那个顶点出发再找一个新的环路把它插进旧环路里。这样把多个小环路拼接起来最终就得到覆盖全部边的欧拉回路。书面描述听着抽象写成代码其实非常简短。我用Python实现了一个通用版本支持有向图和无向图核心逻辑就一个栈def hierholzer(adj, directedFalse): # adj: 邻接表建议用列表存储每个顶点的邻居 # directed: True 表示有向图False 表示无向图 edge_count 0 n len(adj) if directed: in_deg [0] * n out_deg [0] * n for u in range(n): out_deg[u] len(adj[u]) for v in adj[u]: in_deg[v] 1 edge_count 1 odd [i for i in range(n) if (in_deg[i] out_deg[i]) % 2 1] start odd[0] if odd else 0 else: for u in range(n): edge_count len(adj[u]) odd [i for i in range(n) if len(adj[i]) % 2 1] start odd[0] if odd else 0 # 如果有超过两个奇度顶点肯定没有欧拉路径 if len(odd) 2: raise ValueError(图中不存在欧拉路径) # 从孤立点中挑一个非零度顶点作起点 for i in range(n): if len(adj[i]) 0: start i break # 复制邻接表因为算法会修改它 local_adj [lst[:] for lst in adj] stack [start] path [] while stack: u stack[-1] if local_adj[u]: v local_adj[u].pop() if not directed: # 无向图需要删除反向边避免重复访问 local_adj[v].remove(u) stack.append(v) else: path.append(stack.pop()) # path 是逆序的所以反转 path.reverse() # 边数量检查如果路径边数不等于图中边数说明图不连通 if len(path) - 1 ! edge_count // (1 if directed else 2): raise ValueError(图不连通或存在无法覆盖的边) return path代码里有两个小地方我特别说明一下。第一孤立点处理如果图中存在零度顶点我在代码里先选中一个非零度顶点作为起点这样就避免了从孤立点出发的空转。第二边数检查构造出来的路径经过的边数必须等于原图的边数否则说明有些边属于其他连通分量这种情况下直接报错比返回一条残缺路径更安全。3.3 代码测试用非欧拉图和欧拉图验证算法光说不练不行我随手构造两个图验证上面的代码。先看一个经典的半欧拉图四个顶点四条边分别是0-1、1-2、2-3、3-0。这是一个正方形每个顶点度数都是2属于欧拉图上面的函数应该能输出一条覆盖四条边的回路。再看一个关键测试图里有0-1、1-2、2-0这三条边形成三角形另外还有一个单独顶点3以及一条从2到3的边。顶点3的度数是1顶点0和1的度数都是2顶点2的度数是3。奇度顶点有两个2和3因此存在欧拉路径起点是2终点是3但不一定是闭合回路。用上面的代码跑能正确得到类似[2, 0, 1, 2, 3]的路径覆盖了所有四条边。我建议你自己动手测试时多准备几种构造全偶度数的连通图、恰好两个奇度顶点的连通图、包含孤立点的图、有多个连通分量的图、有向图。把这些边界情况都跑一遍才算是真正吃透了欧拉路径的判定与构造而不是停留在“读过算法”的层面。4. 当图不是欧拉图中国邮递员问题与工程化补救4.1 中国邮递员问题的由来现实中我们遇到的图不一定是欧拉图。最经典的场景是邮递员送信从邮局出发把一条街区的每条街道至少走一遍最后回到邮局问怎么走总路程最短。这个问题最早由中国学者管梅谷先生在1962年提出后来国际上称为中国邮递员问题Chinese Postman ProblemCPP。这里的难点在于街区道路组成的图往往包含奇度顶点而欧拉回路条件要求所有顶点度数为偶数。于是核心思路变为用某种方式补齐那些缺失的“配对”把奇度顶点变成偶度顶点再用欧拉回路算法求解。补边的本质就是找出哪些街道需要额外走一遍比如把两点之间的距离最短路当作添加边。具体操作分两步。第一步找出图中所有奇度顶点显然奇度顶点的数量一定是偶数。第二步在奇度顶点之间进行配对使得每一对之间那条最短路径的总长度之和最小。配对完成后把这若干条最短路上的每条边复制一份加到原图里此时新图的每个顶点度数都变成偶数。然后在新图上找欧拉回路得到的路线就是这样规定的“每条边至少走一次且总路程最短”的最优解。4.2 实际应用路线规划和硬件遍历中国邮递员问题的思路早已不只是邮递员专用。环卫垃圾清运车的路线规划、电力线路巡检员的巡检路径、景区导览路线的设计本质上都是在处理“如何才能不重复或少重复地走完所有目标路段”的问题。只要目标路段可以被抽象成图上的边优化目标是最小化总里程这类问题都能用欧拉图模型递推过去。另一个非常有意思的应用是数控机床的钻孔路径规划。一块电路板上要钻几千个孔钻头需要从一个孔移动到另一个孔。如果把每个孔当顶点把钻头从某个孔到另一个孔的空走过程当边就会发现设计一条尽量不重复空走路径的问题本质上就是在一个完全图中寻找欧拉路径或最小权重的闭合遍历路径。这些场景里欧拉图不是“最多只能画一笔”的数学游戏而是直接关系到生产效率的硬核工具。DNA测序里的de Bruijn图拼接也是欧拉路径的经典应用。测序仪产生的短序列片段被切割成更小的k-mer然后以k-mer为顶点、以相邻k-mer的重叠关系为边构造de Bruijn图接下来程序需要在这个巨型有向图中找一条能覆盖所有相关边的路径也就是欧拉路径。这个领域对算法的性能要求很高大规模的有向图欧拉路径求解在很多基因组组装工具里都是核心环节。4.3 有向欧拉图的特殊之处有向图和无向图在工程实践中的选择差异很大。像道路清扫这类任务道路本身是双向可通的用无向图建模更自然但在某些单向通行的道路网络、轨道交通调度、任务依赖关系里方向是强约束只能用有向图建模。有向图的欧拉回路条件“所有顶点入度等于出度”在代码里很好检查但在实际路网里却容易因为单行线导致某个顶点的出入度失衡。解决这类问题时有两个常用技巧。一是尽量在建模阶段避免奇度顶点的出现比如把某些单向街道临时改为双向通行但这要结合实际交通法规。二是接受偶发的不平衡用中国邮递员问题的思路补边。我在实际项目中倾向于先用无向图简化建模等确认最优路线后再把单向约束作为附加条件逐条验证这样能在第一轮快速得到一个可用解而不是一上来就被有向性卡住。5. 常见问题速查验证欧拉图时的坑5.1 为什么图明明“欧拉”却画不出路径这是最常见的困惑。很多人拿到一个顶点度数全部为偶数的图就开始尝试一笔画画到一半卡住了。原因大概率在于图并不满足连通性条件。比如一个图分成两个独立部分每个部分内部都是全偶度但两部分之间没有边这时你永远无法通过一条路径串完两边。另一个常见情况是图里存在一些零度点代码在找起点时没有跳过这些点导致一开始就站在一个没有任何边的顶点上算法直接输出空路径。我的建议是在验证代码逻辑之前先手动打印出每个顶点的度数和连通分量数量把这两个基础信息确认一遍再跑算法。遇到“明明条件都满足但输出不对”的情况还有一个隐蔽问题无向图的邻接表里一条边会被存两次。使用Hierholzer算法时如果只删正向边而忘记删反向边可能会导致路径提前终止或反复走同一条边。这是典型的实现细节错误排查方法是在每次删边后统计当前剩余边数对比原图边数看看差异是否按预期减少。5.2 有向图的连通性检查与出入度记忆法有向图的连通性检查经常被人忽视。一些人只验证了出入度条件却忘了检查底层的弱连通结果代码跑出来的“欧拉路径”可能根本覆盖不到所有边。正确顺序应该是先验证所有非零度顶点的弱连通性再验证出入度条件最后用算法构造路径。弱连通的检查方式很简单把每条有向边当成无向边从任意一个非零度顶点做一次深度优先搜索或者广度优先搜索统计访问到的非零度顶点数量是否等于全集。关于出入度条件的记忆我提供一个比死记更牢的口诀“回路要平账路径只允许一个欠账、一个赊账”。也就是说欧拉回路要求每个顶点的入度等于出度账目全平欧拉路径允许最多一个顶点出度比入度多1另一个顶点入度比出度多1其余顶点仍需要平账。一旦理解了记账的比喻再也不会把有向图的优先级搞混。5.3 常见误区速查表我整理了一张表格把平时最容易踩的坑集中列出来方便你在实际验证时对照自查。误区正确理解图有多个连通分量但每个分量都是欧拉图就断言整图是欧拉图欧拉回路必须覆盖所有边多个分量之间无法通过一条路径跨越孤立点会导致欧拉图判定失败孤立点不参与路径只需忽略零度点后再判断有向图只要出入度平衡就存在欧拉回路还要求所有非零度顶点弱连通无向图中删边后只删邻接表一端的边无向图的每条边在邻接表里出现两次两端都要同步删除存在欧拉路径的图一定是欧拉图欧拉路径是开放性路径只有闭合版本才是欧拉图度数为奇数就一定没有欧拉路径恰好两个奇度顶点时存在开放型欧拉路径它们是起点和终点这张表是我在做代码评审时最常用的检查清单。每一条都是真实踩过的坑尤其是第五行经常有初学者混用“欧拉图”和“欧拉路径”的概念导致后续设计和实现走错方向。6. 最后分享一个判断技巧我每次遇到“一笔画”类型的谜题第一反应就是数奇度顶点。如果奇度顶点数量是0可以一笔画成闭合回路起点终点重合如果奇度顶点数量是2可以一笔画成开放路径起点和终点落在这两个奇度顶点上只要奇度顶点数量超过2就不可能一笔画成功。这个方法不仅适用于纸上谜题在规划景区游览路线、设计室内参观动线时同样能用上。在实际的编码经历中我发现很多看上去复杂的问题只要把顶点和边的语义定义清楚最后都会落到欧拉图判定这件小事上。比如有一条观光小火车路线要求所有轨道都至少通过一次最后回到车站这个问题本质上就是中国邮递员问题的无向版本。先把地图转成图再验证奇度点数量如果真的存在奇度点就补边、配对、求最短路最后用Hierholzer算法输出结果。整套流程下来代码量不到两百行却能解决一堆路线规划类的实际问题。如果你想进一步深入可以自己动手扩展一下有向图的场景或者把Hierholzer算法改写为递归版本体会一下栈与递归调用之间微妙的等价关系。对我来说欧拉图最迷人的地方就在于一个两百多年前的数学问题至今仍然活跃在公交调度、芯片制造和基因测序这些截然不同的领域里反复提醒着人们好的抽象永远经得起时间考验。