摘要：
本文首先最小生成树三种算法简单描述，再介绍Prim算法描述、算法正确性证明并给出例子，最后用C语言实现该算法，并给出测试结果。
一、最小生成树算法
现实中不少问题可以抽象成最小生成树模型，比如道路铺设，使得任何两个地方可达，并且使得总费用最省。最小生成树算法主要有：
(1) Kruskal(克鲁斯克尔)算法
从G中的最小边开始，进行避圈式扩张。从符合扩展边(新加入的边不会构成回路)选择权值最小的边进行扩展。
(2) 管梅谷的破圈法
不断破圈(从赋权图G的任意圈开始，去掉该圈中权值最大的一条边，称为破圈)，直到G中没有圈为止，最后剩下的G的子图为G的最小生成树。
(3) Prim算法
对于连通赋权图G的任意一个顶点u，选择与点u关联的且权值最小的边作为最小生成树的第一条边e1。在接下来的边e2,e3,…,en-1 ,在与一条已经选取的边只有一个公共端点的的所有边中，选取权值最小的边。
二、Prim算法
(1) 算法描述
Prim算法利用贪心法思想，算法描述如下：
在图G=(V, E) （V表示顶点 ，E表示边）中，从集合V中任取一个顶点（例如取顶点v0）放入集合 U中，这时 U={v0}，集合T(E)为空。
从v0出发寻找与U中顶点相邻（另一顶点在V中）权值最小的边的另一顶点v1，并使v1加入U。即U={v0,v1 }，同时将该边加入集合T(E)中。
重复(2)，直到U = V为止。
这时T(E)中有n-1条边，T = (U, T(E))就是一棵最小生成树。
(2) 算法正确性证明
即证明用该算法得到的生成树是最小的。如下：
设prim生成的树为G0，假设存在Gmin使得cost(Gmin)
(3) 例子
三、代码实现
注释比较清楚，源代码如下：
- /************************************
-
* 算法描述
-
*图用邻接矩阵存储adjMatrix[][]
-
*lowcost[i]表示当前生成树，到各顶点i的最小权值
-
* 当该点加入生成树，标记值为-1
-
*startVertex[i]与lowcost[i]对应的最小权值边的起点
-
*
-
*filename:prim_main.c
-
*by Jelline
-
* *********************************/
-
-
-
#include <stdio.h>
-
-
#define MAX_WEIGHT 0x7FFFFFFF
-
-
//const int MAX_WEIGHT = 0x7FFFFFFF;
-
//const int MAX_WEIGHT = 500;
-
-
int prim(int n, int adjMatrix[][n], const char vertex[]);
-
-
int main()
-
{
-
const char vertex[] = {'a','b', 'c', 'd', 'e', 'f', 'g', 'h','i'};
-
const int n = sizeof(vertex)/sizeof(char); //the number of vertices
-
-
int adjMatrix[9][9] = {
-
{MAX_WEIGHT, 4, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 8, MAX_WEIGHT},
-
{4, MAX_WEIGHT, 8, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 11, MAX_WEIGHT},
-
{MAX_WEIGHT, 8, MAX_WEIGHT, 7, MAX_WEIGHT, 4, MAX_WEIGHT, MAX_WEIGHT, 2},
-
{MAX_WEIGHT, MAX_WEIGHT, 7, MAX_WEIGHT, 9, 14, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT},
-
{MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 9, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT},
-
{MAX_WEIGHT, MAX_WEIGHT, 4, 14, MAX_WEIGHT, MAX_WEIGHT, 2, MAX_WEIGHT, MAX_WEIGHT},
-
{MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 2, MAX_WEIGHT, 1, 6},
-
{8, 11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 1, MAX_WEIGHT, 7},
-
{MAX_WEIGHT, MAX_WEIGHT, 2, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 6, 7, MAX_WEIGHT}
-
};
-
-
/*
-
int adjMatrix[9][9] = {
-
{0, 4, 0, 0, 0, 0, 0, 8, 0},
-
{4, 0, 8, 0, 0, 0, 0, 11, 0},
-
{0, 8, 0, 7, 0, 4, 0, 0, 2},
-
{0, 0, 7, 0, 9, 14, 0, 0, 0},
-
{0, 0, 0, 9, 10, 0, 0, 0, 0},
-
{0, 0, 4, 14, 10, 0, 2, 0, 0},
-
{0, 0, 0, 0, 0, 2, 0, 1, 6},
-
{8, 11, 0, 0, 0, 0, 1, 0, 7},
-
{0, 0, 2, 0, 0, 0, 6, 7, 0}
-
};
-
*/
-
-
//prim(adjMatrix[][n]);
-
int sumWeight = prim(n, adjMatrix, vertex);
-
printf("the min sum of weight is %d\n", sumWeight);
-
-
return 0;
-
}
-
-
-
int prim(int n, int adjMatrix[][n], const char vertex[])
-
{
-
int sumWeight = 0;
-
//lowcost[i]表示当前生成树，到各顶点i的最小权值 当该点加入生成树，标记值为-1
-
int lowcost[n];
-
int startVertex[n]; //startVertex[i]与lowcost[i]对应的最小权值边的起点
-
int minWeight; //最小权值
-
int minID; //对应minWeight的顶点
-
-
//默认选择第一个顶点加入边集合，第一次初始化lowcost
-
int i;
-
int j;
-
-
startVertex[0] = -1; //第一个顶点加入生成树
-
-
for (i=1; i<n; i++) //以顶点0出发的所有边权值
-
{
-
startVertex[i] = 0;
-
lowcost[i] = adjMatrix[0][i];
-
}
-
-
for (i=1; i<n; i++) //生成树需要n-1个顶点
-
{
-
minWeight = MAX_WEIGHT; //初始化
-
minID = 0;
-
-
for (j=1; j<n; j++) //寻找权值最小的顶点
-
{
-
if(lowcost[j]<minWeight && lowcost[j]!=-1) //边权值最小且不在生成树中
-
{
-
minWeight = lowcost[j];
-
minID = j;
-
}
-
}
-
-
sumWeight += minWeight; //update the sumWeight
-
lowcost[minID] = -1; //标记顶点j已加入生成树
-
-
//print the edge
-
printf("%c----%c: %d\n", vertex[(startVertex[minID])], vertex[minID], minWeight);
-
-
-
//更新当前结点minID到其他节点权值 而原lowcost[]已保存了之前顶点的最小权值
-
//即求未加入生成树的顶点到已加入顶点的最小权值
-
for (j=1; j<n; j++)
-
{
-
if (adjMatrix[minID][j] < lowcost[j])
-
{
-
lowcost[j] = adjMatrix[minID][j];
-
startVertex[j] = minID; //更新最小权值边的起点
-
}
-
}
-
}
-
-
return sumWeight;
-
}
四、测试结果
用上述的例子进行测试，结果如下：
- a----b: 4
-
b----c: 8
-
c----i: 2
-
c----f: 4
-
f----g: 2
-
g----h: 1
-
c----d: 7
-
d----e: 9
-
the min sum of weight is 37
参考资料：
[1] 维基百科词条
阅读(3280) | 评论(0) | 转发(2) |
