哈密顿.cpp

这里面是很多经典算法的源代码

#include<stdio.h>
#define n 20
#define m 21
int visited[m];
int r[m];
int g[m][m]=
	{
		{0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0},
		
		{0, 0,1,0,0,0, 0,0,0,0,0, 0,0,0,1,0, 0,0,0,0,1},
		{0, 1,0,1,0,0, 1,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0},
		{0, 0,1,0,1,0, 0,0,0,0,0, 0,0,1,0,0, 0,0,0,0,0},
		{0, 0,0,1,0,1, 0,0,0,0,0, 1,0,0,0,0, 0,0,0,0,0},
		{0, 0,0,0,1,0, 1,0,0,1,0, 0,0,0,0,0, 0,0,0,0,0},
		
		{0, 0,1,0,0,1, 0,1,0,0,0, 0,0,0,0,0, 0,0,0,0,0},
		{0, 0,0,0,0,0, 1,0,1,0,0, 0,0,0,0,0, 0,0,0,0,1},
		{0, 0,0,0,0,0, 0,1,0,1,0, 0,0,0,0,0, 0,0,1,0,0},
		{0, 0,0,0,0,1, 0,0,1,0,1, 0,0,0,0,0, 0,0,0,0,0},
		{0, 0,0,0,0,0, 0,0,0,1,0, 1,0,0,0,0, 0,1,0,0,0},
		
		{0, 0,0,0,1,0, 0,0,0,0,1, 0,1,0,0,0, 0,0,0,0,0},
		{0, 0,0,0,0,0, 0,0,0,0,0, 1,0,1,0,0, 1,0,0,0,0},
		{0, 0,0,1,0,0, 0,0,0,0,0, 0,1,0,1,0, 0,0,0,0,0},
		{0, 1,0,0,0,0, 0,0,0,0,0, 0,0,1,0,1, 0,0,0,0,0},
		{0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,1,0, 1,0,0,1,0},

		{0, 0,0,0,0,0, 0,0,0,0,0, 0,1,0,0,1, 0,1,0,0,0},
		{0, 0,0,0,0,0, 0,0,0,0,1, 0,0,0,0,0, 1,0,1,0,0},
		{0, 0,0,0,0,0, 0,0,1,0,0, 0,0,0,0,0, 0,1,0,1,0},
		{0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,1, 0,0,1,0,1},
		{0, 1,0,0,0,0, 0,1,0,0,0, 0,0,0,0,0, 0,0,0,1,0}
	};
main()
{
	void search(int ,int );
	search(1,1);
	
}
int check(int i,int j)
{
	if(g[i][j]&&!visited[j])
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
void out()
{
	int i;
	for(i=1;i<=n;i++)
	{
		printf("%d ",r[i]);
	}
}
void search(int i,int j)//走的第i 个城市的序号是j
{
	int k;
	visited[j]=1;
	r[i]=j;
	if(i==n)
	{
		if(g[r[1]][r[n]])
		{
			printf("\n");
			out();
		}
	}
	else
	{
		for(k=1;k<=n;k++)
		{
			if(check(j,k))
			{
				search(i+1,k);
			}
		}
	}
	visited[j]=0;
}