贪心算法 - 最小生成树 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算法的过程为:

代码实现如下:
1 3 1 3 6 1 3 4 6 1 2 3 4 6 1 2 3 4 5 6
算法复杂度为O(n^2)