首页 > 代码库 > 哈密尔顿环问题

哈密尔顿环问题

哈密尔顿环
  欧拉回路是指不重复地走过所有路径的回路,而哈密尔顿环是指不重复地走过所有的点,并且最后还能回到起点的回路。
 
 
 1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int num[10001];//求一个点能过到达的边的数量  5 int map[1001][1001]; 6 int jztx[1001]; 7 int vis[1001]; 8 int now=1; 9 int ans[1001];10 int x;11 void print()12 {13     for(int i=1;i<=now-1;i++)14     cout<<ans[i]<<" ";15     cout<<endl;16 }17 void dfs(int last,int i)// last为上一次访问的节点,避免出现圆环首尾相连的情况,,i是当前访问的点 18 {19     jztx[i]=1;20     vis[i]=1;21     ans[now]=i;22     now++;23     for(int j=1;j<=num[i];j++)24     {25         if(map[i][j]==x&&map[i][j]!=last)26         {27             ans[now]=map[i][j];28             now++;29             print();30             now--;31             break;32         }33         if(vis[map[i][j]]==0)34         {35             dfs(i,map[i][j]);36         }37     }38     now--;39     vis[i]=0;40 }41 int main()42 {43     int n,m;44     scanf("%d%d",&n,&m);45     for(int i=1;i<=m;i++)46     {47         int x,y;48         scanf("%d%d",&x,&y);49         map[x][++num[x]]=y;50         map[y][++num[y]]=x;51     }52     for(x=1;x<=n;x++)53     if(jztx[x]==0)54     {55         now=1;56         dfs(0,x);57     }58     return 0;59 }

 

哈密尔顿环问题