使用回溯法求解哈密顿路径与循环问题时无输出的求助

尝试用回溯法解决从指定源顶点出发的图的哈密顿路径与循环问题，要求遍历所有顶点时输出路径，期望获取所有哈密顿路径或循环。但以下C代码运行后无任何输出：

#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. 循环内修改顶点变量破坏回溯逻辑：在for循环中直接修改n = i，导致当前层的顶点状态被篡改，后续循环迭代错误，且回溯时无法恢复原顶点的访问标记。
2. visited数组标记逻辑混乱：用顶点值n赋值visited[n]，虽然初始为-1，但标记方式不直观，且回溯时的恢复依赖正确的当前顶点，容易出错。
3. 全局变量m引发状态冲突：递归过程中全局变量的状态无法隔离，容易出现计数错误，导致终止条件判断失效。

修复后的代码 #

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

int ans[5];

void Hamilton(int G[5][5], int visited[5], int current, int pathLen) {
    // 路径包含所有顶点时输出
    if (pathLen == 5) {
        for (int i = 0; i < 5; i++) {
            printf("%d ", ans[i]);
        }
        // 判断是否为哈密顿回路（起点与终点相连）
        if (G[current][ans[0]] == 1) {
            printf("(回路)");
        }
        printf("\n");
        return;
    }

    visited[current] = 1;
    for (int i = 0; i < 5; i++) {
        // 存在边且未访问该顶点
        if (G[current][i] == 1 && visited[i] == 0) {
            ans[pathLen] = i;
            Hamilton(G, visited, i, pathLen + 1);
        }
    }
    // 回溯：取消当前顶点的访问标记
    visited[current] = 0;
}

int 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 visited[5] = {0}; // 0=未访问，1=已访问
    ans[0] = 0; // 起点为0
    Hamilton(G, visited, 0, 1);
    return 0;
}

修复说明 #

• 移除全局变量m，改用pathLen参数跟踪当前路径的顶点数，避免递归间的状态冲突。
• 循环内不再修改当前顶点变量current，直接传递i作为下一个递归的顶点，保证当前层状态不受影响。
• visited数组改用0/1标记访问状态，逻辑清晰，回溯时恢复操作可靠。
• 增加哈密顿回路的判断与标注，完善输出信息。
• 移除不必要的conio.h头文件，提升代码兼容性。

内容的提问来源于stack exchange，提问作者Suman Bhattacharya