hamiltonian_path.cpp

// hamiltonian_path.cpp
// -----------------------------------------------------------------
// Hamiltonian Path / Cycle：狀態壓縮 DP（bitmask DP）
//   dp[S][v] = 「是否存在一條路徑，恰好走過集合 S 的點，且結尾在 v」
//   轉移：dp[S | 1<<u][u] |= dp[S][v]  (v,u 相鄰, u 不在 S)
//   複雜度 O(2^n · n^2)，比 O(n!) 枚舉好非常多
//
// Compile: g++ -std=c++17 -O2 -Wall -Wextra -o hamiltonian_path hamiltonian_path.cpp
// -----------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>

using namespace std;

class Hamiltonian {
    int n;
    vector<unsigned> adj;                    // bitmask 鄰接
    vector<vector<int>> parent;              // parent[S][v] = 前一個點（還原用）
    vector<vector<char>> dp;
public:
    Hamiltonian(int n_) : n(n_), adj(n_, 0) {}
    void addEdge(int u, int v) {
        adj[u] |= 1u << v;
        adj[v] |= 1u << u;
    }

    // 找 Hamiltonian Path（起點任意）；回傳空 = 不存在
    vector<int> findPath() {
        buildDP(false);
        unsigned full = (1u << n) - 1;
        for (int v = 0; v < n; ++v)
            if (dp[full][v]) return reconstruct(full, v);
        return {};
    }

    // 找 Hamiltonian Cycle：固定起點 0（環的起點不影響存在性），
    // 尾點 v 需與 0 相鄰才能閉合
    vector<int> findCycle() {
        buildDP(true);                       // DP 只從點 0 起跑
        unsigned full = (1u << n) - 1;
        for (int v = 1; v < n; ++v)
            if (dp[full][v] && (adj[v] >> 0 & 1)) {
                auto path = reconstruct(full, v);   // 必以 0 開頭
                path.push_back(0);           // 閉合
                return path;
            }
        return {};
    }

    long long statesVisited = 0;
private:
    void buildDP(bool fixStartAtZero) {
        dp.assign(1u << n, vector<char>(n, 0));
        parent.assign(1u << n, vector<int>(n, -1));
        statesVisited = 0;
        if (fixStartAtZero)
            dp[1u][0] = 1;                   // 只允許從 0 出發
        else
            for (int v = 0; v < n; ++v)
                dp[1u << v][v] = 1;          // 單點路徑
        for (unsigned S = 1; S < (1u << n); ++S)
            for (int v = 0; v < n; ++v) {
                if (!dp[S][v]) continue;
                ++statesVisited;
                unsigned cand = adj[v] & ~S; // v 的鄰居中還沒走過的
                while (cand) {
                    int u = __builtin_ctz(cand);
                    cand &= cand - 1;
                    unsigned S2 = S | (1u << u);
                    if (!dp[S2][u]) {
                        dp[S2][u] = 1;
                        parent[S2][u] = v;
                    }
                }
            }
    }
    vector<int> reconstruct(unsigned S, int v) {
        vector<int> path;
        while (v != -1) {
            path.push_back(v);
            int p = parent[S][v];
            S &= ~(1u << v);
            v = p;
        }
        reverse(path.begin(), path.end());
        return path;
    }
};

static void printPath(const vector<int>& p) {
    if (p.empty()) { cout << "none\n"; return; }
    for (size_t i = 0; i < p.size(); ++i)
        cout << p[i] << (i + 1 < p.size() ? " -> " : "\n");
}

int main() {
    // ---- 範例 1：有 Path 沒 Cycle 的圖 ----
    cout << "=== Example 1: path exists, cycle doesn't ===\n";
    // 0-1-2-3-4 一條鏈 + 邊 1-3
    Hamiltonian h1(5);
    h1.addEdge(0,1); h1.addEdge(1,2); h1.addEdge(2,3); h1.addEdge(3,4);
    h1.addEdge(1,3);
    cout << "Hamiltonian path : ";
    printPath(h1.findPath());
    cout << "Hamiltonian cycle: ";
    printPath(h1.findCycle());
    cout << "\n";

    // ---- 範例 2：立方體圖 Q3（Path 和 Cycle 都有） ----
    cout << "=== Example 2: cube graph Q3 ===\n";
    Hamiltonian h2(8);
    for (int u = 0; u < 8; ++u)
        for (int b = 0; b < 3; ++b) {
            int v = u ^ (1 << b);            // 恰差一個位元 = 立方體的邊
            if (u < v) h2.addEdge(u, v);
        }
    cout << "Hamiltonian path : ";
    printPath(h2.findPath());
    cout << "Hamiltonian cycle: ";
    printPath(h2.findCycle());
    cout << "(cycle = 3-bit Gray code!)\n\n";

    // ---- 範例 3：Petersen 圖——著名的「有 Path 沒 Cycle」 ----
    cout << "=== Example 3: Petersen graph (famous non-Hamiltonian) ===\n";
    Hamiltonian h3(10);
    int petE[][2] = {{0,1},{1,2},{2,3},{3,4},{4,0},
                     {5,7},{7,9},{9,6},{6,8},{8,5},
                     {0,5},{1,6},{2,7},{3,8},{4,9}};
    for (auto& e : petE) h3.addEdge(e[0], e[1]);
    cout << "Hamiltonian path : ";
    printPath(h3.findPath());
    cout << "Hamiltonian cycle: ";
    printPath(h3.findCycle());
    cout << "\n";

    // ---- 範例 4：複雜度對比 O(2^n n^2) vs O(n!) ----
    cout << "=== Example 4: bitmask DP vs factorial enumeration ===\n";
    // n=18 的隨機圖
    Hamiltonian h4(18);
    unsigned seed = 987654321;
    auto nextRand = [&seed]() {
        seed = seed * 1103515245 + 12345;
        return (seed >> 16) & 0x7fff;
    };
    for (int u = 0; u < 18; ++u)
        for (int v = u + 1; v < 18; ++v)
            if (nextRand() % 100 < 30) h4.addEdge(u, v);
    auto t0 = chrono::steady_clock::now();
    auto path = h4.findPath();
    auto t1 = chrono::steady_clock::now();
    cout << "n=18: path " << (path.empty() ? "not found" : "FOUND")
         << " in " << chrono::duration<double, milli>(t1 - t0).count()
         << " ms (DP states with value=1: " << h4.statesVisited << ")\n";
    cout << "compare: 18! = 6,402,373,705,728,000 permutations\n";
    cout << "         2^18 * 18^2 = 84,934,656 DP transitions\n";
    if (!path.empty()) {
        cout << "path: ";
        printPath(path);
    }
    return 0;
}