本文主要是介绍回溯法寻找连通图中是否存在哈密顿回路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
使用了回溯法寻找连通图中是否存在哈密顿回路.
哈密顿回路:除了始末点,其他所有点只经过一次
需要注意的地方:
①由哈密顿回路的定义,既然经过了n个点,除了始末两点都不重合,那么这条回路有n条边,在回到初始点前的那一个点处,已经经过了n-1条边
②起始点start并没有存在数组中,需要手动额外打印
③一定要记得使用memset初始化
④检查所有点是否都遍历完的for循环需要放在遍历图的for循环外面
⑤递归之后记得"恢复现场"
#include<iostream>
#include<cstring>
using namespace std;
const int N=100;
int e[N],ne[N],h[N];
int t[N];
bool st[N];
int n,m,idx;
int start,cnt;
/*
8 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
1 7
2 8
1 3
*/
/*
6 6
1 2
2 3
3 4
4 5
5 6
6 1
*/
void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void solve(int k)
{bool flag=true;for(int i=h[k];i!=-1;i=ne[i]){int j=e[i];if(!st[j]){if(j!=start){st[j]=true;t[cnt++]=j;
// printf("solve(%d),经过点:%d,cnt=%d\n",k,j,cnt);solve(j);st[j]=false;cnt--;}else if(j==start&&cnt==n-1){st[j]=true;t[cnt++]=j;
// printf("solve(%d),回到起点:%d\n",k,j);solve(j);st[j]=false;cnt--;}}}for(int p=1;p<=n;p++)if(!st[p]) flag=false;if(flag){printf("--------此图中存在哈密顿回路--------:\n");printf("%d ",start); //start没有存在t数组里面,需要单独打印 for(int p=0;p<cnt;p++){printf("%d ",t[p]);}printf("\n");}
}
int main()
{memset(h,-1,sizeof h);cin>>n>>m;for(int i=0;i<m;i++){int a,b;scanf("%d%d",&a,&b);add(a,b),add(b,a);}for(int i=1;i<=n;i++){printf("起始点:%d\n",i);start=i;solve(i);}return 0;
}这篇关于回溯法寻找连通图中是否存在哈密顿回路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
