prim.h

数据结构头文件源代码

struct MinSpanTree
{
	VerT vertex;
	int weight;
};

void Prim(AdjMWGraph&G,MinSpanTree minSTree[]);
//
{
	int n=G.NumOfVertices(),minCost;
	int *lowCost=new int[n];
	int i,j,k;

	for(i=1;i<n;i++)
	{
		lowCost[i]=G.GetWeight(0,1);
	}

	//
	minSTree[0].vertex=G.GetValue(0);
	cout<<""<<G.GetValue(0)<<endl;

	for(i=1;i<n;i++)
	{
		//
		minCost=MaxWeight;   //
		j=1;k=1;
		while(j<n)
		{
			if(lowCost[j]<jminCost&&lowCost[j]!=0)
			{
				minCost=lowCost[j];
				k=j;
			}
			j++;
		}
		cout<<<<G.GetValue(k)<<<<minCost
			cout<<endl;
		lowCost[k]=0;

		//
		for(int j=1;j<n;j++)
		{
			if(G.GetWeight(k,j)<lowCost[j]
			{
				lowCost[j]=G.GetWeight(k,j);
				minSTree[j].vertex=G.GetValue(k);
			}
		}
	}
}