数据结构精品共享课 最小生成树课件_第1页
数据结构精品共享课 最小生成树课件_第2页
数据结构精品共享课 最小生成树课件_第3页
数据结构精品共享课 最小生成树课件_第4页
数据结构精品共享课 最小生成树课件_第5页
已阅读5页,还剩14页未读 继续免费阅读

下载本文档

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

文档简介

1、1/19最小生成树主讲人: 石冰2013.11.30数据结构精品资源共享课2/19内容提要 最小生成树 最小生成树的性质 普里姆算法 克鲁斯卡尔算法 最小生成树 最小生成树的性质 普里姆算法 克鲁斯卡尔算法3/19内容提要 最小生成树 最小生成树的性质 普里姆算法 克鲁斯卡尔算法 最小生成树 最小生成树的性质 普里姆算法 克鲁斯卡尔算法4/19最小生成树( MST)连通图网图生成树最小生成树:在一个连通网的所有生成树中, 各边的权值之和最小的那棵生成树称为该连通网的最小代价生成树(Minimum Cost Spanning Tree),简称为最小生成树(MST)。 最小生成树 最小生成树的性质

2、 普里姆算法 克鲁斯卡尔算法5/19内容提要 最小生成树 最小生成树的性质 普里姆算法 克鲁斯卡尔算法 最小生成树 最小生成树的性质 普里姆算法 克鲁斯卡尔算法7/19证明(反证法) 最小生成树 最小生成树的性质 普里姆算法 克鲁斯卡尔算法 假设不存在这样一棵包含边(u, v)的最小生成树。 任取一棵最小生成树T,将(u, v)加入T中。根据树的性质,此时T中必形成一个包含(u, v)的回路, 且回路中必有一条边(u, v)的权值大于或等于(u, v)的权值。 删除(u, v),则得到一棵代价小于等于T的生成树T,且T为一棵包含边(u, v)的最小生成树。 这与假设矛盾,故该性质得证。8/19

3、内容提要 最小生成树 最小生成树的性质 普里姆算法 克鲁斯卡尔算法 最小生成树 最小生成树的性质 普里姆算法 克鲁斯卡尔算法10/19Prim算法的辅助数组 最小生成树 最小生成树的性质 普里姆算法 克鲁斯卡尔算法 为了提高算法效率设置一个辅助数组closedge,以记录从U到V-U具有最小代价的边。每个顶点vV-U在辅助数组中存在一个分量closedgev,它包括两个域vex和lowcost,其中lowcost存储该边上的权。 struct int adjvex; int lowcost; closedgeMAX-VERTEX-NUM; closedgev.lowcost=Min(cost(

4、u, v) | uU) 11/19生成树的构造过程 最小生成树 最小生成树的性质 普里姆算法 克鲁斯卡尔算法165432651356642513116314164314211643214251654321425312/19辅助数组的变化 最小生成树 最小生成树的性质 普里姆算法 克鲁斯卡尔算法 iclosedge12345UV-UkAdjvexlowcostv16v11v15v1v2,v3,v4,v5,v62Adjvexlowcostv350v15v36v34v1,v3v2,v4,v5,v65Adjvexlowcostv350v62v360v1,v3,v6v2,v4,v53Adjvexlowc

5、ostv3500v360v1,v3,v6,V4v2,v51Adjvexlowcost000v230v1,v3,v6,v4,v2v54Adjvexlowcost00000v1,v3,v6,v4,v2,v514/19Prim算法描述-2 最小生成树 最小生成树的性质 普里姆算法 克鲁斯卡尔算法 printf( closedgek.adjvex, k); closedgek.lowcost=0; /将顶点k加入U for( i=0; iG.vexnum; i+) /更新closedge if( G.arcski.adj closedgei.lowcost) closedgei.lowcost=G.arcski.adj; closedgei.adjvex=k; /for 15/19内容提要 最小生成树 最小生成树的性质 普里姆算法 克鲁斯卡尔算法 最小生成树 最小生成树的性质 普里姆算法 克鲁斯卡尔算法17/19Kruskal算法执行过程 最小生成树 最小生成树的性质 普里姆算法 克鲁斯卡尔算法12345612345612123456123123456123412345612345123456118/19算法对比 最小生成树 最小生成树的性质 普里姆算法 克鲁斯卡尔算法普里姆算法:生长法克鲁斯卡尔算法:连片法 19/1

温馨提示

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

评论

0/150

提交评论