hamiton.cpp

Hamilton 回路得算法

#include "stdio.h"
#include "iostream.h"

int n=5;    //五个顶点
int visited[5+1];  //存储顶点的访问标志
int x[5+1];     //存储哈密顿回路上的顶点
int c[5+1][5+1];
void Hamiton();

void main()
{
	//对数组c[][]赋值
	c[1][2] = 1;c[1][4] = 1;
	c[2][1] = 1;c[2][3] = 1;c[2][5] = 1;
	c[3][2] = 1;c[3][4] = 1;c[3][5] = 1;
	c[4][1] = 1;c[4][3] = 1;c[4][5] = 1;
	c[5][2] = 1;c[5][3] = 1;c[5][4] = 1;
	Hamiton();
}

void Hamiton()
{
	int k;
	int m=1;
	int i;
	for(k=1;k<=n;k++)
	{
		visited[k] = 0;
		x[k] = 0;
	}
	k=1;visited[1] = 1;x[1] = 1;   //从顶点1出发
	k++;
	while(k>0)
	{
		x[k]=x[k]+1;      //搜索下一个顶点
		while(x[k]<=n)
			if(visited[x[k]]==0 && c[x[k-1]][x[k]]==1)
				break;
			else
				x[k]=x[k]+1;
		if(x[k]<=n && k==n && c[x[k]][x[1]]==1)
		{
			for(i=1;i<=n;i++)
			{
				cout<<x[i];
			}
			return;
		}
		else
			if(x[k]<=n && k<n)
			{
				visited[x[k]] = 1;
				k=k+1;
			}
			else
			{       //回溯
				
				visited[x[k-1]] = 0;
				x[k] = 0;
				k=k-1;
			}
//		printf("%d\n",m++);
//			printf("%d\n",k);
	}
	printf("No Answer!\n");
	for(i=1;i<=n;i++)
	{
		cout<<x[i];
	}
}