汉密尔顿回路与路径 (Hamiltonian Cycle & Path)¶

汉密尔顿路径 (Hamiltonian Path)：经过图中每个顶点恰好一次的路径。
汉密尔顿回路 (Hamiltonian Cycle)：起点与终点相同，且除起点外经过每个顶点恰好一次的回路。

不同于可以在 \(\mathcal{O}(V + E)\) 判定的欧拉回路，判定一般图中是否存在汉密尔顿回路是一个著名的 NP-完全问题 (NP-Complete)。

经典充分性判定定理¶

对于包含 \(n \ge 3\) 个顶点的无向简单图：

狄拉克定理 (Dirac's Theorem)：若对图中任意顶点 \(u\)，均有其度数 \(\deg(u) \ge \lceil n / 2 \rceil\)，则图一定存在汉密尔顿回路。
奥尔定理 (Ore's Theorem)：若对图中任意一对不相邻的顶点 \(u, v\)，均满足 \(\deg(u) + \deg(v) \ge n\)，则图一定存在汉密尔顿回路。

状态压缩动态规划求解 (TSP / 最短汉密尔顿回路)¶

在算法竞赛中，当 \(n \le 20 \sim 22\) 时，通常采用状态压缩 DP (Bitmask DP) 求解最短汉密尔顿路径或回路（旅行商问题，TSP）。

设二进制掩码 \(mask \in [1, 2^n - 1]\) 表示已访问顶点的集合（第 \(i\) 位为 \(1\) 表示点 \(i\) 已访问）。
定义 \(dp[mask][u]\) 表示当前已走过的节点集合为 \(mask\)，且当前停留在节点 \(u\) 时的最小路径权值。
状态转移方程：

\[ dp[mask \mid (1 \ll v)][v] = \min \big( dp[mask \mid (1 \ll v)][v],\; dp[mask][u] + \text{weight}(u, v) \big) \]

时间复杂度：\(\mathcal{O}(2^n \cdot n^2)\)，空间复杂度：\(\mathcal{O}(2^n \cdot n)\)。

#include <vector>
#include <algorithm>

constexpr long long INF = 0x3f3f3f3f3f3f3f3fLL;

// dist[u][v] 为 u 到 v 的有向边权 (不存在边设为 INF)
// 返回从起点 0 出发，遍历所有节点恰好一次的最短路径长度
long long hamiltonian_path(int n, const std::vector<std::vector<long long>> &dist) {
    int total_states = 1 << n;
    std::vector<std::vector<long long>> dp(total_states, std::vector<long long>(n, INF));

    dp[1][0] = 0; // 起点为 0，初始状态仅包含点 0 (掩码二进制 00...001)

    for (int mask = 1; mask < total_states; ++mask) {
        for (int u = 0; u < n; ++u) {
            if (dp[mask][u] == INF) continue;

            // 枚举下一个前往的顶点 v
            for (int v = 0; v < n; ++v) {
                if (!(mask & (1 << v)) && dist[u][v] != INF) {
                    int next_mask = mask | (1 << v);
                    dp[next_mask][v] = std::min(dp[next_mask][v], dp[mask][u] + dist[u][v]);
                }
            }
        }
    }

    // 求访问完所有点 (mask == (1 << n) - 1) 的最短路径
    long long ans = INF;
    for (int u = 0; u < n; ++u) {
        ans = std::min(ans, dp[total_states - 1][u]);
    }
    return ans;
}

// 求解汉密尔顿回路 (最后回到起点 0)
long long tsp_cycle(int n, const std::vector<std::vector<long long>> &dist) {
    int total_states = 1 << n;
    std::vector<std::vector<long long>> dp(total_states, std::vector<long long>(n, INF));
    dp[1][0] = 0;

    for (int mask = 1; mask < total_states; ++mask) {
        for (int u = 0; u < n; ++u) {
            if (dp[mask][u] == INF) continue;
            for (int v = 0; v < n; ++v) {
                if (!(mask & (1 << v)) && dist[u][v] != INF) {
                    dp[mask | (1 << v)][v] = std::min(dp[mask | (1 << v)][v], dp[mask][u] + dist[u][v]);
                }
            }
        }
    }

    long long min_cycle = INF;
    for (int u = 1; u < n; ++u) {
        if (dp[total_states - 1][u] != INF && dist[u][0] != INF) {
            min_cycle = std::min(min_cycle, dp[total_states - 1][u] + dist[u][0]);
        }
    }
    return min_cycle;
}

LeetCode 经典真题精选与题解提示¶

LeetCode 847 - 访问所有节点的最短路径 (Shortest Path Visiting All Nodes) 困难
提示

状压 BFS 求全遍历最短路 / 广义哈密顿问题。
- 允许节点和边重复访问，求遍历全部 \(n\) 个节点的最短路径长度；
- 状态定义为二元组 \((u, mask)\)：当前位于节点 \(u\)，已访问过的节点集合为 \(mask\)；
- 由于边权均为 1，直接以所有单一节点初始状态 \((i, 1 \ll i)\) 作为多源起点运行 BFS，首次到达 \(mask == (1 \ll n) - 1\) 时的搜索层数即为全局最短步数。
LeetCode 943 - 最短超级串 (Find the Shortest Superstring) 困难
提示

有向图 TSP 模型 / 状压 DP 路径回溯。
- 计算任意两个单词 \(words[i]\) 拼接到 \(words[j]\) 时所能重叠的最大公共前后缀长度 \(overlap[i][j]\)；
- 问题等价于在包含所有单词的有向完全图中，寻找一条访问所有节点恰好一次且边权（重叠字符数）和最大的哈密顿路径（即 TSP 最长路）；
- 用状压 DP \(dp[mask][u]\) 记录前驱指针回溯出最优顺序。
LeetCode 980 - 不同路径 III (Unique Paths III) 困难
提示

网格图哈密顿路径回溯搜索。
- 要求从起点走到终点，且经过每一个无障碍空方格恰好一次；
- 这是标准的网格图哈密顿简单路径计数问题；
- 统计空地总数 \(empty\)，DFS 回溯过程中维护已走步数，当到达终点且已走步数恰好等于 \(empty + 1\) 时计数 \(+1\)。