c7_prim.cpp

这个是严蔚敏版的数据结构上机教程中的部分源代码

/*
Prim
BY:wangyucao
*/ 
  
//无向图                           
//初始时u只包含1个点，后一步步将v中的点添加到u中来。用closest[i]=0表示i点在u集合中
//lowcost[i],当前起点到i点的最小代价


#include<iostream>
#define vex 21//至多20个頂点
#define maxcost 999999//“无穷”权值，及一个足夠大的数
using namespace std;
void Prim(int c[][vex],int n)//c[][vex]
{
	int i,j,k,min,lowcost[vex],closest[vex];

	for(i=2;i<=n;i++)
	{
		lowcost[i]=c[1][i];//第1个点到其他点的代价
		closest[i]=1;//初始时，所有点的起点都是点1 
	}

	for(i=2;i<=n;i++)
	{
		min=maxcost;//maxcost一个很大的数
		for(j=2;j<=n;j++)
			if(closest[j]&&lowcost[j]<min&&lowcost[j]>0)	 {
				min=lowcost[j];//在v中找到最小的代价点
				k=j;
			}
		printf("(%d %d) %d\n",closest[k],k,c[closest[k]][k]);//closest[k]->起点，k->终点
		closest[k]=0;//k点归入u中
		for(j=2;j<=n;j++)
			if(closest[j]&&c[k][j]<lowcost[j]&&c[k][j]>0) {
				lowcost[j]=c[k][j];//以k点为起点进行新一轮的代价计算
				closest[j]=k;
			}
	}
}

int main()
{
	register int i,j;
	int EdgeNum,VexNum,c[vex][vex],start,end,weight;
	
	
	printf("输入顶点数和边数:");
	scanf("%d%d",&VexNum,&EdgeNum);
	for(i=1;i<=VexNum;i++)
		for(j=1;j<=VexNum;j++)
			c[i][j]=maxcost;
	for(i=1;i<=EdgeNum;i++)
	{
	//	printf("Input %d-th start end and weight:",i);
		scanf("%d%d%d",&start,&end,&weight);
		c[start][end]=c[end][start]=weight;
	}
	
/*
	for(i=1;i<=VexNum;i++)
	{
		for(j=1;j<=VexNum;j++)
			printf("%-d\t",c[i][j]);
		printf("\n");
	}
*/
	Prim(c,VexNum);
	system("PAUSE");
	return 0;
}

/*4 4
1 2 7
2 3 10
3 4 11
4 2 9*/