c语言哈密顿回路回溯法

哈密顿回路问题是指在一个无向图中，找到一条经过每个节点恰好一次的回路。回溯法是一种常用的解决哈密顿回路问题的方法。

下面是使用回溯法解决哈密顿回路问题的C语言代码：

#include <stdio.h>
#define MAX 20

int n; // 图中节点数量
int a[MAX][MAX]; // 图的邻接矩阵
int x[MAX]; // 存储当前回路的节点编号

// 判断节点i是否可以加入到当前回路中
int is_ok(int i, int k)
{
    if (a[x[k-1]][i] == 0) // i和前一个节点不相邻
        return 0;
    for (int j = 1; j < k; j++) // i和之前的节点重复
        if (x[j] == i)
            return 0;
    return 1;
}

// 输出当前回路
void print_hamilton()
{
    for (int i = 1; i <= n; i++)
        printf("%d ", x[i]);
    printf("%d\n", x[1]); // 回路闭合，输出起点
}

// 回溯求哈密顿回路
void hamilton(int k)
{
    if (k > n) { // 找到一个哈密顿回路
        if (a[x[n]][x[1]] == 1) // 回路闭合
            print_hamilton();
    }
    else {
        for (int i = 2; i <= n; i++) { // 枚举所有节点，从第二个节点开始
            if (is_ok(i, k)) { // 如果节点i可以加入到当前回路中
                x[k] = i; // 将节点i加入到回路中
                hamilton(k+1); // 继续搜索下一个节点
                x[k] = 0; // 回溯
            }
        }
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &a[i][j]);
    x[1] = 1; // 从节点1开始
    hamilton(2); // 从第二个节点开始搜索
    return 0;
}

该算法的时间复杂度为 $O(n!)$，在节点数量较大时，可能会超时。