编辑代码

#include <stdio.h>

#define MAX 100
/*
算法-无向图连通图-哈密尔顿Hamilton回路。
从无向连通图的某个顶点出发，经过图上所有其他顶点一次且仅一次，最后回到该顶点的路径。
n: 图中的顶点数
x[]:访问的顶点编号，从0开始
c[][]:图的邻接矩阵
*/
void hamilton(int n, int x[MAX], int c[MAX][MAX]){
    int i,k;//统计变量，当前已经访问的顶点数为k+1
    int visited[MAX];//第k个顶点的访问标志，0表示未访问，1表示已访问
    //初始化x数组和visited数组
    for( i = 0; i <= n ; i++){
        x[i] = 0;
        visited[i] = 0;
    }
    printf("初始化\n");
    //访问起始顶点
    k = 0;
    visited[0] = 1;/*(1)*///第一个顶点，设置为访问
    x[0] = 0;//第k个访问的顶点编号，从0开始
    k = k + 1;
    //访问其他顶点
    while(k >= 0){
        x[k] = x[k] + 1;
        printf("顶点 %d, 访问 %d\n", k, x[k]);
        while(x[k] < n){
            // 不知道为啥，会输出(好像int溢出了)：搜索 顶点 2, 访问 1, 上个 1, 连接 32765
            i = x[k-1];
            printf("搜索 顶点 %d, 访问 %d, 上个 %d, 连接 %d\n", k, x[k], i, c[i][x[k]]);
            if(/*(2)*/visited[x[k]]==0 && c[i][x[k]] == 1){//邻接顶点x[k]未被访问过
                printf("%d-%d 连通未记录\n", k-1, k);
                break;
            }else{
                x[k] = x[k]+1;
            }
        }
        printf("-顶点 %d, 访问 %d\n", k, x[k]);
        if(x[k] < n && k == n-1&& /*(3)*/ c[x[k]][0] == 1 ){//找到一条哈密尔顿回路
            printf("结束\n");
            for(i = 0; i < n ; k++){
                printf("%d-- ", x[k]);
            }
            printf("%d-- ", x[0]);
            return;
        }else if( x[k]<n && k<n-1){//设置当前顶点的访问标志，继续下一个顶点
            printf("记录 顶点=%d,x[k]=%d,visited[x[k]]=%d\n", k, x[k], visited[x[k]]);
            visited[x[k]]=1;/*(4)*/
            k = k + 1;
        }else{//没有未被访问过的邻接顶点，回退到上一个顶点
            printf("回溯 顶点=%d,x[k]=%d,visited[x[k]]=%d\n", k, x[k], visited[x[k]]);
            x[k] = 0;
            visited[x[k]] = 0;
            k=k-1;/*(5)*/
        }
    }
    printf("x: ");
    for(k=0;k<n;k++){
        printf("%d,", x[k]);
    }
    printf("visited: ");
    for(k=0;k<n;k++){
        printf("%d,", visited[k]);
    }
}

int main () {
    //算法-无向图连通图-哈密尔顿Hamilton回路
    //从无向连通图的某个顶点出发，经过图上所有其他顶点一次且仅一次，最后回到该顶点的路径
    printf("算法-无向图连通图-哈密尔顿Hamilton回路!     - c.jsrun.net.\n");
    int n = 4;
    int t[4][4] = {{0,1,0,1},{1,-1,1,0},{0,1,0,1},{1,0,1,0}};
    int d[] = {0,1,2,3};
    hamilton(n, d, t);
    return 0;
}