回溯法寻找连通图中是否存在哈密顿回路

?使用了回溯法寻找连通图中是否存在哈密顿回路.

哈密顿回路:除了始末点,其他所有点只经过一次

需要注意的地方:

①由哈密顿回路的定义,既然经过了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;
}