想象你管理着一座巨大的游乐园，园区里散布着大大小小的路口与景点，道路纵横交错。今天你要安排两件表面相似的差事：第一件，让洒水车司机把每一条道路都洒一遍水，每条路恰好洒一次；第二件，让游客把每一个景点都打卡一遍，每个景点恰好逛一次。前者叫“扫街”，后者叫“打卡”——听起来都是“走一圈”的事，可两件差事的难度却天差地别。 扫街的老欧（欧拉 Euler）上手极快，他只要在每个路口数一数有几条路进出，就能立刻判断路线是否可行。而打卡的小哈（哈密顿 Hamiltonian）却愁眉苦脸：没有任何简单公式能帮他判断路线行不行，只能一套方案一套方案地反复试。当景点数量稍多时，可能的方案数量甚至比宇宙中原子的总数还多。 这背后正是图论中两座著名的“大山”——欧拉路径与哈密顿路径。这篇文章就从洒水车与打卡者的故事出发，把它们的定义、判定、算法和复杂度差异一次讲个明白。

岗位关联

学懂欧拉与哈密顿的区别，你就能在算法设计时快速识别“这是边任务还是顶点任务”，避免在 NP 完全问题上空耗算力，这是图论应用与算法面试中的必备直觉。

目录
  1. 可视化演示
  2. 定义起源：七桥与环游世界
  3. 度数判定：路口的岔口计数法
  4. 弗勒里算法：独木桥前的慎重
  5. NP完全性：打卡路线的指数噩梦
  6. 核心区别：边任务与顶点任务的分野
  7. 实际应用：从扫地机器人到 DNA 测序
  8. AI 应用场景
  9. Python 演示
  10. 常见误区
  11. 面试题

可视化演示

展示欧拉路径遍历每条边一次、哈密顿路径遍历每个顶点一次，以及P与NP完全问题的复杂度本质差异。

本节配有交互动效（进入视口后自动加载，约 3KB）。

欧拉路径遍历 每条边恰好经过一次 判定条件：0或2个奇度顶点 复杂度：O(E) — Hierholzer算法 欧拉路径存在多项式时间解法，可高效求解

定义起源：七桥与环游世界

1736 年的普鲁士，柯尼斯堡城有一条普雷格尔河穿城而过，河中有两座小岛，两岸与岛之间一共架了七座桥。城里人闲来无事，最爱玩一个“洒水车难题”：能否从某一块陆地出发，不重复地走遍这七座桥，最后还能回到原点？这像极了游乐园里老欧的扫街任务——只不过他面对的是七座桥和四块陆地，目标是“每条路恰好走一次”。

欧拉把这四块陆地压缩成四个点，把七座桥画成连接点的线段，问题立刻变成了一张“图”。他给出了干脆的回答：这种走法根本不存在。这篇论文被公认为图论的起点。一百多年后，数学家哈密顿发明了一个环游世界的游戏：把正十二面体的二十个顶点看作二十座城市，要找一条路线，经过每座城市恰好一次再返回。这正是小哈的“打卡任务”——目标是“每个景点恰好去一次”。

两个问题都叫“路径”，定义却对称地拧着劲。欧拉路径要求遍历每条边恰好一次，哈密顿路径要求遍历每个顶点恰好一次；若要求终点回到起点，则分别是欧拉回路与哈密顿回路。这一字之差，预示了完全不同的命运。

老欧的眼里只有路，小哈的眼里只有景点。同一张地图摆在那里，任务对象不同，接下来的命运就开始分道扬镳了——而第一道分水岭，出现在“能否快速判定”这个问题上。

欧拉回路:E(P)=E(G),哈密顿回路:V(P)=V(G)\text{欧拉回路}: E(P)=E(G),\qquad \text{哈密顿回路}: V(P)=V(G)
这个公式用集合相等表达了两种回路的核心要求：欧拉回路要求“路径踩过的边集合”等于“全图的边集合”；哈密顿回路要求“路径经过的顶点集合”等于“全图的顶点集合”。一个装满边，一个装满点，任务对象从一开始就分道扬镳。
  1. 路径的边集 E(P)P 是走过的路线，E(P) 收集这条路线上踩过的所有边。欧拉回路要求这些边恰好装满整张图的边集，每条路都跑且只跑一次。
    E(P)=E(G)E(P)=E(G)
  2. 全图的边集 E(G)E 是边集符号，E(G) 表示图 G 里所有道路的集合，共 m 条边。等式表达的正是“一条不漏、一条不多”。
    E(G)={e1,e2,…,em}E(G)=\{e_1,e_2,\ldots,e_m\}
  3. 路径的顶点集 V(P)V 是顶点集符号，V(P) 是路线经过的顶点集合。哈密顿回路要求每个景点至少到访一次且整条路线闭合。
    V(P)=V(G)V(P)=V(G)
  4. 全图的顶点集 V(G)V(G) 是所有景点的集合，共 n 个顶点。对哈密顿回路而言，这个等式就是“全部打卡、不重不漏”的数学表达。
    V(G)={v1,v2,…,vn}V(G)=\{v_1,v_2,\ldots,v_n\}

