hamiltonian.cpp

给定一个n个结点的连通图

#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);
}