普里姆(Prim)算法的实现与分析
开篇：润墨网以专业的文秘视角，为您筛选了一篇普里姆(Prim)算法的实现与分析范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：普里姆(prim)算法是实现图的最小生成树的最常用算法。该文主要介绍普里姆(Prim)算法的实现方法，并对普里姆(Prim)算法的效率进行分析。
关键词：普里姆(Prim)算法；算法实现；算法分析
中图分类号：TP18 文献标识码：A文章编号：1009-3044(2011)27-6711-02
The Realization and Analysis ofPrim's Algorithm
HU Zhi-qin
(Ningxia Polytechnic, Ningxia TV University, Yinchuan 750002, China)
Abstract: Prim's Algorithm is used the most frequently in constructing the minimum-cost spanning tree of the graph. The paper aims to introduce the approach to realization of Prim's Algorithm and makes an analysis of its efficiency.
Key words: Prim's Algorithm; realization of algorithm; analysis of algorithm
1 普里姆(Prim)算法的基本思想
从连通网络 N = {V,E}中的某一顶点 u0 出发，选择与它关联的具有最小权值的边(u0,v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。
采用邻接矩阵作为图的存储表示。
算法的基本框架:利用最小堆(MinHeap)和并查集(DisjointSets)来实现普里姆(Prim)算法。
2 最小生成树的构造准则
必须只使用该网络中的边来构造最小生成树；必须使用且仅使用n-1条边来联接网络中的n个顶点；不能使用产生回路的边。
3 用普里姆算法构造最小生成树的实例
如图1所示。
在构造过程中，设置两个辅助数组：
lowcost[ ]：存放生成树顶点集合内顶点到生成树外各顶点的各边上的当前最小权值；
nearvex[ ]：记录生成树顶点集合外各顶点距离集合内哪个顶点最近(即权值最小)。
若选择从顶点0出发，即u0 = 0，则两个辅助数组的初始状态为：
然后反复做以下工作：在 lowcost [ ]中选择nearvex[i]!=-1 && lowcost[i]最小的边i用 v 标记它。则选中的权值最小的边为 (nearvex[v], v)，相应的权值为 lowcost[v]。将nearvex[v] 改为 -1,表示它已加入生成树顶点集合。将边 ( nearvex[v], v, lowcost[v] )加入生成树的边集合。取 lowcost[i] = min{ lowcost[i], Edge[v][i] }，即用生成树顶点集合外各顶点 i 到刚加入该集合的新顶点 v 的距离 Edge[v][i] 与原来它们到生成树顶点集合中顶点的最短距离lowcost[i] 做比较,取距离近的作为这些集合外顶点到生成树顶点集合内顶点的最短距离。如果生成树顶点集合外顶点 i 到刚加入该集合的新顶点 v 的距离比原来它到生成树顶点集合中顶点的最短距离还要近，则修改nearvex[i]：nearvex[i] = v。表示生成树外顶点i到生成树内顶点v当前距离最近。顶点5加入生成树顶点集合：
继续重复得：
最后生成树中边集合里存入得各条边为：
(0, 5, 10), (5, 4, 25), (4, 3, 22),(3, 2, 12), (2, 1, 16), (1, 6, 14)
4 利用普里姆算法建立最小生成树
void Graph ::
Prim ( MinSpanTree &T ) {
int NumVertices = VerticesList.last; //图顶点数
float * lowcost = new float[NumVertices];
int * nearvex = new int[NumVertices];
for ( int i = 1; i < NumVertices; i++ ) {
lowcost[i] = Edge[0][i]; //顶点0到各边的代价及最短带权路径
nearvex[i] = 0;}
nearvex[0] = -1; //顶点0加到生成树顶点集合
MSTEdgeNode e;//最小生成树结点辅助单元
for ( i = 1; i < NumVertices; i++ ) {//循环n-1次, 加入n-1条边
float min = MAXNUM;int v = 0;
for ( int j = 0; j < NumVertices; j++ )
if ( nearvex[j] != -1 && lowcost[j] < min )
{ v = j;min = lowcost[j]; } //求生成树外顶点到生成树内顶点具有最小权值的边, v是当前具最小权值的边的位置
if ( v ) {//v==0表示再也找不到要求顶点了
e.tail = nearvex[v]; e.head = v;
e.cost = lowcost[v];
T.Insert (e);//选出的边加入生成树
nearvex[v] = -1;//作该边已加入生成树标记
for ( j = 1; j < NumVertices; j++ )
if ( nearvex[j] != -1 && Edge[v][j] < lowcost[j] ) { //需要修改
lowcost[j] = Edge[v][j];
nearvex[j] = v;}}}}
5 普里姆算法的时间复杂度分析
设连通网络有n个顶点 ，则该算法的时间复杂度为O(n2), 与图中边数无关，它适用于边稠密的网络。
参考文献：
[1] [美]D.E.克努特.计算机程序设计技巧3[M].管纪文,译.北京:国防工业出版社,1999:185-190.
[2] 许卓群.数据结构[M].北京:高等教育出版社,1993:103-108.
[3] 严蔚敏.数据结构[M].北京:清华大学出版社,2004:207-215.