度数判定：路口的岔口计数法

游乐园的老欧想快速知道扫街任务是否可行。他做了个聪明的统计：在每个路口数一数，到底有几条路从这个路口伸展出去。这个数字，图论里叫“度数”。他发现，如果每个路口的道路条数都是偶数，也就是“有进必有出”，那就能设计一条不重复走完所有路的闭合路线。反之，如果某个路口是“死胡同”，道路成单，就容易卡壳。

这个规律就是欧拉定理的核心：一个连通无向图存在欧拉回路，当且仅当所有顶点的度数都为偶数。为什么必须连通？因为如果地图被大河分成两个互不相连的区域，即使两边各自满足偶数度，洒水车也飞不过河，自然无法一笔画完。所以“连通”是地基，“全偶数度”是楼层，缺一不可。

如果图形条件稍稍放宽，恰好有 0 个或 2 个奇数度顶点，图仍然存在欧拉路径——不需要闭合的路线，两个奇度顶点恰好充当起点和终点。比如“一笔画”游戏里的“日”字，中间两个顶点度数为 3，其他为 2，所以能一笔画出但不闭合。

老欧靠着“路口岔口计数法”几秒钟就完成了判定，图纸一摊，结论立现。但判定可行不等于能走通——真正上路时，他还需要学会一件事：在独木桥前保持慎重。

连通图 G 存在欧拉回路  ⟺  ∀v∈V(G), deg⁡(v)≡0 (mod 2)\text{连通图 }G\text{ 存在欧拉回路}\iff\forall v\in V(G),\ \deg(v)\equiv0\ (\mathrm{mod}\ 2)
这条定理是图论中最“亲民”的判定工具：把每个顶点的度数算一遍，再确认图整体连通，就能在几分钟内判断洒水车任务能否完成。欧拉问题“容易”的第一个信号，就在这里。
  1. 顶点度数 deg(v)顶点 v 接出去的道路条数。十字路口有 4 条路，所以 deg=4；丁字路口有 3 条路，所以 deg=3。
    deg⁡(v)=与 v 相连的边数\deg(v)=\text{与 }v\text{ 相连的边数}
  2. 偶数度的含义度数对 2 取余为 0。对闭合路线来说，每次进入一个路口，必须能匹配到一条出去的路，所以进出要成双。
    deg⁡(v)≡0 (mod 2)\deg(v)\equiv0\ (\mathrm{mod}\ 2)
  3. 全称量词 所有顶点要求图中每一个顶点都满足偶数度，不允许任何一个“落单”。洒水车老欧必须把每个路口的岔口数都检查一遍。
    ∀v∈V(G)\forall v\in V(G)
  4. 双向箭头 当且仅当条件是充分且必要的。只要连通且全偶数度，欧拉回路必然存在；反过来，只要有欧拉回路，度数必然是偶数。
    A  ⟺  BA\iff B
  5. 欧拉路径的宽松版若恰好有 2 个奇度顶点，图中仍有欧拉路径，只是不闭合；这两个奇度顶点就是起点和终点。
    #{v:deg⁡(v) 为奇数}=0 或 2\#\{v:\deg(v)\text{ 为奇数}\}=0\ \text{或}\ 2

弗勒里算法：独木桥前的慎重

判定是纸上谈兵，真正握着方向盘的老欧还面临一个陷阱：有些路段是“独木桥”——一旦开过去，整座桥就被封掉，自己可能被困在一小块孤岛上，剩下的路再也洒不着。要避免这种悲剧，老欧给自己立了一条规矩：每次选择下一段路时，只要还有其他选择，就绝对不碰独木桥；只有当面前每一条路都是独木桥时，才被迫走上去。

