- 1、本文档共34页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
燕山大学数据结构-最小生成树讨论课PPT-王喆讲解
最小生成树讲解 ;最小生成树;最小生成树的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——如有问题,欢迎指正讨论
文档评论(0)