哈密顿回路 回溯法.txt

ACM资料大集合

#include <iostream>
#include <iomanip>
#include <stdio.h>
using namespace std;

//哈密顿回路 回溯法
/*
输入：
5 7
1 2
1 4
2 3
2 5
3 5
3 4
4 5

输出:
k=1  0  0 -1 -1 -1
k=2  0  1  0 -1 -1
k=3  0  1  2  0 -1
k=4  0  1  2  3  0
k=3  0  1  2  4 -1
k=4  0  1  2  4  0
k=4  0  1  2  4  3
1
*/
int path[11][11]={0};
int next[11]={-1};
int visited[11]={0};
int save;

void print(int num,int k)
{
	int i;
	cout<<"k="<<k;
	for(i=0;i<num;i++)
		printf("%3d",next[i]);
	cout<<endl;
}

void init()
{
	int i;
	for(i=0;i<11;i++)
		next[i]=-1;//next[i]表示第i次要访问的点，初始化，表示还未开始访问
}
bool HAMIDUN(int num,int start)
{
	int k=1,now=1,s=start;
	init();//初始化
	visited[start]=1;//访问第一个点
	next[start]=start;
	while(k>=1)//从第2个点开始访问
	{
		next[k]++;//开始访问，访问下一个点，设为A处
		print(num,k);
		while(next[k]<num)
		{
			if(visited[next[k]]==0&&path[next[k-1]][next[k]]==1) 
				break;//第k次正在访问的点符合条件
			next[k]++;
		}
		if(next[k]<num)
		{	
			//该点符合条件
			if(k==num-1&&path[next[k]][start]==1)
			{
			//访问到最后一个点，且已形成哈密顿回路
				visited[next[k]]=1;
				print(num,k);
				return true;
			}
			else if(k<num-1) 
			{	//还未访问完，继续下一次访问
				visited[next[k]]=1;//访问该点
				k++;
			}
		}
		else
		{	//该点不符合条件，回溯
			visited[next[k-1]]=0;//上一次访问的点无效（也就是还未访问）
			//注意，此时next[k-1]不是为0，而是为上次访问后停留的位置
			//回溯后从上次停留的位置后面（注意A处）开始访问
			next[k]=-1;	//本次访问未得到合适的点	
			k--;
		}
	}
	return false;
}

int main()
{
	int num,ta,tb,pathnum,i;
	scanf("%d%d",&num,&pathnum);
	for(i=0;i<pathnum;i++)
	{
		scanf("%d%d",&ta,&tb);
		path[ta-1][tb-1]=path[tb-1][ta-1]=1;
	}
	printf("%d",HAMIDUN(num,0));
	return 0;
}















#include <iostream>
#include <iomanip>
#include <stdio.h>
using namespace std;

//哈密顿回路 回溯法
/*
输入：
5 7
1 2
1 4
2 3
2 5
3 5
3 4
4 5

输出:
k=1  0  0 -1 -1 -1
k=2  0  1  0 -1 -1
k=3  0  1  2  0 -1
k=4  0  1  2  3  0
k=3  0  1  2  4 -1
k=4  0  1  2  4  0
k=4  0  1  2  4  3
1
*/
int path[11][11]={0};
int next[11]={-1};
int visited[11]={0};
int save;

void print(int num,int k)
{
	int i;
	cout<<"k="<<k;
	for(i=0;i<num;i++)
		printf("%3d",next[i]);
	cout<<endl;
//	system("pause");
}

void init()
{
	int i;
	for(i=0;i<11;i++)
		next[i]=-1;
}
bool HAMIDUN(int num,int start)
{
	int k=1,now=1,s=start;
	init();
	visited[start]=1;
	next[start]=start;
//	next[0]=1;
	while(k>=1)
	{
		next[k]++;
		print(num,k);
//		save=next[k];
//		visited[next[k]]=0;
		while(next[k]<num)
		{
			if(visited[next[k]]==0&&path[next[k-1]][next[k]]==1) 
			{
				s=next[k];
				break;
			}
			next[k]++;
		}
		if(k==num-1&&path[next[k]][start]==1&&next[k]<num)
		{
			visited[next[k]]=1;
			print(num,k);
//			next[k]=start;
			return true;
		}
		else if(next[k]<num&&k<num-1) 
		{
			visited[next[k]]=1;
			k++;
		}
		else
		{
//			visited[next[k-1]]=0;
//			next[k-1]=0;
//			if(k<num) 
//			{
		
//			if(next[k]>=num) next[k]=save;
//			if(next[k]>=num) visited[save]=0;
//			else 
			visited[next[k-1]]=0;
//			next[k-1]++;
				next[k]=-1;		
//			}
	//		next[k]=0;
	//		visited[next[k]]=0;
			k--;
		}
	}
	return false;
}

int main()
{
	int num,ta,tb,pathnum,i;
	scanf("%d%d",&num,&pathnum);
	for(i=0;i<pathnum;i++)
	{
		scanf("%d%d",&ta,&tb);
		path[ta-1][tb-1]=path[tb-1][ta-1]=1;
	}
	printf("%d",HAMIDUN(num,0));
	return 0;
}