哈密顿路径检查器

检查图是否包含哈密顿路径或哈密顿回路。运行带有 Warnsdorff 剪枝的回溯算法，验证连通性和度数先决条件，测试 Dirac 和 Ore 充分条件，并在动画 SVG 可视化中显示见证路径。

哈密顿路径检查器

哈密顿路径检查器判定图中是否包含哈密顿路径（经过每个顶点恰好一次的序列）或哈密顿回路（额外返回起始顶点的路径）。它结合了快速的结构预检查（连通性、度数前提条件、Dirac 定理、Ore 定理）以及通过 Warnsdorff 启发式优化的回溯搜索，并通过逐步动画可视化见证路径。

什么是哈密顿路径？

给定一个具有 n 个顶点的图 G = (V, E)，哈密顿路径是所有顶点的一个有序序列 v₁, v₂, …, v_n，使得每一对相邻的 (v_i, v_i+1) 都是 G 的一条边，且每个顶点恰好出现一次。如果 (v_n, v₁) 也是一条边，则该序列称为哈密顿回路。

哈密顿路径： v1 — v2 — v3 — … — vn (全部互异，且每一对相邻顶点间有边) 哈密顿回路： v1 — v2 — v3 — … — vn — v1 (闭合回起点)

该问题以 William Rowan Hamilton 的名字命名，他在 1857 年发明了 Icosian game——一个要求玩家找到一条经过正十二面体每个顶点恰好一次的回路的谜题。

难点所在：NP-Completeness

哈密顿路径判定问题和哈密顿回路判定问题都是 NP-complete 的 (Karp, 1972)。除非 P = NP，否则不存在能解决所有实例的多项式时间算法。在最坏情况下，回路搜索的回溯搜索树规模高达 (n−1)!。这就是为什么该计算器将输入限制在 20 个顶点以内的原因——n 的微小多项式增长会导致运行时间的爆炸式增加。

在实践中，Warnsdorff 启发式算法（最初由 Heinrich Warnsdorff 于 1823 年为“骑士巡游”问题设计）使结构化图的搜索速度显著提高：在每一步中，算法都会将当前路径扩展到具有最少剩余未访问邻居的未访问邻居。这种贪心规则可以防止搜索进入死胡同，并且通常在性质良好的图上能以零回溯找到哈密顿巡游。

必要条件 — 快速拒绝

在运行昂贵的搜索之前，计算器会拒绝那些绝对不可能包含哈密顿路径的图：

连通性： 哈密顿路径必须访问每个顶点，因此图必须只有一个连通分量。对于有向图，要求弱连通（忽略箭头方向）。
度数（无向）： 最多只有两个顶点的度数为 1——它们只能作为路径的端点。对于哈密顿回路，每个顶点的度数必须至少为 2。
度数（有向）： 对于哈密顿路径，最多只能有一个顶点入度为 0（起点），且最多只能有一个顶点出度为 0（终点）。对于哈密顿回路，每个顶点的入度和出度都必须 ≥ 1。

这些规则能在线性时间内拒绝许多无望的输入，避免浪费回溯精力。

充分条件 — 经典定理

几个经典定理给出了保证无向简单图中存在哈密顿回路的充分（而非必要）条件。如果其中任何一个适用，计算器会将结果标记为“保证存在”，甚至无需运行搜索——尽管它仍会展示一条见证回路。

Dirac 定理 (1952)

如果 G 是一个具有 n ≥ 3 个顶点的简单无向图，且每个顶点的度数至少为 n / 2，那么 G 具有哈密顿回路。

δ(G) ≥ n / 2 ⟹ G 是哈密顿图

Ore 定理 (1960)

如果对于每一对不相邻的顶点 u 和 v，都有 deg(u) + deg(v) ≥ n，那么 G 具有哈密顿回路。Ore 条件比 Dirac 条件更宽松，因此 Ore 定理涵盖了 Dirac 定理的情况。

∀ 不相邻顶点 u, v: deg(u) + deg(v) ≥ n ⟹ G 是哈密顿图

Dirac 或 Ore 条件不满足并不意味着图缺乏哈密顿回路——许多图两者都不满足但仍包含回路（例如，一个大型简单 n-回路的最小度数为 2，远低于 n/2）。

内置搜索算法

当预检查无法得出结论时，计算器会在图的邻接表示上运行回溯搜索。关键策略包括：

位掩码已访问集合： 已访问的顶点存储为位掩码（对于 20 个顶点的图，成员测试速度为快 O(1)）。
Warnsdorff 启发式： 在每次扩展时，按邻居的剩余未访问度数排序进行尝试（从小到大），模拟“低分支”顺序。
根节点选择： 对于哈密顿回路，只需要一个起始顶点（回路具有旋转不变性）。对于哈密顿路径，起始节点按出度升序尝试——优先尝试最稀有的位置。
步骤预算： 硬限制防止极端实例无限运行；如果预算耗尽，UI 将报告结果为“超时”。

哈密顿 vs 欧拉

哈密顿问题和欧拉问题容易混淆——它们听起来很像，但有本质区别：

属性	哈密顿路径 / 回路	欧拉通路 / 回路
访问每个…	顶点恰好一次	边恰好一次
复杂性	NP-complete	多项式 (O(n+m))
判定条件	无简单特征描述	连通 + 所有度数为偶数（回路）；最多 2 个奇数度（通路）
命名来源	W. R. Hamilton (1857)	L. Euler (1736, 柯尼斯堡七桥)
经典示例	旅行推销员问题, Icosian game	线路巡检, 邮递员问题

