注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

极夜.潜的博客

 
 
 

日志

 
 

Prim算法——最小生成树的贪心算法  

2011-06-09 11:52:48|  分类: Algorithm |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

对图G=(V,E),如果存在边集E的一个子集,从G中删除这些边后,它的连通分图的个数增多,则称该子集为边割集。对一个连通图来说,删除这些边后,连通图变为不连通。含有最少边的边割集称为最小边割集。类似可定义点割集和最小点割集。仅含1个边的边割集称为割边,割边也称为,仅含1个点的点割集称为割点。Prim算法的基本思想:树A从图G的任意结点r开始,在算法的每一步,在连接A到G-A的所有边中,权值最小的边被加入到树中,树逐渐生长直至该树跨越了G中的所有结点。当算法终止时,A为一棵最小生成树。事实上,每步加入的边是图G边割集中权值最小的边,该边割集将图G割为A和G-A(G-A可能是有多颗树的森林)。因为每次都将权值最小的边添加到树中,Prim算法也是贪心算法

Prim算法类似寻找最短路径的Dijkstra算法,不同的是,Prim算法每次加入边的权重最小,Dijkstra算法每次加入的顶点到起点的路径最短。与Kruskal算法不同,Prim算法的特点是集合A中的边总是只形成单棵树。

一、Prim最小生成树算法

算法的输入是连通图G和将生成的最小生成树的根r。在算法执行过程中,不在树中的所有结点都驻留于优先级基于key域的队列Q中。对每个结点v,key[v]是连接v到树中结点的边所具有的最小权值;按常规,若不存在这样的边则key[v]=∞。域p[v]说明树中v的“父母”。有效实现Prim算法的关键是设法较容易地选择一条新的边添加到由A的边所形成的树中。

 MST-PRIM(G,w,r)1. Q←V[G]2. for 每个u?Q3.   do key[u]←∞4. key[r]←05. p[r]←NULL6. while Q≠?7.   do u←EXTRACT-MIN(Q)8.      for 每个v?Adj[u]9.        do if v?Q and w(u,v)<key[v]10.            then p[v]←u11.                 key[v]←w(u,v)

第1步 第1-4行,初始化优先队列Q使其包含所有结点,r的key域被置为0,其余结点的key域为∞。
第2步 第5行,初始化p[r]的值为NULL,这是由于r没有父母。在整个算法中,集合V-Q包含正在生长的树中的结点。
第3步 第7行,识别出与通过割(V-Q,Q)的一条轻边相关联的结点u?Q(第一次迭代例外,根据第4行这时u=r)。从集合Q中去掉u后把它加入到树的结点集合V-Q中。
第4步 第8-11行,对与u邻接且不在树中的每个结点v的key域和p域进行更新,这样的更新保证key[v]=w(v,p[v])且(v,p[v])是连接v到树中某结点的一条轻边。 

二、Prim算法工作流程实例

下图中,阴影覆盖的边属于正在生成的树,树中的结点为黑色。

  Prim算法——最小生成树的贪心算法 - 极夜.潜 - 极夜.潜的博客

(a)

  Prim算法——最小生成树的贪心算法 - 极夜.潜 - 极夜.潜的博客

(b)

  Prim算法——最小生成树的贪心算法 - 极夜.潜 - 极夜.潜的博客

(c)

  Prim算法——最小生成树的贪心算法 - 极夜.潜 - 极夜.潜的博客

(d)

  Prim算法——最小生成树的贪心算法 - 极夜.潜 - 极夜.潜的博客

(e)

  Prim算法——最小生成树的贪心算法 - 极夜.潜 - 极夜.潜的博客

(f)

  Prim算法——最小生成树的贪心算法 - 极夜.潜 - 极夜.潜的博客

(g)

  Prim算法——最小生成树的贪心算法 - 极夜.潜 - 极夜.潜的博客

(h)

  Prim算法——最小生成树的贪心算法 - 极夜.潜 - 极夜.潜的博客

(i)

摘自:http://www.comp.nus.edu.sg/~xujia/mirror/algorithm.myrice.com/algorithm/commonalg/graph/mst/chapter2.htm

 

  评论这张
 
阅读(1594)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018