13.cpp

用Prim算法求最小生成树

#include <stdio.h>
#include <malloc.h>
#define infinite 9999
#define maxn 100
int cost[maxn][maxn];
int n,v;
void prim(){
	int lowcost[maxn],min;
	int closest[maxn],i,j,k;
	for(i=1;i<=n;i++){
		lowcost[i]=cost[v][i];closest[i]=v;
	}
	for(i=1;i<n;i++){
		min=infinite;
		for(j=1;j<=n;j++)
			if((lowcost[j]!=0)&&(lowcost[j]<min)){
				min=lowcost[j];
				k=j;
			}
			printf("边为：(%3d,%3d),权为：%5d\n",closest[k],k,min);
			lowcost[k]=0;
			for(j=1;j<=n;j++)
				if((cost[k][j]!=0)&&(cost[k][j]<lowcost[j])){
					lowcost[j]=cost[k][j];
					closest[j]=k;
				}
	}
}

void main(){
	int i,j,p;
	printf("请输入顶点个数：");
	scanf("%d",&n);
	for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
cost[i][j]=infinite;
for (i=1;i<=n;i++)
cost[i][i]=0;
for(i=1;i<=n;i++){
for(j=i+1;j<=n;j++)
{ printf("请输入%d到%d的权值(输入0为无穷大):",i,j);
  scanf("%d",&p);
  if(p!=0)
  cost[i][j]=cost[j][i]=p;
  else
  cost[i][j]=cost[j][i]=infinite;
}
}
printf("请输入起始节点位置:");
scanf("%d",&v);
prim();
}