planeyang最小生成树文档格式.docx
《planeyang最小生成树文档格式.docx》由会员分享，可在线阅读，更多相关《planeyang最小生成树文档格式.docx（15页珍藏版）》请在冰点文库上搜索。
性质3.1：
将一条边加入这棵树，就会形成唯一的环。
这是一个很显然的性质，但是他是下面两条重要性质的基础。
PointOne：
Cutproperty（割的性质）
割是什么：
割将整个图的顶点分割成不相交两个部分，其中的边（CrossingEdge）连接两个不同部分的顶点。
割的另一种定义：
ThecutinducedbyasubsetofnodesSisthesetofallarcswithexactlyoneendpointinS.（割由一个点的子集S决定，是一些弧的集合，并且这些弧只有一个端点在S中。
）
Cutproperty：
给出图中的任意一个割，其中的每一个最小边（MinimumCrossingEdge）属于图的某些MST，并且每一个MST包含了其中的一条最小边。
Proof：
反证法。
我们假设e是最小边不属于任意最小生成树，而T是任意最小生成树不包含e，考虑将e加入T，我们会得到一个环，并且这个环中一定有另一条边f，它的权值大于或等于e，那么将e代替f，这棵树的权值将不变或者减小，如果减小，就和T是最小生成树矛盾，如果不变，那么e属于一棵最小生成树，和假设同样矛盾。
性质得证。
#
这意味着MST中的每一条边都是割中的最小边，这些割是由两个子树的顶点决定的。
（割最优条件）
PointTwo：
Cycleproperty（环的性质）
环是什么：
一个形如{a,b},{b,d},{d,g}…{z,a}的边集，其中边没有重复。
Cycleproperty：
给出一个图G，将G增加一条边e，形成G'
。
增加e到G的MST中，并且删除形成的环中最大的边，得到的就是G’的MST。
如果e是一条最大边，那么很显然他不是G'
的最小生成树。
因为我们将e删除，形成两个点集，而e不是割中的最小边，不符合上面的性质。
如果t是加入e形成的环中的最大边，那么原来的MST被分为连个部分，且原来的G中，连接着两个部分的边没有比t更小的，那么在G’中，连接着两个部分的最小边就显而易见是e了，同样根据上面的性质，e是G’的MST中的一条边。
这意味着图中每条边，如果他是在与形成的环中的最大者，则他一定不属于MST。
（环最优条件）
等下登台演出的算法便是根据以上两条性质所实现的，这些算法同样也仰仗着下面这条性质：
最小生成树具有最优子结构——最小生成树的每个部分也是对应子图的最小生成树。
（可以用剪切法证明，有兴趣可以看算法导论讲解Lecture16）。
附：
PointThreeCycle-Cutintersection：
一个环于一个割相交，一定是偶数条边
最后不加证明地给出如下显然的性质。
Prim，Kruskal和Boruvka算法都能计算任何连通图的MST。
[B1]
3.2第一位演员的表演——Prim（1957）（特别提醒：
写程序的时候不要和Dijkstra混了）
貌似我们学习数据结构，最早接触到的便是Prim算法，这个算法的本质是利用最优子结构原理来进行贪心而得到最后解。
标准的Prim算法是求稠密的MST的最好办法。
基本想法（BasicIdea）：
我们维持图的一个割，这个割将图的顶点分成了两个部分，一部分是已经本选到MST中的（设为S），另一部分是还没有选到MST中的。
1、将一个顶点放到S中
2、找到割中的最小边（他一定是MST的一条边）
循环V-1次即把MST找到了。
这便是最初开始时叙述的MST的形成过程。
在实现过程中，我们利用顶点索引数组储存到每个顶点最短的距离。
1、从中找出最小值，设他的端点为u，
2、利用u更新所以没有进入S的顶点的最短距离。
如是再三。
在初始的时候，我们选择一个顶点（V0），利用它来初始所有顶点的最短距离，实际是一个初始割。
而后不断地更新，实际上是维护割的过程。
（是不是这样？
这里有这么个性质：
用Prim算法，我们可以在线形时间内找到稠密图的MST。
（对于稠密图来说，V2便是线形时间了。
数据结构：
程序中是利用数组a是整个图的矩阵储存。
B数组记录每个顶点是否已经进入集合S中。
同时，顶点数组indext记录每个顶点关联的最短边。
Father[i]数组记录的是与i顶点共边的另一个顶点。
procedureprim;
var
b:
array[1..maxn]ofboolean;
v0,f,m,max:
longint;
i,j:
begin
fillchar（b,sizeof（b）,true）;
v0:
=1;
fori:
=1tondo//初始化
begin
ifa[v0,i]=0thenindex[i]:
=maxlongint
elseindex[i]:
=a[v0,i];
father[i]:
=v0;
end;
b[v0]:
=false;
forj:
=1ton-1do
m:
=0;
max:
=maxlongint;
=1tondo//找到最小边
if（index[i]<
max）and（b[i]）then
=i;
=index[i];
ifm=0thenbreak;
b[m]:
push（father[m],m）;
//将最小边加入到MST中
=1tondo//更新所有没有进入MST的点
ifb[i]and（index[i]>
a[m,i]）then
index[i]:
=a[m,i];
=m;
end；
从程序可以很直接的看出，时间复杂度是O（V2）。
对于稀疏图会怎么样么？
我们发现在标准的Prim算法中，很占用时间的部分是找到最小边这个部分，我们很快想到了用堆优化这个部分：
我们每次从堆中直接找出最优值，然后用当前的这个点更新其他的点（这些点要是与之相连接的），并且维护这个堆。
直到这个堆为空。
这样，我们从开始的一个数组变成了需要两个数组：
数组a用来记录每个顶点在堆中的位置，数组Heap便是这个堆了。
这样操作起来比标准的算法要麻烦（要维护一个堆，还有将这个堆和原来的算法联系起来）。
这种算法的时间复杂度是O（ElgV）的。
Proof：
W-C下，所有的边可能都会导致顶点堆得调整，而每一次调整最坏情况时lgV的。
所以总的时间最差是O（ElgV）。
数据结构
B数组作用同上，整个图利用邻接表储存。
Heap表示整个堆。
varp,q:
nice;
i,v0,v:
V0:
pre（v0）;
//利用V0初始化
makeheap;
//建堆
b[heap[1].v]:
delmin（v）;
//删除堆中最小值，并且进入MST
change（v）;
//利用删除的那个边的顶点，更新其他没有进入MST的顶点
end;
3.3第二位演出者——Kruskal（1956）
明显的前面一位是利用割最优条件设计出来的算法，这一位便是利用环最优条件设计出来的算法。
由于我们知道一个环的最长边一定不再MST中，那么我们就想到不要选择这条边——我们按照顺序从小的开始选起，发现组成环了，那么最后的那条边就一定是这个环的最大边了，我们就不要。
基本思想（BasicIdea）
1、将所有的边长度进行排序，
2、逐一选择每条边。
2.1>
对于每条边的两个顶点，设置他们属于两个集合S1，S2，如果这两个集合不相交，那么可以说明他们这条边的加入不会构成换。
选择这条边，并且将两个集合合并。
2.2>
如果S1和S2是同一个集合，那么可以说明，将这条边加入就会形成一个环，而这条边一定是环中最大的边，当然不能够加入MST，跳过。
上图便是利用Kruskal算法构造开始所叙述的那个图的MST。
程序暂略
我们观察程序发现，这个算法的时间复杂度为O（ElgE+E）。
瓶颈在于将所有的边进行排序需要的时间ElgE，而后面的E是说得W-C下，我们可能需要扫描所有的E才能把MST构造成功（MST的某一条边可能很大很大，但是有满足环最优条件）。
我们也可以换个角度来实现Kruskal算法。
1、我们将所有的边初始成一个小根堆。
2、每一次我们直接删除小根堆的根，并且维护这个小根堆。
3、当然，每一次基本操作都还是询问连个顶点所属的集合是不是不相交……
[B1]Property：
这种方法的时间复杂度时O（E+xlgE），其中x是由MST中的最长边所决定的。
X是图中所有不大于MST最长边的边数和。
这个操作的花费集中于以下几点。
1、建堆的时间O（E）
2、X次删除操作。
3、X次插入操作。
4、V-1并查操作。
注意：
这种方法只在X不大于E/lgE的时候优秀。
（如果X<
=E/lgE，那么这个算法是线性的。
明显优秀于普通Kruskal。
）#
最后值得一说的，我们的合并操作显然利用并查集很比较快！
3.4演出者之——Boruvka（1926）
这位演出者一定是最老资格的了，他的原始想法在1926年被提出，当然在后来在1961被Sollin重新提出且有所更新。
后来还被作为了并行算法的基础。
同时，在1995年左右，Karger,Klein,Tarjan提出了一种期望值为O（|E|+|V|）的随机算法，我们稍后会介绍这位小朋友。
这个算法是Kruskal和Prim的混合版本。
在其中你会看到他们的影子。
基本想法：
1、我们用顶点数组记录每个子树（一开始是单个顶点）的最近邻居。
——类似Prim
2、对于每一条边进行处理。
——类似Kruskal
如果这条边连接的两个顶点属于同一个集合，忽略
否则，检查这条边连接的两个子树，如果是割中的最小边，则更新。
上图便是Boruvka的实现过程。
这个过程实际上可以看作缩点。
从实现的角度来说，这种算法是最容易实现的（虽然看上去很难理解）。
1、生成的森林是否有v-1条边，如果是，则说明已经生成MST，否则转2
2、询问所有的边，将所有的子树相关联的最短边（割中的最小边）找出来，将其边的序号连接子树的根上。
3、将所有子树连接上他们的最小边。
转1。
我们可以分析一下这种算法的时间复杂度。
对于每一次查找，都是O（E）的，因为要把所有的边扫描一遍。
第二，循环的次数：
每一次循环我们都至少把两个子树合并为一棵子树，因子每次Div2——因此我们只需要lgV次循环。
Property：
Boruvka算法的时间复杂度是O（ElgV）。
最后值得一提的时候，这种算法是适用于稀疏图的。
（可以根据时间复杂度看出来）
3.5同台演出之一决高下。
算法
W-C时间复杂度
注释
Prim（标准）
V2
稠密图最优算法
Prim（堆）
ElgV
保守上界
Prim（d-叉堆）
ElogdV
稍稍优化
Kruskal
ElgE
排序时间决定
Kruskal（堆）
E+XlgE
有MST中最大决定
Boruvka
刚才三位已经把本领都显出来了，所以我们现在需要比较一下它们的优劣。
以上述表格为基础，我们进行一些分析。
首先，我们可以肯定的是，在稠密图的情况下，Prim标准算法是最优秀的，不需要找其他算法了，因为他已经达到了稠密图的线性时间。
同时我们发现，不同算法的应用是根据图的稠密程度来说的：
1、对于密度较低的时候，选择Kruskal是比较优秀。
2、对于密度中等的时候，选择Prim+堆是比较优秀的。
3、对于密度较高的时候，选择Prim是优秀的。
在表格中我们发现了这样一个项目：
Prim（d-叉堆）。
像普通的堆一样，我们将堆的儿子推广到3个或者4个，普通堆节点i的儿子为2i和2i+1。
我们可以推广到3叉堆，节点i的儿子是3i-1，3i和3i+1。
推广到4叉堆……从理论上来说我们发现在某些时候比用普通堆优秀，但是由于操作起来复杂，而且优化程度不高，并不被广泛应用。
当然，还有著名的Fibonacci堆优化时间到O（E+VlgV），这是一个非常复杂的实现过程，以理论研究为主。
在注释和前面的讲述我们知道Kruskal的时间瓶颈是排序这一步导致的。
通过所学的知识，我们发现在范围允许的情况下，我们可以考虑用基数排序（RadixSort）。
这样一来可以把排序的时间复杂度降到O（E）。
当然，MST还有很多很奇妙的性质，也很多很奇妙的算法。
但是其中真正值得各位实现的，具有使用价值的可能就是上面几种了，其中以Prim和Kruskal算法最为有用，以至于绝大多数教材都只涉及这两种算法。
下面的表格简单的枚举了一些关于MST的算法，仅供大家娱乐。
MST算法的发展
确定算法
●O（mlogn）Jarní
k,Prim,Dijkstra,Kruskal,Boruvka
●O（mloglogn）.Cheriton-Tarjan（1976）,Yao（1975）
●O（mβ（m,n））.Fredman-Tarjan（1987）
●O（mlogβ（m,n））.Gabow-Galil-Spencer-Tarjan（1986）
●O（mα（m,n））.Chazelle（2000）
随机算法
●O（m）randomized.Karger-Klein-Tarjan（1995）
●O（m）verification.Dixon-Rauch-Tarjan（1992）
3.6新的算法——随机算法[P1]
如上表格所说，下面将要介绍的随机算法将期望在O（|V|+|E|）的时间内找到MST。
这个算法是以Boruvka算法为基础的。
参考书籍及资料
[B1]AlgorithmsinCPart5:
GraphAlgorithms（ThirdEdition）
[America]RobertSedgewick
[B2]算法导论英文版
[P1]普林斯顿大学KevinWayne所写的PPT。
（RedRule&
BlueRule）
升级会员 