1. 概述
在图论中，Hamiltonian 路径和 Euler 路径是两个非常基础且重要的概念。本文将分别介绍这两个概念的定义、特性，并通过图示和代码辅助说明，帮助读者快速掌握其核心思想。
最后我们会对这两个概念做一个高阶对比，帮助你更好地区分它们的应用场景和本质区别。
2. 定义解析
2.1. Hamiltonian 路径
Hamiltonian 路径是指一条恰好经过图中每一个顶点一次的路径。也就是说，它覆盖图中所有顶点，且每个顶点只访问一次。
✅ 关键点：
- 每个顶点只能访问一次
- 可以存在于有向图和无向图中
- 不要求起点和终点相同
2.2. Euler 路径
Euler 路径是指一条恰好经过图中每一条边一次的路径。也就是说，它覆盖图中所有边，但顶点可以重复访问。
✅ 关键点：
- 每条边只能访问一次
- 顶点可以重复访问
- 可以存在于有向图和无向图中
- 有顶点度数限制（后面详述）
3. 示例演示
3.1. Hamiltonian 路径示例
示例图 G₁
尝试路径 ABCDE：
- 所有顶点都被访问一次
- 没有重复顶点
✅ 结论：ABCDE 是一个 Hamiltonian 路径。
另一个例子：ACBED 也是一个 Hamiltonian 路径。
示例图 G₂
尝试路径 ABCDEDF：
- 顶点
D被访问了两次 ❌
✅ 结论：这不是一个 Hamiltonian 路径，且此图不存在任何 Hamiltonian 路径。
3.2. Euler 路径示例
示例图 G₃
尝试路径 ABCDBED：
- 所有边都被访问一次
- 边没有重复
✅ 结论：这是一个 Euler 路径。
其他路径如 ABEDBCD 也是合法的 Euler 路径。
示例图 G₄
尝试路径 ABCDEFDCABE：
- 边
E1和E2被重复访问 ❌
✅ 结论：这不是一个 Euler 路径，且此图无法构造出任何 Euler 路径。
4. 性质与判定条件
4.1. Hamiltonian 路径性质
✅ 判定条件：
对于任意一对非相邻顶点 u 和 v，满足：
d(u) + d(v) + δ(u, v) ≥ N + 1其中：
d(u)、d(v)：顶点 u 和 v 的度数δ(u, v)：u 到 v 的最短路径长度N：图中顶点总数
✅ 另一个性质：
- Hamiltonian 路径的起点和终点必须不同
4.2. Euler 路径性质
✅ 判定条件：
- 图中最多只能有两个顶点的度数为奇数（其余顶点度数必须为偶数）
✅ 附加性质：
- 所有非零度数顶点必须位于同一个连通分量中
5. 高阶对比总结
| 特性 | Hamiltonian 路径 | Euler 路径 |
|---|---|---|
| 定义 | 恰好访问每个顶点一次 | 恰好访问每条边一次 |
| 顶点访问 | 每个顶点只能访问一次 | 可以重复访问 |
| 边访问 | 可以重复 | 每条边只能访问一次 |
| 起点终点 | 必须不同 | 可以相同（回路） |
| 判定条件 | 任意非相邻顶点满足 d(u)+d(v)+δ(u,v) ≥ N+1 |
最多两个顶点度数为奇数 |
| 应用场景 | 网格划分、数据组织、通信优化 | DNA 序列重建、逻辑门排序 |
6. 小结与建议
✅ 踩坑提醒：
- 不要混淆顶点和边的访问规则
- 判断是否存在路径时，优先看度数和连通性
- 实际应用中，Euler 路径更容易判断和构造
✅ 适用建议：
- Hamiltonian 路径适用于路径规划、旅行商问题等
- Euler 路径适用于边遍历问题，如电路设计、基因拼接
7. 附录：代码片段（伪代码）
// 判断是否存在 Euler 路径（伪代码）
public boolean hasEulerPath(Graph g) {
int oddCount = 0;
for (Vertex v : g.vertices()) {
if (v.degree() % 2 != 0) {
oddCount++;
}
}
return oddCount <= 2;
}
// 判断是否存在 Hamiltonian 路径（伪代码）
public boolean hasHamiltonianPath(Graph g) {
Set<Vertex> visited = new HashSet<>();
for (Vertex v : g.vertices()) {
if (dfs(v, visited, 0)) {
return true;
}
}
return false;
}
⚠️ 注意：Hamiltonian 路径判断通常需要回溯或启发式算法，时间复杂度较高。
8. 参考资料
如果你在图论算法、路径规划、网络优化方面有进一步需求，这两个概念会是你的基础工具之一。建议结合实际项目多加练习，加深理解。