支持的输入格式

边列表

每行一条边，或用逗号分隔。支持的连接符：A-B, A B, A,B, A--B, A->B, A<-B。使用 -> 强制按有向图解析。

A-B, B-C, C-D, D-A, A-C (具有 5 条边的无向图) A->B, B->C, C->D, D->A (有向 4-回路)

邻接矩阵

0/1 值的方阵，每行一个，空格或逗号分隔。可在“矩阵标签”字段中提供可选标签；否则将自动使用 A, B, C…。

0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0

如何使用此检查器

选择输入格式 — 手写的小型图使用“边列表”，从代码或教材粘贴时使用“邻接矩阵”。
粘贴您的图 到文本区域。对于矩阵输入，可选提供顶点标签。
选择检查内容：仅路径、仅回路，或一次性检查两者。
选择图类型 — “自动检测”会根据箭头样式 (->) 或矩阵对称性推断有向性。
点击“检查哈密顿”。 结果页面会显示判定标题、必要条件预检查、Dirac / Ore 充分条件测试、见证路径（如果存在）以及交互式可视化。
重现见证过程 使用播放 / 单步控件。观察路径在图上逐边点亮。

应用实例 — Petersen 图

著名的 Petersen 图（10 个顶点，15 条边，3-正则图）是具有哈密顿路径但没有哈密顿回路的典型教材案例。将以下内容粘贴到边列表字段并点击检查：

1-2, 2-3, 3-4, 4-5, 5-1, 6-8, 8-10, 10-7, 7-9, 9-6, 1-6, 2-7, 3-8, 4-9, 5-10

检查器确认：找到哈密顿路径（例如 1 — 2 — 7 — 10 — 5 — 4 — 9 — 6 — 8 — 3），但详尽搜索未发现能闭合回路的方法——这一结论最早在 1890 年代得到证明。

常见应用

路由与旅行推销员问题 — 每个 TSP 巡游都是完全带权图中的哈密顿回路。
基因组组装 — 从重叠读取中重建 DNA 序列可以建模为重叠图中的哈密顿路径。
电路布局 — 在 PCB 上排列引脚以实现最小长度布线。
游戏 AI 与谜题求解 — 棋盘上的骑士巡游、Icosian game。
调度 — 为任务排序，使每个任务都能可行地转换到下一个。
组合学教学 — 用可手算的微型示例演示 NP-completeness。

常见问题解答

什么是哈密顿路径？

哈密顿路径是图中经过每个顶点恰好一次的路径。它以 William Rowan Hamilton 的名字命名，他于 1857 年研究了十二面体图上的这一问题。判断此类路径是否存在是一个 NP-complete 问题，因此目前没有已知的多项式时间算法能解决所有图的这一问题。

哈密顿回路与哈密顿路径有何不同？

哈密顿回路是一条返回起始顶点的哈密顿路径，形成一个经过每个顶点恰好一次的闭合回路。每个哈密顿回路都包含一条哈密顿路径（只需去掉闭合边），但反之不成立：许多图具有哈密顿路径但没有哈密顿回路。

Dirac 定理的内容是什么？

Dirac 定理 (1952) 指出，对于任何具有 n ≥ 3 个顶点的简单无向图，如果每个顶点的度数至少为 n/2，则该图包含哈密顿回路。这是一个充分但不必要条件：许多未达到 Dirac 阈值的图仍然拥有哈密顿回路。

Ore 定理的内容是什么？

Ore 定理 (1960) 指出，如果对于具有 n ≥ 3 个顶点的简单图中的每一对不相邻顶点 u 和 v，它们的度数之和至少为 n，则该图具有哈密顿回路。Ore 条件比 Dirac 条件更弱，因此只要 Dirac 定理适用，Ore 定理也适用。

为什么搜索限制在 20 个顶点以内？

哈密顿路径和回路判定问题属于 NP-complete。最坏情况下的运行时间随顶点数量呈指数级增长。通过剪枝和 Warnsdorff 启发式算法，计算器可以快速处理许多 20 个顶点以内的小型图，但更复杂的情况可能会超时。超过 20 个顶点后，建议使用 Concorde 等专业求解器或整数规划建模。

什么是 Warnsdorff 启发式算法？

Warnsdorff 规则由 Heinrich Warnsdorff 于 1823 年针对“骑士巡游”问题提出，该规则建议在每一步都访问下一个具有最少未访问邻居的顶点。这种贪心策略在实践中能极大地剪枝回溯树，并且在正则图上通常无需回溯即可找到哈密顿路径。

该工具会找到所有哈密顿路径吗？

不会 — 它在存在路径或回路时会找到单一的见证序列。计算哈密顿路径的总数本身是一个 #P-complete 问题，比判定问题难得多。对于枚举需求，专业的工具或整数规划求解器更为合适。

延伸阅读

引用此内容、页面或工具为：

"哈密顿路径检查器" 于 https://MiniWebtool.com/zh-cn/哈密顿路径检查器/，来自 MiniWebtool，https://MiniWebtool.com/

由 miniwebtool 团队制作。更新日期：2026年4月21日

您还可以尝试我们的 AI数学解题器 GPT，通过自然语言问答解决您的数学问题。

其他相关工具:

哈密顿路径检查器