从‘七桥问题’到算法面试：欧拉图与哈密顿图的核心考点与避坑指南

在18世纪的哥尼斯堡，七座桥梁连接着城市的不同区域，引发了一个看似简单却深奥的问题：能否设计一条路线，使得每座桥恰好经过一次？这个著名的"七桥问题"不仅催生了图论这一数学分支，更成为现代算法面试中图论问题的经典原型。对于准备技术岗位面试的求职者来说，理解欧拉图与哈密顿图的概念、区别及应用场景，是攻克算法题目的关键一环。

1. 历史渊源与概念本质

1.1 七桥问题与欧拉图的诞生

1736年，数学家欧拉将哥尼斯堡的七桥问题抽象为图论模型，用顶点表示陆地，边表示桥梁。他证明了一个重要结论： 要能够不重复地遍历所有边并回到起点，图中所有顶点的度数必须都是偶数 。这一发现奠定了欧拉图的基础：

• 欧拉回路 ：经过图中每条边一次且仅一次，并回到起点的路径
• 欧拉通路 ：经过图中每条边一次且仅一次，但不要求回到起点
• 判定条件 ：
  • 无向图存在欧拉回路 ⇨ 图连通且所有顶点度数为偶数
  • 无向图存在欧拉通路 ⇨ 图连通且恰好有两个顶点度数为奇数

# 判断无向图是否为欧拉图的Python实现
def is_eulerian(graph):
    if not is_connected(graph):  # 需要先实现图的连通性检查
        return False
    odd_degree = 0
    for degree in graph.degree().values():
        if degree % 2 != 0:
            odd_degree += 1
    return odd_degree == 0 or odd_degree == 2

1.2 哈密顿图的起源与发展

1859年，数学家哈密顿提出了一个不同的问题：能否找到一个闭合路径，经过图中每个顶点恰好一次？这类路径被称为哈密顿回路，相应的图称为哈密顿图。与欧拉图关注边不同，哈密顿图关注的是顶点的遍历。

提示：欧拉图与哈密顿图的根本区别在于前者关注边的遍历，后者关注顶点的遍历。这种差异导致它们的判定条件和应用场景大不相同。

2. 核心判定定理与算法实现

2.1 欧拉图的判定与应用

欧拉图的判定相对明确，基于顶点度数的奇偶性即可判断。在实际应用中，欧拉图常用于：

• 路径规划问题（如垃圾收集车路线）
• 电路板布线设计
• DNA片段组装

常见面试题变体 ：

• 给定一个图，判断是否存在欧拉回路/通路
• 如果存在，输出一条可能的路径
• 最少需要添加多少条边才能使图具有欧拉回路

# Hierholzer算法求欧拉回路
def find_eulerian_circuit(graph):
    if not is_eulerian(graph):
        return None
    
    circuit = []
    stack = [next(iter(graph.nodes()))]
    
    while stack:
        current = stack[-1]
        if graph.degree(current) == 0:
            circuit.append(stack.pop())
        else:
            neighbor = next(iter(graph.neighbors(current)))
            stack.append(neighbor)
            graph.remove_edge(current, neighbor)
    
    return circuit[::-1]

2.2 哈密顿图的判定挑战

与欧拉图不同，哈密顿图的判定要复杂得多。目前已知的一些充分条件包括：

• Ore定理 ：对于n≥3的简单图，如果任意两个不相邻顶点u和v满足deg(u)+deg(v)≥n，则图是哈密顿图
• Dirac定理 ：对于n≥3的简单图，如果每个顶点的度数至少为n/2，则图是哈密顿图

然而，判定一个图是否为哈密顿图是一个NP完全问题，没有已知的多项式时间算法。这使得哈密顿图问题在面试中常以以下形式出现：

• 判断特定结构的图（如完全图、网格图）是否为哈密顿图
• 在特定约束条件下寻找哈密顿路径
• 近似算法或启发式方法的应用

3. 面试中的高频考点与解题策略

3.1 欧拉图相关题目分析

例题1 （LeetCode 332. 重新安排行程）： 给定一个机票列表，每个机票用出发地到到达地的形式表示，请重建行程顺序。所有机票必须用且只用一次。

解题思路 ：

1. 将机票视为有向图的边
2. 问题转化为寻找有向图的欧拉通路
3. 使用Hierholzer算法求解

常见错误 ：

• 忽略有向图欧拉通路的判定条件（一个顶点入度比出度大1，一个顶点出度比入度大1，其余顶点入度等于出度）
• 未正确处理字典序要求

3.2 哈密顿图相关题目分析

例题2 （LeetCode 980. 不同路径 III）： 在二维网格上，有障碍物和空地，要求找到一条经过所有空格的路径。

解题思路 ：

1. 将网格建模为图，每个空格为顶点
2. 相邻空格之间添加边
3. 问题转化为寻找哈密顿路径
4. 使用回溯法+剪枝策略

优化技巧 ：

• 提前终止不可能完成的分支
• 使用位掩码记录访问状态
• 从度数较小的顶点开始搜索

4. 实战技巧与避坑指南

4.1 易混淆概念辨析

特征	欧拉图	哈密顿图
关注对象	边	顶点
判定复杂度	多项式时间	NP完全
充分条件	度数条件	Ore/Dirac定理
典型应用	路径规划	旅行商问题

4.2 面试准备建议

1. 基础概念 ：

   • 熟记欧拉图和哈密顿图的定义
   • 理解判定条件的证明思路
   • 掌握经典算法实现

2. 题目练习 ：

   • 欧拉图相关：LeetCode 332, 753
   • 哈密顿图相关：LeetCode 980, 996

3. 思维训练 ：

   • 遇到新问题时，先判断属于哪类图论问题
   • 分析问题是否可以转化为欧拉或哈密顿问题
   • 考虑是否存在更优的近似解法

在实际面试中，我曾遇到一个变种的哈密顿路径问题，需要在特定约束条件下找到最短的顶点遍历路径。通过将问题分解为连通性检查和回溯搜索两个阶段，最终给出了可行的解决方案。这种分而治之的思路在处理复杂图论问题时往往非常有效。