planeyang最小生成树文档格式.docx

1、 性质3.1：将一条边加入这棵树，就会形成唯一的环。 这是一个很显然的性质，但是他是下面两条重要性质的基础。 Point One：Cut property（割的性质） 割是什么：割将整个图的顶点分割成不相交两个部分，其中的边（Crossing Edge）连接两个不同部分的顶点。割的另一种定义：The cut induced by a subset of nodes S is the set of all arcs with exactly one endpoint in S.（割由一个点的子集S决定，是一些弧的集合，并且这些弧只有一个端点在S中。）Cut property：给出图中的任意一个割

2、，其中的每一个最小边（Minimum Crossing Edge）属于图的某些MST，并且每一个MST包含了其中的一条最小边。 Proof：反证法。 我们假设e是最小边不属于任意最小生成树，而T是任意最小生成树不包含e，考虑将e加入T，我们会得到一个环，并且这个环中一定有另一条边f，它的权值大于或等于e，那么将e代替f，这棵树的权值将不变或者减小，如果减小，就和T是最小生成树矛盾，如果不变，那么e属于一棵最小生成树，和假设同样矛盾。性质得证。# 这意味着MST中的每一条边都是割中的最小边，这些割是由两个子树的顶点决定的。（割最优条件）Point Two：Cycle property（环的性质）

3、 环是什么：一个形如a,b,b,d,d,gz,a的边集，其中边没有重复。 Cycle property：给出一个图G，将G增加一条边e，形成G。增加e到G的MST中，并且删除形成的环中最大的边，得到的就是G的MST。如果e是一条最大边，那么很显然他不是G的最小生成树。因为我们将e删除，形成两个点集，而e不是割中的最小边，不符合上面的性质。如果t是加入e形成的环中的最大边，那么原来的MST被分为连个部分，且原来的G中，连接着两个部分的边没有比t更小的，那么在G中，连接着两个部分的最小边就显而易见是e了，同样根据上面的性质，e是G的MST中的一条边。这意味着图中每条边，如果他是在与形成的环中的最大

4、者，则他一定不属于MST。（环最优条件）等下登台演出的算法便是根据以上两条性质所实现的，这些算法同样也仰仗着下面这条性质：最小生成树具有最优子结构最小生成树的每个部分也是对应子图的最小生成树。（可以用剪切法证明，有兴趣可以看算法导论讲解Lecture 16）。附：Point Three Cycle-Cut intersection：一个环于一个割相交，一定是偶数条边最后不加证明地给出如下显然的性质。Prim，Kruskal和Boruvka算法都能计算任何连通图的MST。B13.2 第一位演员的表演Prim（1957）（特别提醒：写程序的时候不要和Dijkstra混了）貌似我们学习数据结构，最早

5、接触到的便是Prim算法，这个算法的本质是利用最优子结构原理来进行贪心而得到最后解。标准的Prim算法是求稠密的MST的最好办法。基本想法（Basic Idea）：我们维持图的一个割，这个割将图的顶点分成了两个部分，一部分是已经本选到MST中的（设为S），另一部分是还没有选到MST中的。1、 将一个顶点放到S中2、 找到割中的最小边（他一定是MST的一条边）循环V-1次即把MST找到了。这便是最初开始时叙述的MST的形成过程。在实现过程中，我们利用顶点索引数组储存到每个顶点最短的距离。1、 从中找出最小值，设他的端点为u，2、 利用u更新所以没有进入S的顶点的最短距离。如是再三。在初始的时候，

6、我们选择一个顶点（V0），利用它来初始所有顶点的最短距离，实际是一个初始割。而后不断地更新，实际上是维护割的过程。（是不是这样？这里有这么个性质：用Prim算法，我们可以在线形时间内找到稠密图的MST。（对于稠密图来说，V2便是线形时间了。数据结构：程序中是利用数组a是整个图的矩阵储存。B数组记录每个顶点是否已经进入集合S中。同时，顶点数组indext记录每个顶点关联的最短边。Fatheri数组记录的是与i顶点共边的另一个顶点。procedure prim;var b:array1.maxnof boolean; v0,f,m,max:longint; i,j:begin fillchar（b

