C语言用回溯法解决哈密顿回路问题
时间: 2023-06-25 19:05:24 浏览: 66
哈密顿回路问题是指在一个无向图中是否存在一条路线,使得经过每个节点恰好一次后再回到起点。下面是一个用回溯法解决哈密顿回路问题的 C 语言实现。
```c
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 20
bool graph[MAX_VERTICES][MAX_VERTICES];
int path[MAX_VERTICES];
int n;
bool is_valid(int v, int k) {
if (!graph[path[k-1]][v]) {
return false;
}
for (int i = 0; i < k; i++) {
if (path[i] == v) {
return false;
}
}
return true;
}
bool find_hamiltonian(int k) {
if (k == n) {
if (graph[path[n-1]][path[0]]) {
return true;
} else {
return false;
}
}
for (int v = 1; v < n; v++) {
if (is_valid(v, k)) {
path[k] = v;
if (find_hamiltonian(k+1)) {
return true;
}
path[k] = -1;
}
}
return false;
}
void print_hamiltonian() {
printf("Hamiltonian cycle:\n");
for (int i = 0; i < n; i++) {
printf("%d ", path[i]);
}
printf("%d\n", path[0]);
}
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]);
}
}
for (int i = 0; i < n; i++) {
path[i] = -1;
}
path[0] = 0;
if (find_hamiltonian(1)) {
print_hamiltonian();
} else {
printf("No Hamiltonian cycle found.\n");
}
return 0;
}
```
在上面的代码中,我们使用了一个 `graph` 数组来存储图的邻接矩阵,使用一个 `path` 数组来存储当前已经走过的路径,使用一个布尔型函数 `is_valid` 来判断当前节点是否可以加入路径中,使用一个递归函数 `find_hamiltonian` 来查找哈密顿回路。如果找到了哈密顿回路,则调用 `print_hamiltonian` 函数打印出路径。