prim算法图解_prim算法是一种什么算法

普里姆算法介绍

prim算法图解_prim算法是一种什么算法

普里姆(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中包含了小生成树中的所有边。

普里姆算法图解

以上图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

版权声明:《prim算法图解_prim算法是一种什么算法》文章主要来源于网络,不代表本网站立场,不承担相关法律责任,如涉及版权问题,请发送邮件至[dcseo8@163 。com]举报,我们会在第一时间进行处理。本文文章链接:https://www.dcseo.cn/38952.html
(0)

相关推荐