multiple_tree.c

用于计算带度约束的最小生成树

#include <stdio.h>

#define INFO	99999
#define	MAXN	100

typedef struct edge
{
	int		head;
	int		trail;
	float	weight;
	int		flag;
}edge;

int			a[MAXN],b[MAXN];
edge	side[10],side_link[10];
int		K,K_max,K_min,KK[6];
int		n;
int		m;
double	L_min = INFO;

void comb_back(int m,int r)
{
	int i,j;
	int	k;
	int		p;
	double  L;
	i = 0;
	a[i] = 1;
	do
	{
		if(a[i] - i <= m-r+1)		//还可以向前试探
		{
			if(i==r-1)			//已找到一个组合
			{
			//	for(j=0;j<r;j++)
			//		printf("%4d",a[j]);
				for(k=0;k<n;k++)
				{
					KK[k] = 0;
				}
			//	printf("\n");

				for(j=0;j<r;j++)
				{
					for(k=0;k<n;k++)
					{
						if(side[a[j]-1].head == k+1 || side[a[j]-1].trail == k+1)
						{
							KK[k]++;
						//	printf("side[%d](%d--%d)\n",a[j],side[a[j]].head,side[a[j]].trail);
						}
					}
				}
				
				K_min = KK[0];
				K_max = KK[0];
				for(k=1;k<n;k++)
				{
					if(KK[k] < K_min)
						K_min = KK[k];
					if(KK[k] > K_max)
						K_max = KK[k];
				}

				if(K_min > 0 && K_max <= K)
				{

					for(j=1;j<r;j++)
						side[a[j]-1].flag = 0;

				//	side_link[0] = side[a[0]-1]; 
					side[a[0]-1].flag = 1;
				
					side_link[0].head = side[a[0]-1].head; 
					side_link[0].trail = side[a[0]-1].trail; 
				//	printf("head=%d,trail=%d\n",side_link[0].head,side_link[0].trail);
				
					for(k=1;k<r;k++)
					{
						side_link[k].head = 0;
						side_link[k].trail = 0;
				//		printf("k=%d: head=%d,trail=%d\n",k,side_link[k].head,side_link[k].trail);
					}
					p = 0;
					for(int js=0;js<r && p < r-1;js++)
					{
						for(j=1;j<r;j++)
						{	
							for(k=0;side_link[k].head != 0 && side[a[j]-1].flag == 0;k++)
							{
								if(	(side[a[j]-1].head == side_link[k].head)
									||(side[a[j]-1].head == side_link[k].trail)
									||(side[a[j]-1].trail == side_link[k].head) 
									||(side[a[j]-1].trail == side_link[k].trail))
								{
									p++;
								//	printf("p=%d\n",p);
									//		printf("side[%d] head=%d,trail=%d\n",a[j],side[a[j]-1].head,side[a[j]-1].trail);	
									side_link[p].head = side[a[j]-1].head;
									side_link[p].trail = side[a[j]-1].trail;
									side[a[j]-1].flag = 1;/*选中标志*/
									break;
									//	printf("head=%d,trail=%d\n",side_link[p].head,side_link[p].trail);
									
								}
							}
						}
					//	printf("p=%d\n",p);						
					}
			//		for(k=0;k<p+2;k++)
			//			printf("side[] head=%d,trail=%d\n",side_link[k].head,side_link[k].trail);

					if(p+1 == r)
					{
						L = 0;
						for(j=0;j<r;j++)
						{
							L += side[a[j]-1].weight;
						//	printf("%4d",a[j]);
						};
						
						if(L_min > L)
						{
							L_min = L;
							for(j=0;j<r;j++)
							{
								b[j] = a[j];
							}
						}
					//	printf("\n p=%d, weight =%4.1f\n",p+1,L);
						
					//	for(k=0;k<n;k++)
					//		printf("%4d",KK[k]);
					//		printf("\n");
					}			
				}

				a[i]++;
				continue;		//相当于goto do处语句
			}
			i++;				//向前试探
			a[i]=a[i-1]+1;
		}
		else					//回溯
		{
			if(i==0)			//已找到了全部解
				return;			//退出循环
			a[--i]++;			//相当于i--;a[i]++;
		}
	}while(1);
}

void main(void)
{
	FILE	*fp;
	int		j;
	n = 6;
	K = 4;
	m = 10;

	fp = fopen("edge.txt","r");
	for(j = 0; j < 3*m; j ++)
	{
		if(j%3 == 0)
			fscanf(fp, "%d", &side[j/3].head);
		if(j%3 == 1)
			fscanf(fp, "%d", &side[j/3].trail);
		if(j%3 == 2)
			fscanf(fp, "%f", &side[j/3].weight);
	//	printf("j%3=%d\n",j/3);
	}
	fclose(fp);

	if(m < n-1)
		printf("Error !!!Not \n");

	comb_back(m,n-1);/******/

	for(j = 0; j < n-1; j ++)
		printf("%4d(%d,%d)", b[j],side[b[j]-1].head,side[b[j]-1].trail);
	printf("\n The small tree's weight is %4.1f\n",L_min);
	
}