hamilton.cpp

利用回溯法求解hamilton回路的算法

#include <iostream>
using namespace std;
struct info
{
	int next[5];
	int num;
	int itr;
};

int main()
{
	
	info data[8];
	int i,j;
	
	for(i=1;i<=6;i++)
	{
		data[i].next[0]=i-1;
		data[i].next[1]=i+1;
		data[i].num=2;
		data[i].itr=0;
	}
	data[0].next[0]=1;
	data[0].next[1]=2;
	data[0].next[2]=6;
	data[0].next[3]=7;
	data[0].itr=0;
	data[0].num=4;
	
	data[2].next[data[2].num]=0;
	data[2].num++;
	
	data[1].next[data[1].num]=7;
	data[1].num++;
	
	data[7].next[0]=6;
	data[7].next[1]=1;
	data[7].next[2]=0;
	data[7].itr=0;
	data[7].num=3;
	
	data[6].next[data[6].num]=0;
	data[6].num++;
	
	int path[8],index,back;
	
	index=0;
	path[0]=0;
	
	while(index>=0)
	{
		if(data[ path[index] ].itr < data[ path[index] ].num)
		{				
			path[index+1]=data[path[index]].next[data[path[index]].itr];
			data[path[index]].itr++;
			index++;
			back=0;
			for(i=0;i<index;i++)//判断是否有相同节点，是则从新走过
			{
				for(j=i+1;j<=index;j++)
				{
					if(path[i]==path[j])
						back=1;
				}
			}
			if(back==1)
			{
				index--;
				continue;
			}
			data[path[index]].itr=0;//下一个节点从新开始寻找路径
		}
		else
		{
			index--;
			continue;
		}
		
		if(index==7)
		{
			for(i=0;i<data[path[7]].num;i++)
			{
				if(data[path[7]].next[i]==path[0])
				{
					for(i=0;i<8;i++)
						cout<<path[i]+1<<"	";
					cout<<path[0]+1<<endl;
				}
			}
			index--;
		}
		
	}
	cin>>i;
	return 0;
	
}