prim.h

来自「数据结构c++-书的一些源代码」· C头文件 代码 · 共 46 行

struct MinSpanTree
{
	VerT vertex;
	int weight;
};

void Prim(AdjMWGraph &G, MinSpanTree closeVertex[])
// 用普里姆方法建立网G的最小生成树closeVertex 
{
	int n = G.NumOfVertices(), minCost;
	int *lowCost = new int[n];
	int i, j, k;

	 
	for(i = 0; i < n; i ++)									// 初始化
		lowCost[i] = G.GetWeight(0, i);

	//从序号为0的顶点出发构造最小生成树
	closeVertex[0].vertex = G.GetValue(0);
	lowCost[0] = -1;

	for(i = 1;i < n;i++) 
	{
		// 寻找当前最小权值的边的顶点 
		minCost = MaxWeight;					//MaxWeight为图类种定义的最大权值 
		for(j = 1; j < n; j++)
		{
			if(lowCost[j] < minCost && lowCost[j] > 0)
			{
				minCost = lowCost[j];
				k = j;
			}
		}

		closeVertex[i].vertex = G.GetValue(k);
		closeVertex[i].weight = minCost;
		lowCost[k] = -1;
		//修改其它顶点的边的权值
		for(int j = 1; j < n; j++)
		{ 
			if(G.GetWeight(k, j) < lowCost[j])
				lowCost[j] = G.GetWeight(k, j);
		}
	}
}