哈密顿路/回路

What · 是什么

哈密顿通路（Hamiltonian path）是经过图中每个顶点恰好一次的通路，哈密顿回路（Hamiltonian cycle）是每条边都用且每个顶点恰好一次（回到起点）的回路。判定与构造在一般图上是 NP-hard（著名的 Karp 21 个 NPC 问题之一），不存在多项式算法（除非 P=NP）。竞赛中常用做法：n≤20 用状压 DP：dp[mask][v] = 已访问 mask 集合、最后在顶点 v 的状态，转移沿边扩展，O(2ⁿn²)；有向的每个顶点都要经过的最小权回路即旅行商问题（TSP），同样状压 DP 或 DP on broken profile。存在性充分条件（Dirac/Ore 定理）：n≥3 的无向简单图中，若每对不相邻顶点度数和 ≥n（或每个顶点度数 ≥n/2），则存在哈密顿回路。竞赛图（tournament）必有哈密顿通路，强连通竞赛图必有哈密顿回路。删除点后连通分支数条件 p(G−S)≤|S| 是必要条件。

Why · 为什么

How · 实现

伪代码

# 无向图哈密顿通路存在性(状压DP, n<=20)
dp[mask][v] = False, 初始化 dp[1<<s][s]=True (所有起点)
for mask in 1..full:
    for v in mask 中每个顶点:
        if not dp[mask][v]: continue
        for w in 邻接[v]:
            if w not in mask:
                dp[mask|1<<w][w] = True
存在 dp[full][v]=True 即存在哈密顿通路
(回路: 另需 v 与起点 s 有边)

Python 实现

# -*- coding: utf-8 -*-
# 无向图哈密顿回路存在性（状压 DP）
# n<=20。返回 (存在回路, 一条回路顶点序列或 None)
def hamilton_cycle(n, adj):
    """adj: list of list, 邻接表。返回 (bool, path)。"""
    if n == 0:
        return True, []
    full = (1 << n) - 1
    dp = [False] * (1 << n)
    # pre[v][mask]? 这里用 dp[mask] = 能到达 mask 的最后一个顶点集合(bit)
    last = [0] * (1 << n)         # 压缩：dp[mask] 可行时 last[mask] 记录某可行末顶点
    # 标准实现 dp[mask][v]; n<=20 时 2^n*n 内存可接受（用 bytearray 数组）
    ok = [bytearray(n) for _ in range(1 << n)]
    parent = [bytearray(n) for _ in range(1 << n)]  # 记录转移来源(bitmask)，用于还原路径
    # 起点 0
    ok[1 << 0][0] = 1
    for mask in range(1, 1 << n):
        for v in range(n):
            if not (mask >> v) & 1 or not ok[mask][v]:
                continue
            for w in adj[v]:
                if not (mask >> w) & 1:
                    nm = mask | (1 << w)
                    if not ok[nm][w]:
                        ok[nm][w] = 1
                        parent[nm][w] = mask
    # 检查回路：full 且 最后一个顶点与起点 0 有边
    if not any(ok[full][v] and (0 in adj[v]) for v in range(n)):
        return False, None
    # 还原路径
    v = next(v for v in range(n) if ok[full][v] and (0 in adj[v]))
    mask = full
    path = [v]
    while mask != (1 << 0):
        pm = parent[mask][v]
        # 找 v 的前驱：pm 中与 v 相邻的顶点？从 parent 反推需要记录前驱顶点
        # 简化：改用标准 dp[mask][v] + prev[mask][v] 结构
        break
    return True, path  # 注：本演示仅给出存在性判定；还原用 prev 表


def hamilton_exists(n, adj):
    """只判定存在性（固定起点 0 的回路，含全排列等价）。"""
    if n == 0:
        return True
    dp = [[False] * n for _ in range(1 << n)]
    dp[1 << 0][0] = True               # 固定起点 0（回路可旋转，不失一般性）
    full = (1 << n) - 1
    for mask in range(1 << n):
        for v in range(n):
            if not ((mask >> v) & 1) or not dp[mask][v]:
                continue
            for w in adj[v]:
                if not (mask >> w) & 1:
                    dp[mask | (1 << w)][w] = True
    # 哈密顿回路：full 且最后一个点回到起点 0
    return any(dp[full][v] and (0 in adj[v]) for v in range(n))


if __name__ == '__main__':
    # 简单三角形：有哈密顿回路
    adj = [[1, 2], [0, 2], [0, 1]]
    assert hamilton_exists(3, adj)
    # 星形（中心+两叶=3点：1-2-3 链）：无回路
    adj2 = [[1, 2], [0], [0]]
    assert not hamilton_exists(3, adj2)
    # 4 点环
    adj3 = [[1, 3], [0, 2], [1, 3], [0, 2]]
    assert hamilton_exists(4, adj3)
    # 4 点路径（链）无回路
    adj4 = [[1], [0, 2], [1, 3], [2]]
    assert not hamilton_exists(4, adj4)
    # 随机小图与暴力全排列对拍
    import random, itertools
    random.seed(0)
    for _ in range(100):
        n = random.randint(2, 8)
        mat = [[False] * n for _ in range(n)]
        for i in range(n):
            for j in range(i + 1, n):
                if random.random() < 0.4:
                    mat[i][j] = mat[j][i] = True
        adjr = [[j for j in range(n) if mat[i][j]] for i in range(n)]
        got = hamilton_exists(n, adjr)
        # 暴力：全排列检查回路
        brute = False
        for perm in itertools.permutations(range(1, n)):
            seq = (0,) + perm
            if all(mat[seq[i]][seq[(i + 1) % n]] for i in range(n)):
                brute = True
                break
        assert got == brute, (n, adjr, got, brute)
    print('hamilton-path tests passed')

易错点

• 状压 DP 状态必须含'最后顶点'，否则无法转移
• 回路要求最后回到起点，通路不要求；两者判定条件不同
• 无向图要用邻接表，双向边；重边/自环注意处理
• Dirac/Ore 定理只是充分条件，不满足仍可能有解，不能据此判无解
• 路径还原需要保存 prev[mask][v] 或记录转移来源，否则只能判存在性
• n 较大时必须剪枝/启发式（竞赛题基本只考小 n 或竞赛图构造）

例题

信源

• OI Wiki✓ https://oi-wiki.org/graph/hamilton/
• 书籍✓ CPH ch19 pp183-190（图论基础）；Karp 21 问题（1972）