这条规矩就是 Fleury 算法（弗勒里算法）的核心。把“独木桥”换成图论术语：一条边若是“桥”（删除它会让剩余图不再连通），就尽量别走。完整流程是：首先确认图满足欧拉路径条件；然后从奇度顶点出发（若无奇度顶点，从任意点出发）；每一步扫描当前顶点的未走边，优先选择非桥边；走完一条边就把它从图中删掉；重复直到所有边走完，得到一条完整的欧拉回路。

这个算法是典型的贪心策略。它的巧妙之处在于，用“当前图”的连通性来指导每一步选择，而不是全局规划。每一条非桥边的选择都保证：走完之后，剩余边仍然可以通过未来的路线连成一体。

弗勒里算法让老欧走得既稳又全，每一步都确保退路存在，最终完整地扫过所有道路。欧拉问题从判定到构造都有了漂亮的多项式算法——可另一边的小哈，就没有这么好运了。

Fleury 选边规则:若存在非桥边，则选取非桥边；否则才允许选桥\text{Fleury 选边规则}:\quad \text{若存在非桥边，则选取非桥边；否则才允许选桥}
弗勒里算法把“别把自己逼进死胡同”这条生活经验变成了严格的算法。每一次选择都像一个谨慎的司机在过桥前探头张望：万一这座桥是唯一退路，那我宁愿绕远路。
  1. 当前图 G已经走过的边从图中移除后，剩下的图叫 G'。决策永远基于此刻还剩下哪些路可走。
    G′=G−{已走过的边}G'=G-\{\text{已走过的边}\}
  2. 桥的定义当一条边被删掉之后，剩余图被分成两个互不相连的部分，这条边就是桥。桥是“路线上唯一的咽喉”。
    e 是桥  ⟺  G′−e 不连通e\text{ 是桥}\iff G'-e\text{ 不连通}
  3. 非桥优先在候选边里，优先挑不是桥的边走，这样不会把剩余路线截断。
    选 e,e∉Bridge(G′)\text{选 }e,\quad e\notin\text{Bridge}(G')
  4. 万不得已才走桥若当前顶点可选的所有边都是桥，说明前方别无选择，也只能硬着头皮走过去。
    Bridge(G′)=E(G′)⇒任意选一条桥\text{Bridge}(G')=E(G')\Rightarrow\text{任意选一条桥}

NP完全性：打卡路线的指数噩梦

游乐园的小哈想把 20 个景点全部打卡，他随手列出所有可能的顺序：20! 种，也就是 20 × 19 × 18 × …… × 1，约等于 2.43 × 10^18 种。即使每秒能验证一百万种方案，也需要七万多年才能穷举完。小哈崩溃了：有没有什么像“数路口”那样的简单规则，能直接判断打卡路线是否存在呢？

遗憾的是，两百年来数学家们也没找到这样的规则。哈密顿路径的判定问题成了第一批被证明的 NP 完全问题之一。所谓 NP 完全，可以通俗理解为“困难俱乐部”的元老成员：全世界成千上万个难以快速求解的问题，都能在多项式时间内转化为哈密顿问题；只要哈密顿问题找到多项式算法，整个俱乐部的难题都会迎刃而解——这等价于计算机科学中著名的 P=NP 猜想。

对普通开发者而言，不需要会证明，只需要记住后果：求哈密顿路径，目前没有已知的多项式级“捷径”。所有精确算法在最坏情况下都退化为指数时间。比赛中能暴力搜索的规模极限通常只有 n≤20 左右，再大就束手无策。

老欧的洒水车路线五分钟规划完毕，小哈的打卡路线却要用近乎“宇宙寿命”的时间去穷举。这就是“简单”与“困难”肉眼可见的差距。现在，让我们把两位主角放在同一张表格里，看看它们到底差在哪里。

T暴力(n)=O(n!)T_{\text{暴力}}(n)=O(n!)
阶乘函数是“指数爆炸”的升级版。当 n=15 时，15! 约等于 1.3 万亿，已经超过普通计算机一秒内的运算次数；当 n=50 时，50! 的位数比宇宙原子的估算总数还多。小哈的打卡任务，本质上是在和阶乘赛跑。
  1. n 个顶点的排列哈密顿路径要确定 n 个景点的访问先后顺序，本质是给 n 个元素排序。
    n: 图 G 的顶点数n\text{: 图 }G\text{ 的顶点数}
  2. 阶乘的展开第一个位置有 n 种选择，第二个位置剩 n-1 种……全部乘起来，就是 n! 种排列顺序。
    n!=n×(n−1)×⋯×2×1n!=n\times(n-1)\times\cdots\times2\times1
  3. 大 O 记法O 描述计算量随 n 增长的量级。n! 增长极快，远超任何多项式函数如 n² 或 n³。
    O(n!) 代表“随 n 阶乘级增长”O(n!)\ \text{代表“随 }n\text{ 阶乘级增长”}
  4. 和欧拉的对比欧拉判定只需扫一遍顶点和边，复杂度是 O(V+E)；哈密顿判定却是 NP 完全，这一刻的对比无比刺眼。
    O(V+E)vsO(n!)O(V+E)\quad\text{vs}\quad O(n!)

核心区别：边任务与顶点任务的分野

把洒水车老欧和打卡者小哈并排站好，最本质的区别其实只有三个词：作用对象、判定难度、求解复杂度。欧拉回路处理的是“边”，谁在乎一个顶点被走过几次呢？路线可以反复经过同一个路口，只要每条路只走一次即可。哈密顿回路处理的是“顶点”，每个景点只能去一次，道路反而可以用不完。

正因为作用对象不同，两者的数学难度发生了断裂。欧拉问题拥有度数定理这样的完美充要条件，判定是线性的，构造有弗勒里算法；哈密顿问题则是 NP 完全，没有简单的充要条件，没有多项式级的构造算法，精确求解只能靠指数级搜索。完全图 K_n 里任意一个顶点排列都是哈密顿路径，共有 n! 条——这个公式恰恰暴露了它是“排列问题”，而排列问题极少有捷径。

对比起来，欧拉问题像“系统性扫街”：路是任务，点可以重复；哈密顿问题像“行商打卡”：点是任务，路只是连接工具。前者是图论里少数能被彻底征服的问题，后者则是计算机科学里公认的硬骨头。

记住这句话：在算法设计里，能数路口就绝不要排列景点。懂得先判断“这是边任务还是顶点任务”，你就已经赢了一半。而另一半，藏在真实世界的那些看似无关的问题中。

欧拉回路:判定 O(V+E), 构造 O(E2)哈密顿回路:判定 NP-完全, 暴力 O(n!)\begin{aligned}\text{欧拉回路} &: \text{判定 }O(V+E),\ \text{构造 }O(E^2)\\\text{哈密顿回路} &: \text{判定 NP-完全},\ \text{暴力 }O(n!)\end{aligned}
一张对比表道尽天壤之别：一个是多项式时间的“乖孩子”，一个是指数爆炸的“问题少年”。当你拿到一个图论题，最先问自己的就是——任务对象是边还是顶点？
  1. 欧拉的复杂度判定只需统计度数再检查连通，消耗 O(V+E)；弗勒里构造最坏 O(E²)。整体上是温和的多项式时间。
    O(V+E) 与 O(E2)O(V+E)\ \text{与}\ O(E^2)
  2. 哈密顿的复杂度判定本身就是 NP 完全，最坏情况下所有已知精确算法都是指数级。
    NP-Complete\text{NP-Complete}
  3. 完全图上的排列数K_n 中任意顶点排列都相邻连通，所以哈密顿路径数量就是全排列数量，这是“点任务”的典型特征。
    Kn 的哈密顿路径数=n!K_n\text{ 的哈密顿路径数}=n!
  4. 规模现实的差距n=50 时，欧拉度数检查只需扫描几百条边，而 50! 超过 3×10^64，比宇宙原子数还恐怖。
    50!≈3.04×106450!\approx3.04\times10^{64}

实际应用：从扫地机器人到 DNA 测序

游乐园老板终于明白了这个道理，开始把两类任务应用到运营中。洒水车要覆盖全部道路且尽量不重复，这是标准欧拉问题；而贵宾体验师想用最短路线玩遍所有景点，这是哈密顿问题，本质是旅行商问题（TSP）——对所有景点排列求总距离最小值。前者用弗勒里算法或更快的 Hierholzer 算法轻松解决，后者只能借助近似算法。

走出游乐园，欧拉与哈密顿的用武之地更广。扫地机器人把房间划成网格，把“需要清扫的相邻格子边界”当边，规划欧拉回路实现全覆盖且少重复；搜索引擎爬虫遍历网页链接时，也常遇到类似“走遍所有链接”的欧拉型路由问题。而哈密顿路径则在基因组测序中唱主角：经典的重叠图拼接策略，正是要在“每个测序片段是一个顶点”的图上，找出一条经过所有顶点的哈密顿路径来还原完整基因组。

在算法竞赛中，这两类问题也是常客。例如“单词接龙”类题目要求用每个单词的首尾字母拼接成链，把字母当顶点、单词当边，就化归为欧拉路径判定；而“小规模旅行推销员”则要求用状态压缩动态规划硬啃哈密顿回路。判断题型决定工具：见到边任务，立刻想到度数定理和欧拉算法；见到点任务，立刻想到 NP 完全并调整策略。

从游乐园到实验室，从扫地机器人到基因组，欧拉负责“把每条路都走遍”的完美方案，哈密顿负责“把每个点都逛完”的艰难抉择。理解了它们的区别，你就掌握了图论中最重要的一道分界线。

min⁡排列 p L=∑i=1n−1d(pi,pi+1)\min_{\text{排列 }p}\ L=\sum_{i=1}^{n-1}d(p_i,p_{i+1})
这是旅行商问题的目标函数：在所有哈密顿回路中，找一条总距离最短的路线。它把“打卡所有景点”变成了一个优化问题，也是物流、芯片钻孔、电路板设计中每天都要面对的难题。
  1. 访问顺序排列 pp_1 到 p_n 是 n 个景点的访问顺序，每种排列对应一条哈密顿路径。
    p=(p1,p2,…,pn)p=(p_1,p_2,\ldots,p_n)
  2. 相邻距离 dd(p_i,p_{i+1}) 表示从第 i 个景点到第 i+1 个景点的距离，可以是直线距离或实际路况距离。
    d(pi,pi+1)d(p_i,p_{i+1})
  3. 总路程求和把沿途所有相邻距离加在一起，得到这条打卡路线的总长度 L。
    L=∑i=1n−1d(pi,pi+1)L=\sum_{i=1}^{n-1}d(p_i,p_{i+1})
  4. 全局取最小在所有可能的哈密顿回路中挑选总长度最小的那一条，这正是旅行商问题的核心。
    min⁡pL\min_{p}L

AI 应用场景

扫地机器人的全覆盖路径规划

阶段：路径规划与决策

解决的问题：传统随机碰撞式扫地机器人效率低、容易漏扫；若把房间划分成网格，把需要清扫的相邻区域边界当作“边”，扫地机器人要扫过每条边恰好一次，这正是欧拉回路问题。用度数判定确认方案可行，再套用弗勒里算法规划路线，能实现“全覆盖、少重复”的清扫路径。

具体案例：某家用机器人团队在 10m×10m 的客厅地图上建立网格图，用欧拉回路算法生成扫街式路径，相比随机碰撞模式，清扫覆盖率从 82% 提升到 99%，重复率下降 40%。

DNA 测序中的序列组装

阶段：生物信息数据处理

解决的问题：基因测序仪把长链 DNA 打碎成海量短片段，拼接时把每个片段看作顶点、片段间的重叠关系看作边，寻找一条经过所有片段的哈密顿路径来还原完整序列；而新一代 de Bruijn 图策略则把 k-mer 当顶点，同样的问题转化为找欧拉路径。两种路径模型在同一个生物问题里“同台竞技”。

具体案例：在细菌基因组组装中，OLC 策略（哈密顿型）处理较长片段效果好，de Bruijn 图策略（欧拉型）对重复序列更稳健，工程师需要根据测序平台选择合适的图模型，才能拼出完整基因组。

物流配送的路线优化

阶段：调度优化

解决的问题：快递员每天要访问辖区内全部客户点并返回仓库，目标是总路程最短——这是标准的哈密顿回路最小化（TSP）。由于哈密顿问题是 NP 完全，无法用暴力穷举，实际系统使用 LKH、蚁群或遗传算法等近似方法求次优解。

具体案例：某同城配送平台为骑手规划订单配送顺序，用 TSP 近似算法把 20 个客户点的配送路线长度缩短 18%，高峰期日均单量提升 12%。

Python 演示

python102 行
# -*- coding: utf-8 -*-"""欧拉路径判定 + Fleury 算法 + 哈密顿暴力搜索演示""" from collections import defaultdict  def euler_type(edges, n):    """返回: 0=无欧拉路径, 1=有欧拉路径, 2=有欧拉回路"""    g = defaultdict(list)    for u, v in edges:        g[u].append(v)        g[v].append(u)    odd = sum(1 for v in range(n) if len(g[v]) % 2)    if odd not in (0, 2):        return 0    seen = set()     def dfs(v):        seen.add(v)        for w in g[v]:            if w not in seen:                dfs(w)     start = next((v for v in range(n) if len(g[v])), 0)    dfs(start)    if any(len(g[v]) and v not in seen for v in range(n)):        return 0    return 1 if odd == 2 else 2  def fleury(edges, n):    """Fleury 算法求解欧拉回路, 返回边序列"""    adj = defaultdict(list)    for i, (u, v) in enumerate(edges):        adj[u].append((v, i))        adj[v].append((u, i))    used = [False] * len(edges)     def is_bridge(u, v, ei):        used[ei] = True        seen = {u}        stack = [u]        while stack:            x = stack.pop()            for y, j in adj[x]:                if not used[j] and y not in seen:                    seen.add(y)                    stack.append(y)        used[ei] = False        return v not in seen     start = 0    for v in range(n):        if len(adj[v]) % 2 == 1:            start = v            break    path = []     def tour(v):        while True:            cands = [(w, ei) for w, ei in adj[v] if not used[ei]]            if not cands:                break            w, ei = cands[0]            for w2, ei2 in cands:                if not is_bridge(v, w2, ei2):                    w, ei = w2, ei2                    break            used[ei] = True            path.append((v, w))            v = w     tour(start)    return path  def hamilton_bruteforce(edges, n):    """暴力搜索一条哈密顿路径, 只适合 n <= 9"""    adj = [set() for _ in range(n)]    for u, v in edges:        adj[u].add(v)        adj[v].add(u)    for start in range(n):        stack = [(start, [start], {start})]        while stack:            v, path, seen = stack.pop()            if len(path) == n:                return path            for w in adj[v]:                if w not in seen:                    stack.append((w, path + [w], seen | {w}))    return None  if __name__ == '__main__':    # 两个三角形共享顶点0, 全偶数度, 有欧拉回路    edges = [(0, 1), (1, 2), (2, 0), (0, 3), (3, 4), (4, 0)]    n = 5    t = euler_type(edges, n)    print("欧拉判定:", "回路" if t == 2 else "路径" if t == 1 else "不存在")    print("Fleury 欧拉回路:", fleury(edges, n))    print("哈密顿路径:", hamilton_bruteforce(edges, n))
目的：在同一个 5 顶点图上，先判定欧拉回路存在并用 Fleury 算法构造出回路，再用暴力搜索找出哈密顿路径，直观展示“边任务”与“点任务”的不同解法。
  1. odd = sum(1 for v in range(n) if len(g[v]) % 2)统计奇数度顶点个数，这是欧拉判定的一号标准。
  2. if odd not in (0, 2): return 0奇度顶点数量不是 0 或 2，直接宣告没有欧拉路径，这是度数定理的核心应用。
  3. if any(len(g[v]) and v not in seen for v in range(n)):检查是否所有非孤立顶点处在同一个连通块里，防止“河对岸”的孤岛。
  4. def is_bridge(u, v, ei):桥检测函数：临时删掉一条边，用 DFS 看能否绕过它到达对岸。
  5. cands = [(w, ei) for w, ei in adj[v] if not used[ei]]收集当前顶点所有尚未走过的候选边，对应老欧在路口探头张望。
  6. for w2, ei2 in cands: if not is_bridge(v, w2, ei2):Fleury 贪心核心：优先取不是桥的边，避免自断退路。
  7. stack = [(start, [start], {start})]哈密顿暴力搜索的初始状态，从每个顶点开始深度优先穷举全部排列。

常见误区

误区我觉得欧拉是每条边一次，哈密顿是每个顶点一次，这不就是把“边”换成“顶点”嘛，难度应该差不多，会一个就会另一个。

正解定义确实对称，但复杂度天差地别。欧拉问题有度数定理给出线性时间的充要判定，哈密顿问题则是 NP 完全，没有任何已知多项式判定手段。就像“把房间打扫干净”和“把房间里的玩具按顺序排队”，前者有成熟流程，后者组合爆炸。这种难度断裂正是图论最反直觉的地方。

为何常见：初学时的定义表述太对称，容易让人误以为背后是对偶关系，而忽略了计算复杂性这道鸿沟。

误区我记得欧拉回路的条件是所有顶点度数都是偶数，那我随便画一个全偶数度的图，不就一定有欧拉回路吗？为什么我画的图走不出来？

正解你很可能漏掉了连通性前提。图若被分成两个互不连通的子图，每个子图内部虽然全偶数度，但没有道路连接，洒水车不可能飞过去。判定时必须加一句：所有非孤立顶点必须处于同一个连通分量里。分居两岸的“偶数度小岛”合起来并不是一个可一笔画的整体。

为何常见：教材常把“度数条件”放在标题位置，连通性作为条件一笔带过，学习者只记住了前半句，做题时便踩坑。

误区我以为欧拉回路就是欧拉路径，反正都要走完所有边，回不回到起点无所谓。

正解回路要求终点回到起点，且所有顶点度数为偶数；而欧拉路径允许恰好 2 个奇度顶点，这两个顶点就是起点和终点。比如“一笔画”一个“日”字，中间两点度为 3，它有一笔画的路径但不能闭合回起点。类似地，哈密顿回路与哈密顿路径也是同样的闭合性区别。判定时先分清楚题目要的是“路径”还是“回路”，条件完全不同。

为何常见：中文里“路径”和“回路”听起来像一回事，但在图论中“闭合”二字直接改变判定条件和算法选择。

误区Fleury 算法能找欧拉回路，那我把图的顶点当目标，用同样的贪心思路选边走，应该也能找哈密顿路径吧？

正解Fleury 的“非桥优先”策略之所以正确，是因为欧拉问题有度数定理兜底，保证非桥边的选择不会破坏整体可行性。哈密顿问题是 NP 完全，没有任何贪心规则能保证不走到死胡同。硬套 Fleury 型贪心只会得到一条很长的路径，却几乎不可能保证恰好覆盖所有顶点。算法可以借鉴思想，但不能跨界搬运保证性。

为何常见：两类问题都叫“路径”，新手容易把欧拉问题的贪心算法误当成通用路径算法。

误区我知道哈密顿是 NP 完全，但我的搜索加了剪枝，几十个顶点很快也能出结果，是不是实际没那么难？

正解剪枝只能优化常数，无法改变最坏情况的指数增长。在竞赛中 n≤20 时状态压缩可行，n≤30 加剪枝也许能碰运气，但 n=50 时排列数量是 50!≈3×10^64，任何剪枝都救不回来。精确算法之外的正确出路是换赛道：用近似算法、启发式算法或动态规划在特定结构上求次优解，而不是硬拼暴力搜索。

为何常见：刷题时常用的小图让剪枝效果“看起来很好”，让人误以为指数级只是理论恐吓，直到真实数据把运行时间拉满才醒悟。

面试题

Q1. 一个连通无向图存在欧拉回路的充要条件是什么？

单选题 · easy

  • A.每个顶点的度数都是偶数← 正确答案
  • B.恰好两个顶点的度数为奇数
  • C.至少有一个顶点的度数为零
  • D.边数恰好等于顶点数

答案：A。欧拉回路要求“有进有出且能回起点”，所以所有顶点度数必须为偶数，此外还要保证连通。B 对应的是不闭合的欧拉路径，C 中零度顶点与连通矛盾，D 只是边数与顶点数的偶然相等，与欧拉条件无关。就像洒水车要环游一圈，每个路口的进出路必须成双。

Q2. 柯尼斯堡七桥问题中，为什么“不重复走遍七座桥”的路线不存在？

单选题 · easy

  • A.因为桥的总数是奇数
  • B.因为四块陆地连接的桥数都是奇数← 正确答案
  • C.因为河流太宽
  • D.因为桥的长度不一样

答案：B。把四块陆地看作顶点，每块陆地连接的桥数分别是 5、3、3、3，四个全是奇数度顶点。欧拉路径要求奇数度顶点数为 0 或 2，这里却有 4 个，所以无解。桥总数是奇数并不妨碍欧拉回路存在，关键在于每个顶点进出配对的“度数”。

Q3. 哈密顿路径要求路线满足什么条件？

单选题 · easy

  • A.经过每条边恰好一次
  • B.经过每个顶点恰好一次← 正确答案
  • C.经过每条边至少一次
  • D.经过每个顶点至少一次

答案：B。哈密顿路径是“点任务”，要求每个顶点恰好访问一次，边可以不用完；欧拉路径才是“边任务”，要求每条边恰好经过一次。A 是欧拉的定义，C 和 D 分别是“中国邮路”和“覆盖问题”的变体，都不是哈密顿的准确表述。

Q4. 以下关于欧拉路径与哈密顿路径的陈述，哪些是正确的？

多选题 · easy

  • A.欧拉路径经过图中每条边恰好一次← 正确答案
  • B.哈密顿路径经过每个顶点恰好一次← 正确答案
  • C.有欧拉回路的图一定是连通的← 正确答案
  • D.有哈密顿回路的图一定有欧拉回路

答案：ABC。A 和 B 是两种路径的标准定义；C 正确，欧拉回路必须在连通图上才有意义。D 错误，哈密顿回路只管顶点不重复，不保证每条边恰好一次。例如五角星图有哈密顿回路但某些边可能多余，其度数条件未必成立。

Q5. 在 Fleury 算法中，“桥”指什么？

单选题 · mid

  • A.图中长度最长的边
  • B.删除后会使剩余图不再连通的边← 正确答案
  • C.连接两个奇数度顶点的边
  • D.权值最大的一条边

答案：B。桥是“独木桥”——删掉它，剩余图就分裂成两个互不相连的部分。Fleury 算法优先避开的正是这种边，防止走过后把自己困在孤岛上。C 是欧拉路径起点终点的特征，但不是桥的定义；A 和 D 与边长权重无关。

Q6. 判断一个图是否存在哈密顿路径，目前已知的复杂度属于哪种？

单选题 · mid

  • A.线性时间 O(V+E)
  • B.多项式时间 O(V²)
  • C.NP 完全← 正确答案
  • D.常数时间 O(1)

答案：C。哈密顿路径判定是第一批被证明的 NP 完全问题之一，目前没有已知多项式算法。欧拉判定才是线性时间，B 和 D 更是无从谈起。遇到“判断是否存在经过所有顶点一次的路径”这类题，第一时间想到指数级搜索，或借助特定图结构求特解。

Q7. 关于欧拉路径的存在条件，下列哪些说法正确？

多选题 · mid

  • A.图中奇数度顶点数为 0 时，连通图存在欧拉回路← 正确答案
  • B.图中奇数度顶点数为 2 时，连通图存在不闭合的欧拉路径← 正确答案
  • C.图可以不连通，只要每个连通分量内满足度数条件
  • D.图中奇数度顶点数为 4 时仍可能有欧拉路径

答案：AB。欧拉定理指出连通且奇数度顶点数为 0 得回路、为 2 得开路径，A 和 B 正确。C 错误，图必须整体连通，否则洒水车跨越不了断裂区域；D 错误，4 个奇度顶点无法配成一条连续的“一笔画”路线。

Q8. 欧拉路径问题与哈密顿路径问题在复杂度上的关键差异是什么？

单选题 · mid

  • A.前者有线性或多项式算法，后者没有已知多项式算法← 正确答案
  • B.后者有线性算法而前者没有
  • C.两者都无法在多项式时间内判定
  • D.两者难度完全相同

答案：A。欧拉判定 O(V+E)、构造 O(E²)，属于典型的 P 类问题；哈密顿判定是 NP 完全，没有已知多项式算法。两者虽定义对称，复杂性却是一个在平地、一个在峭壁。正因为如此，工程中遇到问题要先判断“对象是边还是点”。

Q9. 关于欧拉路径与哈密顿路径的区别，下列哪些说法正确？

多选题 · hard

  • A.欧拉路径针对边，哈密顿路径针对顶点← 正确答案
  • B.欧拉路径的判定是简单问题，哈密顿路径是 NP 完全← 正确答案
  • C.两者的求解复杂度在同一数量级
  • D.欧拉回路必然同时是哈密顿回路

答案：AB。A 是任务对象的本质区别；B 是复杂度上的天壤之别；C 错误，一个多项式一个指数；D 错误，欧拉回路允许重复经过顶点，而哈密顿回路要求顶点不重复。例如一条“8”字形路线可重复走中心点，欧拉成立但哈密顿不成立，反之亦然。

Q10. 在完全图 K_n 中，考虑方向的哈密顿路径总共有多少条？

单选题 · hard

  • A.n 条
  • B.n! / 2 条
  • C.n! 条← 正确答案
  • D.2^n 条

答案：C。完全图任意两个顶点之间都有边，所以顶点的任何排列都自动构成一条哈密顿路径。n 个顶点的排列数是 n!，若方向视为相同则是 n!/2，但题目明确“考虑方向”，因此答案是 n!。这个例子说明哈密顿问题本质上是排列问题，排列数的增长速度决定了它的 NP 完全属性。