cdp.c

实现并解决经典问题汉密顿回路问题

#include<stdio.h>
#include<time.h>
#include<stdlib.h>


int *E;

#define MAX 50

int Graph[MAX][MAX];

void print_Graph(int n)
{
	int i,j;
	printf("    ");
	for(i = 0;i < n;i++)
	{
		 printf("%3d",i);
	}
	printf("\n");
	for(i = 0;i < n;i++)
	{
		printf("%4d",i);
		for(j = 0;j < n;j++)
		{
			printf("%3d",Graph[i][j]);
		}
		printf("\n");
	}
}


void Creat_Graph(int n)
{
	int i,j, x;
	for(i = 0;i < n;i++	)
	{
		for(j = 0;j <= n;j++ )
		{
			if(i != j)
			{
				x = rand()%99+1;
			    Graph[i][j] = x;
				Graph[j][i] = x;
			}
		}

	}
}


void han(int index,int n,int size)
{
	int i,temp,t;
		
	if(n == 1)
	{
		E[size-1] = n;
	}
	else
	{
	temp = index/n;
	t = index%n;
	
	han(temp,n-1,size);

	for(i = 0;i < size-t-1;i++)
	{
		E[i] = E[i+1];
	}
	E[size-t-1] = n;
	}
}



void main()
{
	//	int Source,Destination;/*qi dian zhong dian */
	//clock_t start,end;
	//start = clock();
	unsigned beg_time ,end_time ;
       
	int i,j,n,q,p,m;
	int total,total_n;
	int *path;
	srand(time(0)); 
	for(i = 0;i < MAX;i++)
	{
		for(j = 0;j < MAX;j++)
			Graph[i][j] = 0;
	}

    printf("please input the number of the vertice in the Graph\n");
	scanf("%d",&n);
	if (n>MAX)
	{
		printf("Out of Range,Please input n again!");
		
	}
	else 
	{
		Creat_Graph(n);	
	}
	printf("##Graph##\n");
	print_Graph(n);
	printf("\n");
	q = n-1;
    p = q; 
	m = 1;
	E = (int *)malloc(q*sizeof(int));
	path = (int *)malloc((n+1)*sizeof(int));
    while(p > 0)
	{
		m *= p; 
		p--;
	}

	total=0;
	total_n = 0;
	for(j = 1;j < n;j++)
	{
		total += Graph[j-1][j];
		path[j] = j;   
	} 
	total+=Graph[j-1][0];
	printf("%d    ",total);
	printf("\n");


	path[0] = 0;
	path[n] = 0; 
	
	beg_time = (unsigned)time(NULL);

	for( i = 0;i < m;i+=2)
	{
		han(i,q,q);
		for(j = 1;j < q;j++)
		{
			total_n += Graph[E[j-1]][E[j]];
			if(total_n>=total)
				break;
		}
		total_n += Graph[E[j-1]][0];
		total_n += Graph[0][E[0]];

		if(total_n >= total)
		{
			total_n = 0;
		}
		else
		{
			total = total_n;
			total_n = 0;
			for(j = 1;j < n;j++)
			{
				path[j] = E[j-1];
			}
		}
	}
	end_time = (unsigned)time(NULL);
	printf("用时：  %d",end_time - beg_time);
	printf("\n");
	printf("%d  ,%d   ",i,total);
	printf("\n");
	for(i = 0;i <= n;i++)
	{
		printf("%d  ",path[j]);
	}
}