首页 > 笔记 > 最小生成树笔记

最小生成树笔记

无聊了再坑一坑图论吧。。。啥都搞不好。。。

给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树。。。

有两种著名的算法。。。prim,kruskal。。。

prim的效率取决于优先队列的实现与图的存储方式,这里记顶点数v,边数e 邻接矩阵:O(v2)、邻接表:O(elog2v),若用斐波那契堆作为优先队列则效率为O(e+vlog2v)

kruskal的效率取决于并查集的实现,若用按秩合并与路径压缩效率为O(elog2e)

00:00/00:00

1、prim算法

1.算法简介

普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点(英语:Vertex (graph theory)),且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克(英语:Vojtěch Jarník)发现;并在1957年由美国计算机科学家罗伯特·普里姆(英语:Robert C. Prim)独立发现;1959年,艾兹格·迪科斯彻再次发现了该算法。因此,在某些场合,普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆-亚尔尼克算法。(来自度娘)

2.算法过程:

(1 将一个图的顶点分为两部分,一部分是最小生成树中的结点(U集合),另一部分是未处理的结点(V集合)。

(2 首先选择一个结点,将这个结点加入U中,作为树根。

(3 对集合U中的顶点所连的边遍历,找出边权值最小的那个,将此边所连顶点从V中删除,加入集合U中。

(4 递归重复步骤3,直到V集合中的结点为空,结束此过程。

(5 U集合中的结点就是由Prime算法得到的最小生成树的结点,依照步骤3的结点连接这些顶点,得到的就是这个图的最小生成树。

3.图像演示

images

images

images

images

4、动态图演示

5.简单证明prim算法

反证法:假设prim生成的不是最小生成树

1).设prim生成的树为G0

2).假设存在Gmin使得cost(Gmin)<cost(G0)   则在Gmin中存在<u,v>不属于G0

3).将<u,v>加入G0中可得一个环,且<u,v>不是该环的最长边(这是因为<u,v>∈Gmin)

4).这与prim每次生成最短边矛盾

5).故假设不成立,命题得证.

6、代码实现

伪代码

其工作流程为:

(1)首先进行初始化操作,将所有顶点入优先队列,队列的优先级为权值越小优先级越高

(2)取队列顶端的点u,找到所有与它相邻且不在树中的顶点v,如果w(u, v) < key[v],说明这条边比之前的更优,加入到树中,即更改父节点和key值。这中间还隐含着更新Q的操作(降key值)

(3)重复2操作,直至队列空为止。

(4)最后我们就得到了两个数组,key[v]表示树中连接v顶点的最小权值边的权值,parent[v]表示v的父结点。

现在呢,我们发现一个问题,这里要用到优先队列来实现这个算法,而且每次搜索邻接表都要进行队列更新的操作。

不管用什么方法,总共用时为O(VT(EXTRACTION)+ET(DECREASE))

(1)如果用数组来实现,总时间复杂度为O(V2)

(2)如果用二叉堆来实现,总时间复杂度为O(ElogV)

(3)如果使用斐波那契堆,总时间复杂度为O(E+VlogV)

 

邻接表实现

邻接矩阵

2、kruskal

1.简介

Kruskal算法是一种用来寻找最小生成树的算法,由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪婪算法的应用。和Boruvka算法不同的地方是,Kruskal算法在图中存在相同权值的边时也有效。

2.过程

1.首先将G的n个顶点看成n个孤立的连通分支(n个孤立点)并将所有的边按权从小大排序。

2.按照边权值递增顺序,如果加入边后存在圈则这条边不加,直到形成连通图(到n-1条边)

3.证明

对图的顶点数n做归纳,证明Kruskal算法对任意n阶图适用。

归纳基础:

n=1,显然能够找到最小生成树。

归纳过程:

假设Kruskal算法对n≤k阶图适用,那么,在k+1阶图G中,我们把最短边的两个端点a和b做一个合并操作,即把u与v合为一个点v’,把原来接在u和v的边都接到v’上去,这样就能够得到一个k阶图G'(u,v的合并是k+1少一条边),G’最小生成树T’可以用Kruskal算法得到。

我们证明T’+{<u,v>}是G的最小生成树。

用反证法,如果T’+{<u,v>}不是最小生成树,最小生成树是T,即W(T)<W(T’+{<u,v>})。显然T应该包含<u,v>,否则,可以用<u,v>加入到T中,形成一个环,删除环上原有的任意一条边,形成一棵更小权值的生成树。而T-{<u,v>},是G’的生成树。所以W(T-{<u,v>})<=W(T’),也就是W(T)<=W(T’)+W(<u,v>)=W(T’+{<u,v>}),产生了矛盾。于是假设不成立,T’+{<u,v>}是G的最小生成树,Kruskal算法对k+1阶图也适用。

由数学归纳法,Kruskal算法得证。

4.图像演示

图例描述:

首先第一步,我们有一张图Graph,有若干点和边

将所有的边的长度排序,用排序的结果作为我们选择边的依据。这里再次体现了贪心算法的思想。资源排序,对局部最优的资源进行选择,排序完成后,我们率先选择了边AD。这样我们的图就变成了右图

在剩下的变中寻找。我们找到了CE。这里边的权重也是5

依次类推我们找到了6,7,7,即DF,AB,BE。

下面继续选择, BC或者EF尽管现在长度为8的边是最小的未选择的边。但是现在他们已经连通了(对于BC可以通过CE,EB来连接,类似的EF可以通过EB,BA,AD,DF来接连)。所以不需要选择他们。类似的BD也已经连通了(这里上图的连通线用红色表示了)。

最后就剩下EG和FG了。当然我们选择了EG。最后成功的图就上图
5.动态图
算法
5.代码实现
伪代码

c++

时间复杂度

分析以上代码中Kruskal算法的时间复杂度,n用V表示,m用E表示:

29行:将V个点父节点都置为-1,时间为O(V)

30行:stl中的sort函数,头文件为#include <algorithm>,时间复杂度为O(E log E)

32-40行:由于FIND-SET是树搜索操作,平均时间复杂度为O(lg V),因为这几行时间复杂度平均为O(E log V)

综上:总复杂度表示为:O(V) + O(E log E) + O(E log V);

当图为稠密图时,时间复杂度可表示为 O(E log E);

一般图基本为稀疏图|E| < |V|^2,时间复杂度可表示为 O(E log V)。

因而,从时间复杂度来看,当图为稀疏图时,Kruskal算法性能和Prim相当,当为稠密图时,Prim性能更好。

小技巧(网上看的)

注意每合并两棵树,树的棵树就减少1,当根节点的个数只有一个即只有一棵树时,说明生成了最小生成树,此时程序便可终止,没有必要去查看后面权值更大的边,因而判断根节点的数目,在图较为稠密时,能够提高一定的性能,代码修改如下,图为完全图:

终于写完了= =,累成狗。。。


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×