数据结构与算法——Hamiltonian Cycles

#include <iostream>

using namespace std;

int n = 5;
int x[6] = {0,1};
int G[6][6] = {
    {0,0,0,0,0,0},
    {0,0,1,1,0,1},
    {0,1,0,1,1,1},
    {0,1,1,0,1,0},
    {0,0,1,1,0,1},
    {0,1,1,0,1,0}
};

void NextVetex(int k){
    do
    {
        x[k] = (x[k] + 1) % (n + 1);
        if(x[k] == 0){
            return;
        }
        // 确保和前一个节点联通
        if(G[x[k - 1]][x[k]] != 0){
            int j = 1;
            // 确保节点不会重复
            for(; j < k; ++j){
                if(x[j] == x[k]){
                    break;
                }
            }
            if(j == k){
                // 如果不是最后一个节点
                // 或者是最后一个节点，并且最后一个节点和第一个节点是联通的
                if((k < n) || (k == n && G[x[n]][x[1]] != 0))
                {
                    return;
                }
            }
        }
    }while(true);
}

void Hamiltonian(int k){
    do
    {
        NextVetex(k);
        if(x[k] == 0){
            return;
        }
        // 如果是最后一个节点，说明是一个环，打印结果
        if(k == n){
            for(int i = 1; i <= n; ++i){
                cout << x[i] << " ";
            }
            cout << endl;
        }
        else{
            Hamiltonian(k + 1);
        }
    }while(true);
}
 
int main() 
{
    Hamiltonian(2);
    return 0;
}

Output:
1 2 3 4 5 
1 2 5 4 3 
1 3 2 4 5 
1 3 4 2 5 
1 3 4 5 2 
1 5 2 4 3 
1 5 4 2 3 
1 5 4 3 2