7、,sizeof（b）,true）; v0:=1; for i:=1 to n do /初始化 begin if av0,i=0 then indexi:=maxlongint else indexi:=av0,i; fatheri:=v0; end; bv0:=false; for j:=1 to n-1 do m:=0; max:=maxlongint;=1 to n do /找到最小边 if （indexiam,i） then indexi:=am,i;=m;end；从程序可以很直接的看出，时间复杂度是O（V2）。对于稀疏图会怎么样么？我们发现在标准的Prim算法中，很占用时间的部分是找到

8、最小边这个部分，我们很快想到了用堆优化这个部分：我们每次从堆中直接找出最优值，然后用当前的这个点更新其他的点（这些点要是与之相连接的），并且维护这个堆。直到这个堆为空。这样，我们从开始的一个数组变成了需要两个数组：数组a用来记录每个顶点在堆中的位置，数组Heap便是这个堆了。这样操作起来比标准的算法要麻烦（要维护一个堆，还有将这个堆和原来的算法联系起来）。这种算法的时间复杂度是O（ElgV）的。Proof：W-C下，所有的边可能都会导致顶点堆得调整，而每一次调整最坏情况时lgV的。所以总的时间最差是O（ElgV）。数据结构B数组作用同上，整个图利用邻接表储存。Heap表示整个堆。var p,q

9、:nice; i,v0,v: V0:pre（v0）; /利用V0初始化makeheap; /建堆 bheap1.v: delmin（v）; /删除堆中最小值，并且进入MST change（v）; /利用删除的那个边的顶点，更新其他没有进入MST的顶点end;3.3 第二位演出者Kruskal（1956）明显的前面一位是利用割最优条件设计出来的算法，这一位便是利用环最优条件设计出来的算法。由于我们知道一个环的最长边一定不再MST中，那么我们就想到不要选择这条边我们按照顺序从小的开始选起，发现组成环了，那么最后的那条边就一定是这个环的最大边了，我们就不要。基本思想（Basic Idea）1、 将所

10、有的边长度进行排序，2、 逐一选择每条边。2.1对于每条边的两个顶点，设置他们属于两个集合S1，S2，如果这两个集合不相交，那么可以说明他们这条边的加入不会构成换。选择这条边，并且将两个集合合并。2.2如果S1和S2是同一个集合，那么可以说明，将这条边加入就会形成一个环，而这条边一定是环中最大的边，当然不能够加入MST，跳过。上图便是利用Kruskal算法构造开始所叙述的那个图的MST。程序暂略我们观察程序发现，这个算法的时间复杂度为O（ElgE+E）。瓶颈在于将所有的边进行排序需要的时间ElgE，而后面的E是说得W-C下，我们可能需要扫描所有的E才能把MST构造成功（MST的某一条边可能很大

11、很大，但是有满足环最优条件）。我们也可以换个角度来实现Kruskal算法。1、 我们将所有的边初始成一个小根堆。2、 每一次我们直接删除小根堆的根，并且维护这个小根堆。3、 当然，每一次基本操作都还是询问连个顶点所属的集合是不是不相交B1Property：这种方法的时间复杂度时O（E+xlgE），其中x是由MST中的最长边所决定的。X是图中所有不大于MST最长边的边数和。这个操作的花费集中于以下几点。1、 建堆的时间O（E）2、 X次删除操作。3、 X次插入操作。4、 V-1并查操作。注意：这种方法只在X不大于E/lgE的时候优秀。（如果X=E/lgE，那么这个算法是线性的。明显优秀于普通Kr

