图的最小生成树之普里姆算法
编辑时间:2017-08-14 赞：5 踩：0
导言：
本文将会讲解普里姆算法的原理，及其C语言的实现。这篇文章其实是与克鲁斯卡尔算法的那篇博客一脉相承的。如果说这篇博客是下篇，那么克鲁斯卡尔算法的那篇博客就可以说是上篇。如果是对克鲁斯卡尔算法了解不深的可以先去看关于克鲁斯卡尔算法的博客，链接在此：http://www.kantblog.com/blog/Algorithm/2
正文：
普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克发现；并在1957年由美国计算机科学家罗伯特·普里姆独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。(摘自维基百科)最小生成树概念
要理解普里姆算法的由来必须要先了解什么是最小生成树。一个连通图的生成树是一个极小的连通子图，它含有图中全部的顶点，但只有足以构成一棵树的n-1条边。所谓的最小成本，就是n个顶点，用n-1条边把一个连通图连接起来，并且使得权值的和最小。综合以上两个概念小，我们可以得出：构造连通网的最小代价生成树，即最小生成树（Minimum Cost Spanning Tree）。
普里姆（Prim）算法基本思想
对于图G而言，V是所有顶点的集合；现在，设置两个新的集合U和T，其中U用于存放G的最小生成树中的顶点，T存放G的最小生成树中的边。 从所有uЄU，vЄ(V-U) (V-U表示除去U的所有顶点)的边中选取权值最小的边(u, v)，将顶点v加入集合U中，将边(u, v)加入集合T中，如此不断重复，直到U=V为止，最小生成树构造完毕，这时集合T中包含了最小生成树中的所有边。
图解普里姆算法：
图①
图①为原始的加权连通图，每条边一侧的数字代表其权值。
图②
图②为选定C为任意起点时，普利姆算法的实现。以C为起点，在所有与C点连通且没被选中的顶点中，E点与C点的边权值最小。因此，E点被选中，同时边CE被标记。
图③
如图③所示，在所有与C、E点连通且没被选中的顶点中，B点与E点的边权值最小。因此，B点被选中，同时边BE被标记。
图④
如图④所示，在所有与B、C、E点连通且没被选中的顶点中，A点与B点的边权值最小。因此，A点被选中，同时边AB被标记。
图⑤
如图⑤所示，在所有与A、B、C、E点连通且没被选中的顶点中，A点与D点的边权值最小。因此，D点被选中，同时边AD被标记。
图⑥
如图⑥所示，在所有与A、B、C、D、E点连通且没被选中的顶点中，D点与F点的边权值最小。因此，F点被选中，同时边DF被标记。
图⑦
如图⑦所示，在整个连通图中唯有G点没被选中，而E点与G点的边权值最小。因此，G点被选中，同时边EG被标记。至此，整个普利姆算法运算结束，图①中所展示的连通图的最小生成树如图⑥所示。
普利姆算法C语言实现
#include <stdio.h>
#define INFINITY 65535
#define VERTEXT_NUMBER 3
//测试用例
// int graph[VERTEXT_NUMBER][VERTEXT_NUMBER] = {
// {0,1,5,INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,INFINITY},
// {1,0,3,7,5,INFINITY,INFINITY,INFINITY,INFINITY},
// {5,3,0,INFINITY,1,7,INFINITY,INFINITY,INFINITY},
// {INFINITY,7,INFINITY,0,2,INFINITY,3,INFINITY,INFINITY},
// {INFINITY,5,1,2,0,3,6,9,INFINITY},
// {INFINITY,INFINITY,7,INFINITY,3,0,INFINITY,5,INFINITY},
// {INFINITY,INFINITY,INFINITY,3,6,INFINITY,0,2,7},
// {INFINITY,INFINITY,INFINITY,INFINITY,9,5,2,0,4},
// {INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,7,4,0}
// };
//测试用例
// int graph[VERTEXT_NUMBER][VERTEXT_NUMBER] = {
// {0,6,1,5,INFINITY,INFINITY},
// {6,0,5,INFINITY,3,INFINITY},
// {1,5,0,5,6,4},
// {5,INFINITY,5,0,INFINITY,2},
// {INFINITY,3,6,INFINITY,0,6},
// {INFINITY,INFINITY,4,2,6,0},
// };
int graph[VERTEXT_NUMBER][VERTEXT_NUMBER] = {
{0,990,692},
{990,0,179},
{692,179,0}
};
int treeNode[VERTEXT_NUMBER];
int edgeCost[VERTEXT_NUMBER];
int visited[VERTEXT_NUMBER];
int nodeCnt;
void Prim(){
int tmpVer,tmpWeight,minEdge;
edgeCost[0] = INFINITY;
visited[0] = 1;
treeNode[0] = 0;
// for( int i=0;i<VERTEXT_NUMBER;i++){
// printf(" %d ",visited[i]);
// }
for(int i = 1;i < VERTEXT_NUMBER; i++ ){
minEdge = INFINITY;
for( int j = 0 ; j < VERTEXT_NUMBER ;j++){//在已有的顶点内寻找，权值最少的边，并且改变的另一个顶点不在已有集合内
if( 1 == visited[j] ){
for( int k =0; k < VERTEXT_NUMBER ; k++){
if( 0 == visited[k] && graph[j][k] < minEdge && graph[j][k] != 0){
tmpVer = k;
tmpWeight = graph[j][k];
minEdge = tmpWeight;
}
}
}
}
treeNode[i] = tmpVer;
visited[tmpVer] = 1;
edgeCost[i] = tmpWeight;
}
}
int main(){
Prim();
for(int i=0;i<VERTEXT_NUMBER;i++){
printf(" %d ",treeNode[i]);
}
printf("\n------------------------\n");
for(int i=0;i<VERTEXT_NUMBER;i++){
printf(" %d ",edgeCost[i]);
}
printf("\n");
return 0;
}
至此，普利姆算法的内容就已经结束了。如果大家想巩固一下普利姆算法的知识，可以做一下POJ的第2485题。
相对于克鲁斯卡尔算法，普利姆算法从原理和实现上都较为简单。从实现原理上，普利姆算法是归并点，而克鲁斯卡尔算法是归并边的。因此，普利姆算法适用于点少的图；而克鲁斯卡尔算法，适用于边少的图。
参考资料：
普利姆算法中文维基：https://zh.wikipedia.org/zh-hans/普林姆算法
普利姆算法的博客：http://www.cnblogs.com/skywang12345/p/3711506.html
普利姆算法C语言实现GitHub地址：
https://github.com/OLPMO/DataStructure_And_Algorithm/blob/master/最小生成树（普里姆算法与克鲁斯卡尔算法）/myprim.c