我试图用回溯法解决输入图是否有源顶点的哈密顿回路和路径问题。当所有顶点都被访问到输入图中时,将显示路径。使用回溯方法,我想得到输入图的所有Hamilton路径或循环。
下面是我的代码:
#include<stdio.h>
#include<conio.h>
#include<stdbool.h>
int m=0;
int ans[5];
void Hamilton(int G[5][5], int visited[5], int n, int f){
if(m == 5-1){
for(int i=0;i<f;i++)
printf("%d ",ans[i]);
printf("\n");
return;
}
else{
visited[n] = n;
m++;
for(int i=0;i<5;i++){
if(G[n][i] == 1){
if(visited[i] == -1){
n = i;
ans[f++] = i;
Hamilton(G, visited, n, f);
}
}
}
visited[n] = -1;
m--;
return;
}
}
void main(){
int G[5][5] = {
{0,1,1,0,0},
{1,0,0,1,1},
{1,0,0,1,0},
{0,1,1,0,1},
{0,1,0,1,0}
};
int n = 0;
int visited[5] = {-1,-1,-1,-1,-1};
ans[0] = 0;
Hamilton(G, visited, n, 1);
}
字符串
但在输出中,输出屏幕中没有显示任何内容
1条答案
按热度按时间lyr7nygr1#
一个错误是通过
n = i;
覆盖了原始顶点n
,因此稍后重置visited[n] = -1;
不起作用。第二个错误是f
在回溯时只递增而从不递减。我们可以通过改变字符串
至
型
Hamilton
函数仅找到从顶点0开始的路径。