12、uskal。）# 最后值得一说的，我们的合并操作显然利用并查集很比较快！3.4 演出者之Boruvka（1926）这位演出者一定是最老资格的了，他的原始想法在1926年被提出，当然在后来在1961被Sollin重新提出且有所更新。后来还被作为了并行算法的基础。同时，在1995年左右，Karger, Klein, Tarjan提出了一种期望值为O（|E|+|V|）的随机算法，我们稍后会介绍这位小朋友。这个算法是Kruskal和Prim的混合版本。在其中你会看到他们的影子。基本想法：1、我们用顶点数组记录每个子树（一开始是单个顶点）的最近邻居。类似Prim2、对于每一条边进行处理。类似Kruska

13、l如果这条边连接的两个顶点属于同一个集合，忽略否则，检查这条边连接的两个子树，如果是割中的最小边，则更新。上图便是Boruvka的实现过程。这个过程实际上可以看作缩点。 从实现的角度来说，这种算法是最容易实现的（虽然看上去很难理解）。 1、生成的森林是否有v-1条边，如果是，则说明已经生成MST，否则转2 2、询问所有的边，将所有的子树相关联的最短边（割中的最小边）找出来，将其边的序号连接子树的根上。 3、将所有子树连接上他们的最小边。转1。 我们可以分析一下这种算法的时间复杂度。对于每一次查找，都是O（E）的，因为要把所有的边扫描一遍。第二，循环的次数：每一次循环我们都至少把两个子树合并为一

14、棵子树，因子每次Div 2因此我们只需要lgV次循环。 Property：Boruvka算法的时间复杂度是O（ElgV）。 最后值得一提的时候，这种算法是适用于稀疏图的。（可以根据时间复杂度看出来）3.5 同台演出之一决高下。算法W-C时间复杂度注释Prim（标准）V2稠密图最优算法Prim（堆）ElgV保守上界Prim（d-叉堆）ElogdV稍稍优化KruskalElgE排序时间决定Kruskal（堆）E+XlgE有MST中最大决定Boruvka刚才三位已经把本领都显出来了，所以我们现在需要比较一下它们的优劣。以上述表格为基础，我们进行一些分析。首先，我们可以肯定的是，在稠密图的情况下，Pr

15、im标准算法是最优秀的，不需要找其他算法了，因为他已经达到了稠密图的线性时间。同时我们发现，不同算法的应用是根据图的稠密程度来说的：1、 对于密度较低的时候，选择Kruskal是比较优秀。2、 对于密度中等的时候，选择Prim+堆是比较优秀的。3、 对于密度较高的时候，选择Prim是优秀的。在表格中我们发现了这样一个项目：Prim（d-叉堆）。像普通的堆一样，我们将堆的儿子推广到3个或者4个，普通堆节点i的儿子为2i和2i+1。我们可以推广到3叉堆，节点i的儿子是3i-1，3i和3i+1。推广到4叉堆从理论上来说我们发现在某些时候比用普通堆优秀，但是由于操作起来复杂，而且优化程度不高，并不被广

16、泛应用。当然，还有著名的Fibonacci堆优化时间到O（E+VlgV），这是一个非常复杂的实现过程，以理论研究为主。在注释和前面的讲述我们知道Kruskal的时间瓶颈是排序这一步导致的。通过所学的知识，我们发现在范围允许的情况下，我们可以考虑用基数排序（Radix Sort）。这样一来可以把排序的时间复杂度降到O（E）。当然，MST还有很多很奇妙的性质，也很多很奇妙的算法。但是其中真正值得各位实现的，具有使用价值的可能就是上面几种了，其中以Prim和Kruskal算法最为有用，以至于绝大多数教材都只涉及这两种算法。下面的表格简单的枚举了一些关于MST的算法，仅供大家娱乐。MST算法的发展确定

17、算法 O（m log n） Jarnk, Prim, Dijkstra, Kruskal, Boruvka O（m log log n）. Cheriton-Tarjan （1976）, Yao （1975） O（m （m, n）. Fredman-Tarjan （1987） O（m log （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算法为基础的。参考书籍及资料B1Algorithms in C Part 5: Graph Algorithms （Third Edition） America Robert SedgewickB2算法导论英文版P1普林斯顿大学Kevin Wayne所写的PPT。（Red Rule & Blue Rule）