我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:一品彩票 > 反馈边集合 >

最小生成树(普利姆算法、克鲁斯卡尔算法)

归档日期:05-11       文本归类:反馈边集合      文章编辑:爱尚语录

  给定一个带权的无向连通图,怎样选取一棵生成树,使树上全部边上权的总和为最小,这叫

  图的存贮结构採用边集数组,且权相等的边在数组中排列次序能够是随意的.该方法对于边相对照较多的不是非常有用,浪费时间.

  图的存贮结构採用邻接矩阵.此方法是按各个顶点连通的步骤进行,须要用一个顶点集合,開始为空集,以后将以连通的顶点陆续添?到集合中,所有顶点添?集合后就得到所需的最小生成树 .

  方法:将图中边按其权由小到大的次序顺序选取,若选边后不形成回路,则保留作为一条边,若形成回路则除去.依次选够(n-1)条边,即得最小生成树.(n为顶点数)

  方法:从指定顶点開始将它添?集合中,然后将集合内的顶点与集合外的顶点所构成的所有边中选取权最小的一条边作为生成树的边,并将集合外的那个顶点添?到集合中,表示该顶点已连通.再用集合内的顶点与集合外的顶点构成的边中找最小的边,并将对应的顶点添?集合中,如此下去直到所有顶点都添?到集合中,即得最小生成树.

  例在下图中从1点出发求出此图的最小生成树,并按生成树的边的顺序将顶点与权填入表中.

  第一步:从①開始,①进集合,用与集合外全部顶点能构成的边中找最小权的一条边

本文链接:http://explodingspec.com/fankuibianjihe/185.html

上一篇:网络拓扑发现的算法研究与实现_图文

下一篇:没有了