回溯法求解哈密尔顿回路问题

#include<stdio.h> #include<process.h> #include<math.h> //全局变量声明 int m=1; //用于标志哈密尔顿回路的总个数 int n; // int x[128]; int graph[128][128]; void nextvalue(int k) { int j; while(1) { x[k]=(int)fmod(x[k]+1,n+1); if(x[k]==0) return; if(graph[x[k-1]][x[k]]) { for(j=1;j<=k-1;j++) { if(x[j]==x[k]) break; } if(j==k) { if(k<n||(k==n&&graph[x[n]][1])) return; } } } } void print(int x[],int n) { int i=1; printf("回路%d:",m); for(;i<=n;i++) printf("%d ",x[i]); printf("\n"); m++; } void hamiltonian(int k) { while(1) { nextvalue(k); if(x[k]==0) return; if(k==n) print(x,n); else hamiltonian(k+1); } } void main() { int i,j,e,a,b; printf("***********哈密顿回路递归回溯算法***********\n"); printf("********************************************\n"); printf("请先创建一个n结点的连通图graph[n][n]\n"); printf("请输入顶点n的值:"); scanf("%d",&n); printf("图中一共有几条边？请输入以便我们创建图:"); scanf("%d",&e); for(i=1;i<=n;i++) for(j=1;j<=n;j++) graph[i][j]=0; for(i=1;i<=e;i++) { printf("\n创建第%d条边:\n",i); printf("构成此边的一个顶点号(1~%d):",n); scanf("%d",&a); printf("另一个顶点号(1~%d):",n); scanf("%d",&b); graph[a][b]=graph[b][a]=1; } x[1]=1; for(i=2;i<=n;i++) x[i]=0; printf("\n以下为所求hamiltonian回路的所有解\n"); hamiltonian(2); }