题解：求解无向图上的哈密尔顿回路

Guderian出品

说明

一个无向连通图$ G $点上的哈密尔顿（Hamiltion）回路是指从图$ G $上的某个顶点出发，经过图上所有其他顶点一次且仅一次，最后回到该顶点的路径。

分析

算法设计策略：回溯法+深度优先搜索+记忆化搜索

假设图$ G $存在一个从顶点$ V_0 $出发的哈密尔顿回路$ V_1-V_2-V_3-…-V_{n-1}-V_0$。算法从顶点$ V_0 $出发，访问该顶点的一个未被访问的邻接顶点$ V_1$，接着从顶点$ V_1 $出发，访问$ V_1 $一个未被访问的邻接顶点$ V_2$，以此类推。对顶点$ V_i$，重复进行以下操作：访问$ V_i $的一个未被访问的邻接接点$ V_{i+1}$；若$ V_i $的所有邻接顶点均已被访问，则返回到顶点$ V_{i-1}$，考虑$V_{i-1} $的下一个未被访问的邻接顶点，仍记为$ V_i$；知道找到一条哈密尔顿回路或者找不到哈密尔顿回路，算法结束。

实现

（1）常量和变量说明

n：图$G$中的顶点数

c[][]：图$G$的邻接矩阵

k：统计变量，当前已经访问的顶点数为k+1

x[k]：第k个访问的顶点编号，从0开始

visited[x[k]]：第k个顶点的访问标志，0表示未访问，1表示已访问

（2）C语言程序

#include<stdio.h> 
#include<stdlib.h> 
#define MAX 4  
Void Hamilton(int n,int x[MAX],int c[MAX][MAX]){
    int i; 
    int visited[MAX]; 
    int k; /*初始化x数组和visited数组*/ 
    for(i=0;i<n;i++){ 
        x[i]=0; 
        Visited[i]=0; 
    } 
    /*访问起初顶点*/ 
    k=0;   
    visited[0]=1;
    x[0]=0; 
    k=k+1; 
    /*访问其它顶点*/ 
    while(k>0){ 
        x[k]=x[k]+1; 
        while(x[k]<n){ 
            if(visited[x[k]]==0 &&c[x[k-1]][x[k]]==1){/*邻接顶点x[k]未被访问过*/ 
                break;
            } 
            else{ 
                x[k]=x[k]+1; 
            } 
        } 
        if(x[k]<n&&k==n-1&&c[x[0]][x[k]]==1){/*找到一条哈密尔顿回路*/ 
            for(k=0;k<n;k++){ 
                printf(“%d--”,x[k]);/*输出哈密尔顿回路*/ 
            } 
            printf(“%d\n”,x[0]); 
            return; 
        } 
        else if(x[k]&&k<n-1){/*设置当前顶点的访问标志，继续下一个顶点*/    
            visited[x[k]]=1  ; 
            k=k+1; 
        } 
        else {/*没有未被访问过的领接顶点，回退到上一个顶点*/ 
            x[k]=0; 
            visited[x[k]]=0;    
            k=k-1 ; 
        } 
    } 
}

（3）复杂度分析

时间复杂度：$O(n^n)$（爆搜）
空间复杂度：$O( n ^2)$