哈密尔顿路径要求访问图中每个顶点恰好一次，通常用于解决旅行商问题（TSP）或状态压缩DP问题。
哈密尔顿路径（Hamiltonian Path）是指在一个图中经过每个顶点恰好一次的路径。如果这条路径的起点和终点相同（即形成一个环），则称为哈密尔顿回路（Hamiltonian Cycle）。
关键点
与欧拉路径的区别：
- 欧拉路径：经过每条边恰好一次（顶点可重复）。
- 哈密尔顿路径：经过每个顶点恰好一次（边可不全用）。
计算复杂度：
- 判定一个图是否存在哈密尔顿路径是 NP完全问题（没有已知的多项式时间算法）。
- 但某些特殊图（如完全图、竞赛图）一定存在哈密尔顿路径。
相关 LeetCode 题目
Reconstruct Itinerary
- 问题：给定一组机票
[from, to]，找出从 “JFK” 出发的行程，使得所有机票都被使用一次（类似哈密尔顿路径）。 - 解法：欧拉路径 + 后序遍历（Hierholzer 算法）。
- 实现细节：⭐算法OJ⭐重建行程【哈密尔顿路径】（C++ 实现）Reconstruct Itinerary
- 关键点：
- 需要按字典序访问。
- 使用优先队列（最小堆）存储邻接表。
- 后序遍历 + 逆序输出。
Unique Paths III
- 问题：在 2D 网格中，从起点到终点，必须经过所有无障碍方格（哈密尔顿路径）。
- 解法：回溯 + 状态压缩（DFS + Bitmask）。
- 实现细节：⭐算法OJ⭐矩阵的相关操作【深度优先搜索 DFS + 回溯】（C++ 实现）Unique Paths 系列
- 关键点：
- 统计必须访问的格子数。
- 用
visited或位掩码记录访问状态。
Find the Shortest Superstring
- 问题：给定一组字符串，找到包含所有字符串的最短字符串（类似 TSP）。
- 解法：动态规划 + 状态压缩（类似哈密尔顿路径）。
- 实现细节：⭐算法OJ⭐寻找最短超串【动态规划 + 状态压缩】（C++ 实现）Find the Shortest Superstring
- 关键点：
- 预处理阶段：计算重叠部分。首先我们需要计算任意两个字符串之间的最大重叠长度。
- 动态规划解法：这是一个状态压缩DP问题，类似于旅行商问题(TSP)。
