第十五讲图3数据结构绍兴文理学院课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《第十五讲图3数据结构绍兴文理学院课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第十五 数据结构 绍兴 文理学院 课件
- 资源描述:
-
1、 连通网络的连通网络的最小代价最小代价问题问题第第6 6章章 图图(3)(3)设设G=(VG=(V,E)E)是一个连通是一个连通网络,网络,U U是顶点集是顶点集V V的一个非空子集。若的一个非空子集。若(u(u,v)v)是一条具有最小权值是一条具有最小权值(代价代价)的边的边,其中,其中uUuU,vV-UvV-U,则必存在一棵包,则必存在一棵包含边含边(u(u,v)v)的最小生成树。的最小生成树。(证明略证明略)图的应用图的应用 通信网问题。图的顶点之间的边上的权值表示相应的代价,对通信网问题。图的顶点之间的边上的权值表示相应的代价,对于于n n个顶点的连通图可以建立许多不同的个顶点的连通图
2、可以建立许多不同的生成树生成树。一棵生成树的代价就是树上各边的一棵生成树的代价就是树上各边的代价之和代价之和。各边各边代价之和代价之和最小的那棵生成树称为该连通网的最小的那棵生成树称为该连通网的最小代价生成最小代价生成树树,简称为,简称为最小生成树最小生成树。2 2、求解最小生成树的基础、求解最小生成树的基础 MST MST性质:性质:uvUVUTKSTKS4 47:42 普里姆普里姆(Prim)(Prim)算法和算法和克鲁斯卡尔克鲁斯卡尔(Kruskal(Kruskal)算法是两个利用算法是两个利用MST MST 性质构造最小生成树的算法。性质构造最小生成树的算法。3 3、普里姆算法、普里姆
3、算法(1)(1)算法思想算法思想 从连通网络从连通网络 N N=V V,E E 中的某中的某一顶点一顶点V(T)=V(T)=u u0 0 出发,选择与它关出发,选择与它关联的具有最小权值的边联的具有最小权值的边(u u0 0,v v),将其,将其 以后每一步从一个顶点在以后每一步从一个顶点在V(T)V(T)中,而另一个顶点不在中,而另一个顶点不在V(T)V(T)中的中的各条边中选择权值最小的边各条边中选择权值最小的边(u u,v v),),把它的顶点把它的顶点v v加入到集合加入到集合V(T)V(T)中中,将其边,将其边(u u,v v)加入到生成树的边集合加入到生成树的边集合E(T)E(T)
4、中。中。如此继续下去,直到网络中的所有顶点都加入到生成树顶点集如此继续下去,直到网络中的所有顶点都加入到生成树顶点集合合V(T)V(T)中为止中为止(直到直到V(T)V(T)满满n n个顶点为止个顶点为止)。顶点顶点v v加入到生成树的顶点集合加入到生成树的顶点集合V(T)V(T)中,中,V(T)V(T)TKSTKS5 57:42(2)(2)算法步骤算法步骤(构造过程构造过程)假设假设N=(VN=(V,E)E)是连通网,是连通网,TETE是是N N上最小生成树中边的集合。上最小生成树中边的集合。U=u0(u0V)U=u0(u0V),TE=TE=。在所有在所有uUuU,vVvV-U-U的边的边(
5、u(u,v)Ev)E中找一条权值最小的边中找一条权值最小的边(u0(u0,v0)v0)并入集合并入集合TETE,同时,同时v0v0并入并入U U。重复重复,直至,直至U=VU=V为止。为止。此时此时TETE中必有中必有n-ln-l条边,则条边,则T=(VT=(V,TE)TE)为为N N的最小生成树。的最小生成树。示例示例1 1:v v1 1v v2 2v v3 3v v4 4v v5 5v v6 63 35 55 52 24 46 61 15 56 66 6 v v5 5 v v1 1 v v2 2 v v3 3 v v4 4 v v6 6 v v1 1v v2 2v v3 3v v4 4v
6、v5 5v v6 610105 56 66 66 610107 7121210101515 v v5 5 v v1 1 v v2 2 v v3 3 v v4 4 v v6 6 示例示例2 2:TKSTKS6 67:42(3)(3)普里姆算法的实现普里姆算法的实现 邻接矩阵结构邻接矩阵结构 typedef structtypedef struct char vexsmvnum char vexsmvnum;int arcsmvnummvnum int arcsmvnummvnum;int vexnum,arcnum int vexnum,arcnum;amgraph amgraph;记录前驱顶点
7、和记录前驱顶点和V(T)V(T)中到中到V-V-V(T)V(T)权值最小的边的存储空间权值最小的边的存储空间structstruct int adjvex int adjvex;int lowcostint lowcost;closedgenvnum closedgenvnum;算法实现算法实现 初始化:初始化:首先将初始顶点甜加入首先将初始顶点甜加入U U中,对其余的每一个顶点中,对其余的每一个顶点v vi i,将将closedgeiclosedgei 均初始化为到均初始化为到u u的边信息。的边信息。循环循环n-ln-l次,做加下处理:次,做加下处理:a a、从各组最小边从各组最小边clo
8、sedgevclosedgev 中选出最小的最小边中选出最小的最小边closedgekclosedgek,输出此边输出此边(v(v,k kV V-U)-U);b b、将将k k加入加入U U中;中;c c、更新剩余的每组最小边信息更新剩余的每组最小边信息closedgevclosedgev,(v(vV V-U)-U)。TKSTKS7 77:42 v v1 1v v2 2v v3 3v v4 4v v5 5v v6 610105 56 66 66 610107 7121210101515lowcostlowcost adjvexadjvex lowcostlowcost adjvexadjvex
9、 lowcostlowcost adjvexadjvex lowcostlowcost adjvexadjvex lowcostlowcost adjvexadjvex lowcostlowcost adjvexadjvex k k V-T(V)V-T(V)T(V)T(V)V V6 6V V5 5V V4 4V V3 3V V2 2 V V closedgeclosedge v v5 5 v v1 1 1 1 V V2 2V V3 3V V4 4V V5 5V V6 6 VV1 1 121215151010V V1 1V V1 1V V1 1 2 2 V V3 3V V4 4V V5 5V V
10、6 6 VV1 1V V2 2 V V2 2V V1 1V V2 2V V2 2 v v2 2 7 715156 65 50 03 3 v v3 3 V V4 4V V5 5V V6 6 VV1 1V V2 2V V3 3 7 715156 60 00 0V V2 2V V1 1V V2 24 4 v v4 4 V V5 5V V6 6 VV1 1V V2 2V V3 3V V4 4 6 610100 00 00 0V V4 4V V4 46 6 v v6 6 V V5 5 VV1 1V V2 2V V3 3V V4 4V V6 6 0 010100 00 00 0V V4 45 5 VV1
展开阅读全文