哈密尔顿路径（Hamiltonian Path）及相关算法题目

哈密尔顿路径要求访问图中每个顶点恰好一次，通常用于解决旅行商问题（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)。