最小生成树

给定一个连接的无向图(undirected graph),一个图的生成树是指所有顶点连接在一起的子图。一个图可能有多个生成树

最小生成树(Minimum Spanning Tree)或者最小权重生成树是指一个有权重的连接的无向图,所有边的权重和小于或者等于所有其他的生成树。

最小生成树有 V-1 条边,V 为顶点数


克鲁斯克尔算法(Kruskal) 

最小生成树算法步骤:

1.安权重从小到大排序

2.选择一条最小边,检测它是否和现有的组成了一个圈,如果是或略,如果不是,包含它

3.重复第2步,知道有 V-1 个边包含进来了

这就是典型的贪心算法,每次都贪心选择权重最小的不会组成环路的边,通过下面展示可以更好的理解

After sorting:
Weight   Src    Dest
1         7      6
2         8      2
2         6      5
4         0      1
4         2      5
6         8      6
7         2      3
7         7      8
8         0      7
8         1      2
9         3      4
10        5      4
11        1      7
14        3      5
1.选择6-7
2.选择2-8
3.选择6-5
4.选择0-1
5.选择2-5
6.由于8-6组成了环路,丢弃
7.选择2-3
8.由于7-8会组成环路,丢弃
9.选择0-7
10.由于1-2会组成环路,丢弃
11.选择3-4

最终如下图

从上面我们可以看出,权重相同的如果换下位置,那么将会得到不同的最小生成树,所以这就是典型的贪心算法,不保证结果肯定是最优的

实例请参考 https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/


普里姆(Prim)算法

算法步骤:

1.以某一个点开始,寻找当前该点可以访问的所有的边

2.在已经寻找的边中发现最小边,这个边必须有一个点还没有访问过,将还没有访问的点加入我们的集合,记录添加的边

3.寻找当前集合可以访问的所有边,重复2的过程,直到没有新的点可以加入

4.此时由所有边构成的树即为最小生成树。

sv代表选择了的点,sb代表选择了的边,lb代表可以选择的边
选择顶点0        sv[0] lb[0-1,0-7]
由于边0-1更短,选择顶点1    sv[0,1] sb[0-1] lb[0-7,1-2,1-7]

此时边0-7和1-2权重都为8,都可以选择,我们这里选择0-7
即选择顶点7    sv[0,1,7]  sb[0-1,0-7]  lb[1-2,7-8,7-6]

边7-6最短,选择顶点6    sv[0,1,7,6]   sb[0-1,0-7,7-6]  lb[1-2,6-8,6-5,7-8]
边6-5最短,选择顶点5    sv[0,1,7,6,5]  sb[0-1,0-7,7-6,6-5]  lb[1-2,6-8,7-8,5-4,5-2,5-3]
边5-2最短,选择顶点2    sv[0,1,7,6,5,2] sb[0-1,0-7,7-6,6-5,5-2]  lb[6-8,7-8,5-3,5-4,2-3,2-8]
边2-8最短,选择顶点8    sv[0,1,7,6,5,2,8] sb[0-1,0-7,7-6,6-5,5-2,2-8]  lb[5-3,5-4,2-3]
边2-3最短,选择顶点3    sv[0,1,7,6,5,2,8,3] sb[0-1,0-7,7-6,6-5,5-2,2-8,2-3]  lb[5-4,3-4]
边3-4最短,选择顶点4    sv[0,1,7,6,5,2,8,3,4] sb[0-1,0-7,7-6,6-5,5-2,2-8,2-3,3-4]

至此全部完成,图片请参照上面

从上面可以看出,在选择边0-7和1-2时我们选择了0-7,所以当我们选择1-2时,又是另外一种解,这就是贪心算法的特点,不保证最后的解为最优解



更多原理参考 https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/



上一篇: 活动选择问题
下一篇: 哈夫曼编码
作者邮箱: 203328517@qq.com