算法思想：设连通网N＝（V，｛E｝）中，T＝（U，TE）是存放MST的集合，其中TE是N的最小生成树的边的集合，U是N的最小生成树顶点的集合，V－U是图N中除去U中顶点的顶点集合。具体步骤如下：

①算法开始时，TE为空，U中存在一个初始顶点。

②考查图中满足以下条件的边：边的一端在U集合中的顶点中，另一端在V－U集合的顶点中，在这些边中寻找权值最小的一条，假设为（vi，vj），其中，vi∈U，vj∈V－U，那么将顶点vj加入集合U中，将边（vi，vj）加入集合TE中。

③重复执行步骤②共n－1次，T即为所求。

普里姆算法可描述如下。

算法7.6 普里姆算法

普利姆算法：由于算法中有两个for循环嵌套，时间复杂度为O（n2）；与边的个数无关；适合于求边稠密的网的最小生成树。

利用该算法，对图7－25（a）所示的连通网从顶点v1开始构造最小生成树，算法中各参量的变化如图7－25（b）～（f）所示。

图7－25 普里姆算法构造最小生成树的过程