首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 其他教程 > 其他相关 >

贪口算法 - 最小生成树 Prim算法

2012-09-05 
贪心算法 - 最小生成树 Prim算法一个无向带权图G(V,E),其中n个顶点Vertex,以及连接各个顶点之间的边Edge,

贪心算法 - 最小生成树 Prim算法

一个无向带权图G=(V,E),其中n个顶点Vertex,以及连接各个顶点之间的边Edge,可能有些顶点之间没有边,每条边上的权值都是非负值。

生成树:

G的一个子图,包含了所有的Vertex,和部分的Edge。

最小生成树:

所有的生成树中,各条Edge上的权值总和最小的一个。

例子:设计通信网络时,各个城市之间铺设线路,最经济的方案。

最小生成树性质:

G=(V,E),

S是V的真子集,

如果u在S中,v在V-S中,且(u,v)是图的一条边,称之为特殊边,且(u,v)是所有特殊边中最短的,

那么,(u,v)这条边一定在最小生成树中。


Prim算法:

任意指定一个顶点作为起始点,放在S中。

每一步将最短的特殊边放入S中,需要n-1步,即可把所有的其他的点放入S中。算法结束。

贪口算法 - 最小生成树 Prim算法

对于这个图,Prim算法的过程为:

贪口算法 - 最小生成树 Prim算法


代码实现如下:

1 3 1 3 6 1 3 4 6 1 2 3 4 6 1 2 3 4 5 6 

可由prev数组构造出最小生成树。

算法复杂度为O(n^2)

热点排行