Prim算法（三） Java详解

Prim算法（三） Java详解2014-12-15

普里姆算法介绍

普里姆（Prim）算法，是用来求加权连通图的最小生成树的算法。

基本思想

对于图G而言，V是所有顶点的集合；现在，设置两个新的集合U和T，其中U用于存放G的最小生成树中的顶点，T存放G的最小生成树中的边。从所有uU，v（V-U）（V-U表示出去U的所有顶点）的边中选取权值最小的边（u, v），将顶点v加入集合U中，将边（u, v）加入集合T中，如此不断重复，直到U=V为止，最小生成树构造完毕，这时集合T中包含了最小生成树中的所有边。

普里姆算法图解

以上图G4为例，来对普里姆进行演示（从第一个顶点A开始通过普里姆算法生成最小生成树）。

初始状态：V是所有顶点的集合，即V={A,B,C,D,E,F,G}；U和T都是空！

第1步：将顶点A加入到U中。

此时，U={A}。

第2步：将顶点B加入到U中。

上一步操作之后，U={A}, V-U={B,C,D,E,F,G}；因此，边（A,B）的权值最小。将顶点B添加到U中；此时，U={A,B}。

第3步：将顶点F加入到U中。

上一步操作之后，U={A,B}, V-U={C,D,E,F,G}；因此，边（B,F）的权值最小。将顶点F添加到U中；此时，U={A,B,F}。

第4步：将顶点E加入到U中。

上一步操作之后，U={A,B,F}, V-U={C,D,E,G}；因此，边（F,E）的权值最小。将顶点E添加到U中；此时，U={A,B,F,E}。

第5步：将顶点D加入到U中。

上一步操作之后，U={A,B,F,E}, V-U={C,D,G}；因此，边（E,D）的权值最小。将顶点D添加到U中；此时，U={A,B,F,E,D}。

第6步：将顶点C加入到U中。

上一步操作之后，U={A,B,F,E,D}, V-U={C,G}；因此，边（D,C）的权值最小。将顶点C添加到U中；此时，U={A,B,F,E,D,C}。

第7步：将顶点G加入到U中。

上一步操作之后，U={A,B,F,E,D,C}, V-U={G}；因此，边（F,G）的权值最小。将顶点G添加到U中；此时，U=V。

此时，最小生成树构造完成！它包括的顶点依次是：A B F E D C G。