燕山大学数据结构-最小生成树讨论课王喆共_第1页
燕山大学数据结构-最小生成树讨论课王喆共_第2页
燕山大学数据结构-最小生成树讨论课王喆共_第3页
燕山大学数据结构-最小生成树讨论课王喆共_第4页
燕山大学数据结构-最小生成树讨论课王喆共_第5页
已阅读5页，还剩29页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

最小生成树讲解wOwz-pd.com最小生成树引入:为一个镇的9个村光纤铺设做设计最小生成树MSTMinimumSpannirngTree)树任意两个顶点间有且只有一条通路生成树包括全部顶点且连通最小权值和最小最小生成树的MST性质及证明构造最小生成树有多种算法,其中多数算法用到了最小生成树的下列种性质:假设N=(V,{E})是一个连通网,U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值(代价)的边,其中u∈U,v∈V-U,则必存在一棵包含边(u,v)的最小生成树。证明:对于两个点集,有最小的权值的边(u,v),如果该图的最小生成树不包括这条边的话,那么这棵树就不是最小生成树。我们假设任何一棵最小代价生成树都不包含(u,v),由于树都是连通图,因而必定存在其他的边联通了顶点集U和VU,并且这样的边必须只有一条,否则便会形成回路,因为顶点集U和VU里面各个顶点也都是连通的。那么如果我们现在把轻边(u,v)加入这个树中,那么便形成回路了,那这个时候我们把原来的联通U和VU的边去掉,这样形成的树是比原来的那棵最小生成树的代价还要小的,因为边(u,v)是连接两个点集之间的权值最小的边。所以这棵新的树才是最小生成树,但是它包含了边(u,v),所以与假设矛盾,结论成立。第一章最小生成树算法第1普娜算法让小大普里姆算法思想从连通网N={V,B中的某一顶点U出发,选择与它关联的具有最小权值的边(U,v),将其顶点加入到生成树的顶点集合U中。2、以后每一步从一个顶点在U中,而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合U中。3、如此继续下去,直到网中的所有顶点都加入到生成树顶点集合U中为止。简单证明prim算法反证法:假设prim生成的不是最小生成树1).设prim生成的树为G02).假设存在Gmin使得cost(Gmin)<cost(G0)则在Gmin中存在<u,v>不属于G0·3).将<u,>加入G0中可得一个环,且<u,v>不是该环的最长边(这是因为<u,v>∈Gmin)4).这与prim每次生成最短边矛盾●5).故假设不成立,命题得证普里姆算法过程演示110+20+12+8+16+19+7+16=最小生成树权值Prim算法实例起点{v2,v3,vlowcost5v}4,y5,v6}3advelowcost056y)2.,5,v6}6adivexIvl,V3lowcost1v2v3v4y5v6w(v2,v4y5}4v0615∞∞aaivex3Iv1,v3.v6053lowcost150564adver50IVI,V3,Vv5}5∞36∞0606,v4,v24260djivIv3.v6,v4,v2,v}9普里姆最小生成树算法与dijkstra最短路径算法相同:l:同一种贪心策略,从VU中选最小权值点加入U中不同1:应用prim所有连通和最小dijkstraA到其他最

人人文库> 全部分类> 办公材料 > 办公文档

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论