Hamiltonian Path: 모든 정점 한 번씩

Hamiltonian Path, 해밀턴 경로, Hamiltonian Cycle

정의

Hamiltonian Path 는 그래프의 모든 정점을 정확히 한 번씩 방문하는 경로. 시작 = 끝이면 Hamiltonian Cycle.

일반 그래프에서 NP-complete. Euler path (모든 간선을 한 번씩) 와 대비: Euler 는 다항 시간.

Bitmask DP (N ≤ 20)

상태: dp[mask][v] = “방문 집합 = mask, 현재 v” 도달 가능한가.

dp[1 << s][s] = true;   // s 에서 시작
for (int mask = 0; mask < (1 << n); mask++)
    for (int u = 0; u < n; u++) {
        if (!dp[mask][u] || !(mask & (1 << u))) continue;
        for (int v : adj[u])
            if (!(mask & (1 << v)))
                dp[mask | (1 << v)][v] = true;
    }
// 전체 마스크에서 도달 가능한 v 가 있으면 Hamiltonian path 존재

시간 O(2^N · N²), 공간 O(2^N · N).

관련

• TSP (Hamiltonian cycle + 최소 비용)
• Bitmask DP

참고

• Traveling Salesman Problem
• DP Bitfield