C语言 无法获得所需的正确输出

ix0qys7i  于 2023-08-03  发布在  其他
关注(0)|答案(1)|浏览(103)

我试图用回溯法解决输入图是否有源顶点的哈密顿回路和路径问题。当所有顶点都被访问到输入图中时,将显示路径。使用回溯方法,我想得到输入图的所有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);
}

字符串
但在输出中,输出屏幕中没有显示任何内容

lyr7nygr

lyr7nygr1#

一个错误是通过n = i;覆盖了原始顶点n,因此稍后重置visited[n] = -1;不起作用。第二个错误是f在回溯时只递增而从不递减。我们可以通过改变

n = i;
                     ans[f++] = i;
                     Hamilton(G, visited, n, f);

字符串

ans[f] = i;
                     Hamilton(G, visited, i, f+1);

  • 在一般情况下(不具有给定G的循环图)仍然存在的问题是,该Hamilton函数仅找到从顶点0开始的路径。

相关问题