别再死记硬背了！图解哈密顿回路与欧拉回路的本质区别（附LeetCode刷题指北）

图解哈密顿回路与欧拉回路的本质区别：从理论到LeetCode实战

在准备算法面试或刷题时，图论中的哈密顿回路和欧拉回路是经常让学习者混淆的两个核心概念。许多人在面对相关题目时，常常陷入"这个题目到底在考哪个概念"的困惑。本文将用直观的图解方式，带你彻底理解两者的本质区别，并教你如何在LeetCode等OJ平台中快速识别和应用这些知识。

1. 基础概念：当"点"遇上"边"

1.1 哈密顿回路：每个顶点都是必经之地

想象你是一位旅行推销员，需要访问多个城市（顶点）并最终回到起点，且每个城市只能去一次——这就是哈密顿回路的现实场景。用专业术语来说：

• 定义：图中经过每个顶点恰好一次并返回起点的闭合路径
• 关键特征：
  • 关注顶点的访问情况
  • 允许重复经过边（只要顶点不重复）
  • 判断是否存在是NP完全问题

# 判断给定路径是否为哈密顿回路的简化代码 def is_hamiltonian_cycle(graph, path): if path[0] != path[-1] or len(path) != len(graph): return False visited = set() for i in range(len(path)-1): if path[i] in visited or path[i+1] not in graph[path[i]]: return False visited.add(path[i]) return True

1.2 欧拉回路：每条边都是必经之路

现在换个场景：你拿着一支笔，想不抬笔地画完整个图形，最终回到起点——这就是欧拉回路的一笔画问题。其核心特点是：

• 定义：图中经过每条边恰好一次并返回起点的闭合路径
• 关键特征：
  • 关注边的遍历情况
  • 允许重复经过顶点（只要边不重复）
  • 存在多项式时间判断算法

欧拉回路判定定理：无向图存在欧拉回路当且仅当图连通且所有顶点度数为偶数

2. 多维对比：从数学本质到实际应用

2.1 核心差异对照表

2.2 图解示例：同一图形的两种视角

考虑以下简单图形：

A —— B | | D —— C

• 哈密顿回路示例：A → B → C → D → A（每个顶点恰好访问一次）
• 欧拉回路示例：A → B → C → D → A → D → B → A（每条边恰好访问一次）

这个例子清晰地展示了：一个图可以同时存在哈密顿回路和欧拉回路，但它们是两种完全不同的遍历方式。

3. 算法实现：从理论到代码

3.1 哈密顿回路的典型解法

由于哈密顿回路是NP完全问题，我们通常采用以下策略：

1. 回溯法：系统性地尝试所有可能路径
2. 动态规划：如Held-Karp算法（时间复杂度O(V²·2ᴠ))
3. 启发式方法：遗传算法、模拟退火等近似解法

# 回溯法判断哈密顿回路存在性的简化实现 def has_hamiltonian_cycle(graph): path = [] def backtrack(current): if len(path) == len(graph): return path[0] in graph[current] # 能否回到起点 for neighbor in graph[current]: if neighbor not in path: path.append(neighbor) if backtrack(neighbor): return True path.pop() return False for start in graph: # 尝试每个顶点作为起点 path = [start] if backtrack(start): return True return False

3.2 欧拉回路的Hierholzer算法

相比之下，欧拉回路有确定性的高效算法：

def find_eulerian_circuit(graph): stack = [] circuit = [] current_vertex = next(iter(graph)) # 任意起点 stack.append(current_vertex) while stack: current = stack[-1] if graph[current]: # 还有未遍历的边 next_vertex = graph[current].pop() stack.append(next_vertex) else: circuit.append(stack.pop()) return circuit[::-1] # 反转得到正确顺序

4. LeetCode实战：如何识别题目考点

4.1 题目特征分析

遇到图论题目时，通过以下特征判断考察方向：

哈密顿回路相关题目：

• 要求"访问所有节点恰好一次"
• 常与最短路径结合（如旅行商问题）
• 题目可能直接提及"哈密顿"术语

欧拉回路相关题目：

• 关注"遍历所有边"或"一笔画"
• 可能出现"邮递员"、"路径重复"等关键词
• 题目可能要求判断是否存在或构造路径

4.2 经典题目解析

例题1：LeetCode 753. 破解保险箱

这题实际上是寻找德布鲁因序列，可以转化为有向图的欧拉回路问题。关键观察：

• 每个可能的密码组合对应图中的一个顶点
• 边表示密码之间的转移关系
• 寻找覆盖所有可能边的最短序列

例题2：PAT甲级1150 Travelling Salesman Problem

典型的哈密顿回路判断问题。解题要点：

1. 检查路径是否为环路（首尾相同）
2. 验证是否访问了所有城市
3. 确认每个城市（除首尾）只出现一次
4. 检查相邻城市间是否有直接路径

4.3 解题模板与技巧

对于哈密顿回路类题目，可以准备以下代码模板：

def is_hamiltonian_path(graph, path): # 基本检查：首尾相同、长度正确 if path[0] != path[-1] or len(path) != len(graph): return False visited = set() # 检查中间节点是否重复 for node in path[:-1]: if node in visited: return False visited.add(node) # 检查路径连通性 for i in range(len(path)-1): if path[i+1] not in graph[path[i]]: return False return True

对于欧拉回路问题，记住判定条件：

• 无向图：所有顶点度数为偶数且图连通
• 有向图：每个顶点入度等于出度且图弱连通

5. 进阶思考：为什么复杂度差异如此之大？

深入理解两种回路本质差异的关键在于认识它们对图结构的不同要求：

• 欧拉回路只关心边的遍历，而边是顶点的局部属性（度数）。检查每个顶点的度数即可全局判断，因此是P问题。

• 哈密顿回路要求全局的顶点访问顺序，这种全局约束使得我们必须考虑所有可能的排列组合，导致指数级复杂度。

这种差异也体现在实际应用中：

• 欧拉回路可用于设计高效的网络路由
• 哈密顿回路适用于需要完整覆盖的场景（如物流配送）

在刷题过程中，我经常遇到的一个误区是试图用欧拉回路的思路去解决哈密顿问题。记住一个简单的区分技巧：如果题目强调"访问所有地点"，很可能是哈密顿；如果强调"走过所有道路"，则可能是欧拉。