C语言 用蛮力法求解哈密顿回路

C语言中使用蛮力法（也称暴力搜索或穷举法）求解哈密顿回路是指通过尝试所有可能的路径组合，看是否能找到一条经过图中每一个顶点恰好一次并返回起点的回路。由于这种方法的时间复杂度非常高，通常适用于小规模的问题，对于大规模图可能会非常耗时。

以下是使用蛮力法的一个简单示例，这里假设我们有一个邻接矩阵表示的无向图：

#include <stdio.h>

#define V 4 // 图的顶点数
int graph[V][V] = {
    {0, 1, 0, 1},
    {1, 0, 1, 0},
    {0, 1, 0, 1},
    {1, 0, 1, 0}  // 例如一个4x4的图
};

// 检查给定的路径是否构成一个有效的哈密顿回路
int isValidPath(int path[], int n) {
    int i;
    for (i = 0; i < n; ++i)
        if (path[i] == -1 || path[i] == path[(i + 1) % n])
            return 0;
    return 1;
}

// 蛮力法寻找哈密顿回路
void findHamiltonianCycle(int n, int path[]) {
    // 初始化路径数组，除了第一个顶点，其他都是-1
    int i;
    for (i = 0; i < n; ++i)
        path[i] = -1;

    // 尝试所有可能的起始顶点
    for (i = 0; i < n; ++i) {
        // 从当前顶点开始构建路径
        path[0] = i;
        if (isValidPath(path, n)) {
            printf("找到哈密顿回路: ");
            for (i = 0; i < n; ++i)
                printf("%d ", path[i]);
            printf("\n");
            return; // 如果找到就直接结束循环
        }
    }
    printf("找不到哈密顿回路.\n");
}

int main() {
    int path[V];
    findHamiltonianCycle(V, path);
    return 0;
}