问题描述：哈密顿图是一个无向图，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。从一张普通图的任意一点出发，路途中经过图中每一个结点当且仅当一次，则成为哈密顿回路。
哈密顿回路条件约束：
1.加入路径的节点与前一个加入路径的顶点一定是连通的；
2.加入路径的最后一个顶点和第一个顶点一定是连通的；
3.路径上不能出现重复的顶点。
问题要求：随机生成无向图，且图中部分顶点间无通路，设计算法找到一条哈密顿回路，实现可视化展示
问题的解决方案
用回溯法求解哈密顿回路，首先把n元组的每一个分量初始化为0，然后深度优先搜索解空间树，如果满足约束条件，则继续进行搜索，否则，将引起搜索过程的回溯。回溯法从根节点出发，按照深度优先策略遍历解空间树，搜索满足约束条件的解。在搜索至树种任一结点时，先判断该结点该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，也急速判断该结点是否包含问题的最优解，如果肯定不包含，则跳过对以该结点为根的子树的搜索；否则进入以该结点为根的子树，继续按照深度优先策略搜索。采用dfs，并且适当减枝。下面我们采用这种方法求解。
C语言代码
可乐炸了:
//哈密顿回路问题
#include
#include
#include
int x[100];
static int visit[100];
int arc[10][10];
int n;
void dfs(int step)
{
int i,j;
if(step==n&&arc[x[step-1]][0]==1) //最后一步到达的顶点与起点之间存在路径
{
printf("路径:");
for(i=0;i
printf("n");
return ;
}
else
{
for(j=0;j
if(visit[j]==0&&arc[x[step-1]][j]==1) //j未访问并且当前顶点与j顶点之间存在路径
{
visit[j]=1;
x[step]=j; //下一个访问的顶点为j
dfs(step+1);
visit[j]=0;
x[step]=0;
}
}
}
}
int main(void)
{
int i,j;
scanf("%d",&n);
for(i=0;i
for(j=0;j
if(i==j){
arc[i][j]=0;
}
else{
arc[i][j]=rand()%2;
arc[j][i]=arc[i][j];
}
}
}
printf("地图数据如下：n");
for(i=0;i
printf("%d ",arc[i][j]);
}
printf("n");
}
visit[0]=1; //起点置为已经访问
x[0]=0;
dfs(1);
return 0;
}
