燕山大学数据结构-最小生成树讨论课PPT-王喆讲解.pptx

最小生成树讲解 ;最小生成树;最小生成树的MST性质及证明;最小生成树算法; ;普里姆算法思想 ;简单证明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).故假设不成立，命题得证.;普里姆算法过程演示1 ;9;普里姆最小生成树算法与dijkstra最短路径算法;;程序截图：;运行结果：; ;克鲁斯卡尔算法思想 ;简单证明Kruskal算法 对图的顶点数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算法得证。;克鲁斯卡尔算法过程1 ;18;程序截图：;运行结果：;关于并查集;为了解释并查集的原理，我举一个有爱的例子。 ;路径压缩：所有节点指向根节点;最小生成树小结;小结1 最小生成树算法时间复杂度分析;小结2 最小生成树应用;补充1 其他算法;程序截图：;2、破圈法 其实也是一种贪心算法，只不过prim和krustal算法是“加”边，而这个顾名思义，就是减边。 1.找到图中的一个圈。2.删除其中的权最大的边。3.重复上述操作，直到图中已无圈。 针对无向图，可以这样做： 1.用拓扑分类算法，找到图中的圈。具体就是依次找到图中度为1的顶点（可以保存在队列里），删除之（这里的删除是暂时的，下次遍历还要还原这些点），然后与其邻接的顶点的入度-1，这样往复操作，直到图中已不存在入度为1的顶点，即所有的顶点的度都》=2，那么剩下的边就都在环里了。当然，如果没剩下边，说明没有环，算法结束。 2.剩下的边就都是环中的边了，找一个权最大的删去即可。 3.再进行1操作，直到图中无圈，即所有的圈都已破掉，当剩下的边=结点数-1的时候，剩下的就是最小生成树了。;30;3、补图算法 补图算法首先寻找最小生成树的补图 ,然后再求出该补图的补图即得最小生成树.（ 根据最小生成树的定义易知 ）在寻找最小生成树的补图的过程中 ,遵循以下 2 条原则:原则一 , 度为 1 的结点的关联边肯定不在补图中 ,删去不管;原则二 ,环上的最大权边一定在补图中 ,保留在补图中;循环利用上述原则 ,即可得到最小生成树的补图。 ;补充2：斐波那契堆;;Thank you——如有问题，欢迎指正讨论