哈密尔顿图的c++代码实现

以下是哈密尔顿图的C代码实现：

#include <stdio.h>
#include <stdbool.h>

#define MAX_VERTICES 100 // 最大顶点数

int n; // 顶点数
int graph[MAX_VERTICES][MAX_VERTICES]; // 图的邻接矩阵

int path[MAX_VERTICES]; // 存储哈密尔顿回路的路径
bool visited[MAX_VERTICES]; // 标记顶点是否已经访问过

bool is_valid(int v, int pos)
{
// 判断顶点v是否可以加入路径的pos位置
if (graph[path[pos - 1]][v] == 0) {
return false; // v和前一个顶点没有边相连
}

for (int i = 0; i < pos; i++) {
if (path[i] == v) {
return false; // v已经在路径中出现过了
}
}

return true;
}

bool hamiltonian_cycle_util(int pos)
{
if (pos == n) {
// 找到了哈密尔顿回路
if (graph[path[pos - 1]][path[0]] == 1) {
return true;
} else {
return false;
}
}

for (int v = 1; v < n; v++) {
if (is_valid(v, pos)) {
path[pos] = v;
visited[v] = true;

if (hamiltonian_cycle_util(pos + 1)) {
return true;
}

visited[v] = false;
}
}

return false;
}

bool hamiltonian_cycle()
{
// 从顶点0开始搜索哈密尔顿回路
path[0] = 0;
visited[0] = true;

if (hamiltonian_cycle_util(1)) {
// 找到了哈密尔顿回路，输出路径
printf("Hamiltonian cycle found:\n");

for (int i = 0; i < n; i++) {
printf("%d ", path[i]);
}

printf("%d\n", path[0]);

return true;
} else {
printf("No Hamiltonian cycle found.\n");

return false;
}
}

int main()
{
printf("Enter the number of vertices: ");
scanf("%d", &n);

printf("Enter the adjacency matrix:\n");

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}

if (hamiltonian_cycle()) {
printf("Hamiltonian cycle exists.\n");
} else {
printf("Hamiltonian cycle does not exist.\n");
}

return 0;
}