普里姆(Prim)算法

作者：追风剑情发布于：2014-10-12 15:42 分类：Algorithms

最小生成树算法

开发工具 Visual Studio2010

开发语言 C++

#include <stdlib.h>
#include <stdio.h>

const int MAXVEX = 7;//最大顶点数
const int INF = 429496729;//无路径时的权值

/**
 * 图的最小生成树
 * 普里姆(Prim)算法——适合稠密图
 */
void Prim(int cost[][MAXVEX], int n, int v)
{
	int lowcost[MAXVEX], min;
	int closest[MAXVEX], i, j, k;
	//给lowcost[]和closest[]置初值
	for(i=0; i<n; i++){
		lowcost[i] = cost[v][i];
		closest[i] = v;
	}

	for(i=1; i<n; i++){//找出n-1个顶点
		min = INF;
		//在V-U中找出离U最近的顶点k
		for(j=0; j<n; j++){
			if(lowcost[j] != 0 && lowcost[j] < min){
				min = lowcost[j];
				k = j;
			}
		}
		printf("边(%d, %d)权为：%d\n", closest[k], k, min);
		lowcost[k] = 0;//标记k已经加入U

		//修改数组lowcost和closest
		for(j=0; j<n; j++){
			if(cost[k][j] != 0 && cost[k][j] < lowcost[j]){
				lowcost[j] = cost[k][j];
				closest[j] = k;
			}
		}
	}
}

void main()
{
	//定义一个代价矩阵作为测试数据 INF:无路径
	int cost[MAXVEX][MAXVEX] = {
		{0,   50,  60,  INF, INF, INF,  INF},
		{50,  0,   INF, 65,  40,  INF,  INF},
		{60,  INF, 0,   52,  INF, INF,  45},
		{INF, 65,  52,  0,   50,  30,   42},
		{INF, 40,  INF, 50,  0,   70,   INF},
		{INF, INF, INF, 30,  70,  0,    INF},
		{INF, INF, 45,  42,  INF, INF,  0  }
	};

	printf("最小生成树:\n");
	Prim(cost, MAXVEX, 0);

	system("pause");
}