欧拉路径和欧拉回路是什么？如何判断一个图是否存在欧拉路径？

简化版

欧拉路径是经过图中每条边恰好一次的路径；欧拉回路是起点和终点相同的欧拉路径。

无向图中，存在欧拉回路要求所有非孤立点连通且所有点度数为偶数；存在欧拉路径但不是回路时，要求恰好有 2 个奇度点。

有向图中要看入度和出度：欧拉回路要求每个点入度等于出度；欧拉路径允许一个起点出度比入度多 1，一个终点入度比出度多 1。

详细版

欧拉问题关注的是边，而不是点。

类型	要求
欧拉路径	每条边恰好走一次
欧拉回路	每条边恰好走一次且回到起点

无向图判断：

条件	结论
所有非零度节点连通，奇度点为 0	欧拉回路
所有非零度节点连通，奇度点为 2	欧拉路径
其他情况	不存在

面试里容易和哈密顿路径混淆：欧拉看边，哈密顿看点。

完整版教学

1. 欧拉路径解决什么问题

欧拉路径要求每条边恰好经过一次。

典型问题包括：

• 一笔画问题；
• 安排行程使用所有机票；
• 遍历所有边的线路规划；
• 拼接边表示的序列。

它关心的是边有没有都被使用，而不是点是否只访问一次。

2. 欧拉路径和哈密顿路径的区别

这两个概念很容易混。

概念	关注对象	要求
欧拉路径	边	每条边恰好一次
哈密顿路径	点	每个点恰好一次

记忆方式：欧拉走边，哈密顿走点。

一个点在欧拉路径中可以经过多次，只要边不重复即可。

3. 无向图欧拉回路为什么要求偶数度

如果一条路径进入某个中间点，就必须再从这个点离开。

进入和离开成对出现，所以中间点的度数必须是偶数。

如果是回路，起点最后也要回到自己，起点的进入和离开也成对，因此所有点度数都为偶数。

4. 无向图欧拉路径为什么允许两个奇度点

如果路径不是回路，起点只需要多一次离开，终点只需要多一次进入。

因此最多有两个奇度点：

• 一个作为起点；
• 一个作为终点。

其他中间点仍然需要进入和离开配对，所以是偶数度。

5. 连通性为什么不能忘

只看度数不够。

如果图分成两个不连通部分，即使每个点度数都是偶数，也无法用一条路径覆盖所有边。

所以要保证所有有边的节点在同一个连通分量中。

检查项	目的
度数条件	保证进出配对
连通性条件	保证边能被同一路径覆盖

孤立点可以忽略，因为它们没有边需要走。

6. 有向图怎么判断

有向图要看入度和出度。

欧拉回路：

inDegree[v] == outDegree[v] for every v

欧拉路径：

一个点 out = in + 1 作为起点
一个点 in = out + 1 作为终点
其他点 in = out

同时也要考虑相关节点在连通意义上能串起来。

7. 如何构造欧拉路径

判断存在后，可以用 Hierholzer 算法构造。

基本思想是：

dfs(u):
  while u 还有未使用边:
    取一条边 u -> v
    dfs(v)
  path.add(u)

最后得到的路径通常需要反转。

8. 常见误区与追问

• 误区：欧拉路径要求每个点只经过一次。 那是哈密顿路径，欧拉路径关注每条边一次。
• 误区：只看度数就能判断。 还要检查有边节点的连通性。
• 误区：无向图欧拉路径可以有很多奇度点。 只能是 0 个或 2 个奇度点。
• 追问：欧拉回路和欧拉路径的区别是什么？ 回路要求起点和终点相同。
• 追问：怎么构造路径？ 常用 Hierholzer 算法，边用完后回溯加入路径。