prim.h

数据结构课程设计：“构造可以使n个城市连接的最小生成树”算法的实现！非常不错！

//普里姆函数设计

/*通过函数得到的最小生成树的结点数据和相应结点的边的权值数据closeVertex*/
//数据类型定义


typedef struct
{
	VerT vertex;
	int weight;
}MinSpanTree;


void Prim(AdjMGraph G,MinSpanTree closeVertex[])
{
	VerT x;
	int n=G.Vertices.size, minCost;
	int *lowCost=(int*)malloc(sizeof(int)*n);
	int i,j,k;

	for(i=1;i<n;i++)
		lowCost[i]=G.edge[0][i];


	ListGet(G.Vertices,0,&x);
	closeVertex[0].vertex=x;
	lowCost[0]=-1;

	for(i=1;i<n;i++)
	{
		minCost=MaxWeight;
		for(j=1;j<n;j++)
		{
			if(lowCost[j] < minCost && lowCost[j] >0)
			{
				minCost=lowCost[j];
				k=j;
			}
		}


		ListGet(G.Vertices,k,&x);
		closeVertex[i].vertex=x;
        closeVertex[i].weight=minCost;
		lowCost[k]=-1;

		for(j=1;j<n;j++)
		{
			if(G.edge[k][j]<lowCost[j])
				lowCost[j]=G.edge[k][j];
		}
	}
}