普利姆算法（prim）求最小生成树（MST)过程详解

生活中最小生成树的应用十分广泛，比如：要连通n个城市需要n－1条边线路，那么怎么样建设才能使工程造价最小呢？可以把线路的造价看成权值求这几个城市的连通图的最小生成树。求最小造价的过程也就转化成求最小生成树的过程，则最小生成树表示使其造价最小的生成树。 那么怎么样用普利姆算法(prim算法)求最小生成树（MST）？ 此以图例方式详述prim算法求最小生成树过程，希望对大家有帮助！

2、最小生成树的性质： MST性质：假设G＝(V,E)是一个连通网，U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u∈U，v∈V－U，则必存在一棵包含边(u,v)的最小生成树。 构造网的最小生成树必须解决下面两个问题： （1）尽可能选取权值小的边，但不能构成回路； （2）选取n－1条恰当的边以连通n个顶点；

三、普利姆求最小生成树算法过程图解

1、第一步：随意选取起点 图中有9个顶点v1-v9，集合表示为：V={v1，....，V9}，每条边的边权值都在图上；在进行prim算法时，我们先随意选择一个顶点作为起始点（起始点的选取不会影响最小生成树结果），在此我们一般选择v1作为起始点，现在我们设U集合为当前所找到最小生成树里面的顶点，TE集合为所找到的边。 状态如下：U={v1}；TE={}；

3、第三步：继续寻找最小权值 查找一个顶点在U={v1，v8}集合中，另一个顶点在V-U集合中的最小权值，如下图，在红线相交的线上找最小值。 通过图中我们可以看到边v8-v9的权值最小为4，那么将v9加入到U集合，（v8，v9）加入到TE。 状态如下：U={v1，v8，v9}；TE={（v1，v8），（v8，v9）}；

5、第五步：继续在前一步的基础上，寻找最小权值 查找一个顶点在U={v1，v8，v9，v2娅势毁歹}集合中，另一个顶点在V-U集合中的最小权值，如下图，在红线相交的缏堋垌胯线上找最小值。 通过图中我们可以看到边v2-v3的权值最小为3，那么将v3加入到U集合，（v2，v3）加入到TE。 状态如下：U={v1，v8，v9，v2，v3}； TE={（v1，v8），（v8，v9），（v9，v2），（v2，v3）}；

四、小结

1、（1）最小生成树（MST）是指权值最小的生成树。（2）prim算法是求最小生成树的算法之一，其他算法还有kruskal算法（3）其时间复杂度为O(n^2)，与边得数目无关。prim算法适合稠密图。