prim.txt

来自「图的操作」· 文本 代码 · 共 64 行

# include <stdio.h>
# define inf 1000
# define max  50
prim(int g[][max],int n)
{
	int lowcost[max],closest[max];
	int i,j,k,min;
	for(i=2;i<=n;i++)
	{
		lowcost[i]=g[1][i];
		closest[i]=1;
	}
	lowcost[1]=0;
	for(i=2;i<=n;i++)
	{
		min=inf;
		k=0;
		for(j=2;j<=n;j++)
			if((lowcost[j]<min)&&(lowcost[j]!=0))
			{
				min=lowcost[j];
				k=j;
			}
		printf("(%d,  %d),    %d\t",closest[k],k,min );
		lowcost[k]=0;
		for(j=2;j<=n;j++)
			if(g[k][j]<lowcost[j])
		{
				lowcost[j]=g[k][j];
				closest[j]=k;
		}
		printf("\n");
	}
}


int adjg(int g[][max])
{
	int n,i,j,v1,v2,wei;
	printf("all point=");
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++ )
			g[i][j]=inf;
	printf("point point quan\n");


	do
	{
		scanf("%d   %d   %d",&v1,&v2,&wei);
		g[v1][v2]=wei;
		g[v2][v1]=wei;
	}while(v1!=0 && v2!=0 && wei!=0);
	return(n);
}


main()
{ 
	int g[max][max],n;
	n=adjg(g);
	printf("small tree:\n");
	prim(g,n);
}