数据结构第七章第四节.ppt
《数据结构第七章第四节.ppt》由会员分享,可在线阅读,更多相关《数据结构第七章第四节.ppt(43页珍藏版)》请在三一办公上搜索。
1、7.4.3 最小生成树,Minimum Cost Spanning Tree-MST,构造MST的原则:,必须使用网络中的边来构造最小生成树;必须使用且仅使用n-1条边来连接网络中的n个顶点;不能使用产生回路的边;,u,MST性质:,假设N=(V,E)是一个连通网,U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边,其中u属于U,v属于V-U,则必存在一棵包含边(u,v)的最小生成树,v,T,T,(u,v),(u,v),U,V-U,最小两栖边,MST性质:,假设N=(V,E)是一个连通网,U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边,其中u属于U,v属于V-U,则必存
2、在一棵包含边(u,v)的最小生成树,普里姆(Prim)算法 克鲁斯卡尔(Kruskal)算法,两种算法:,假设N=(V,E)是连通网,TE是N上最小生成树边集合。(1)U=u0(u0属于V),TE=(2)在所有u,vV的边(u,v)E 中找一条代 价最小的边(u0,v0)并入集合TE,同时v0并入U,(3)如果V,转(2),普里姆(Prim)算法,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,普里姆(Prim)算法,V1,V2,V4,V3,V5,V6,6,5,1,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,普里姆(Prim)算法,V
3、1,V2,V4,V3,V5,V6,5,1,6,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,普里姆(Prim)算法,V1,V2,V4,V3,V5,V6,5,1,5,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,普里姆(Prim)算法,V1,V2,V4,V3,V5,V6,5,1,5,6,4,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,普里姆(Prim)算法,V1,V2,V4,V3,V5,V6,5,1,5,6,4,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,普里姆(Prim)
4、算法,V1,V2,V4,V3,V5,V6,1,5,6,4,2,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,普里姆(Prim)算法,V1,V2,V4,V3,V5,V6,1,5,6,4,2,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,普里姆(Prim)算法,V1,V2,V4,V3,V5,V6,1,5,6,4,2,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,普里姆(Prim)算法,V1,V2,V4,V3,V5,V6,1,5,4,2,3,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4
5、,2,普里姆(Prim)算法,V1,V2,V4,V3,V5,V6,1,5,4,2,3,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,普里姆(Prim)算法,V1,V2,V4,V3,V5,V6,1,5,4,2,3,/记录从顶点集 U 到 V-U 的代价最小的边辅助数组struct VerTexType adjvex;VRType lowcost;closedgeMAX_VERTEX_NUM;,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,closedgei-1.lowcost=Mincost(uj,vi),viV-U,closedgei
6、-1.adjvex=uj,U=v1,v3,V-U=v2,v4,v5,v6,ujU,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,V1,V2,V4,V3,V5,V6,6,5,1,i,closedge,V2,V3,V4,V5,V6,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,V1,V2,V4,V3,V5,V6,6,5,1,i,closedge,V2,V3,V4,V5,V6,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,i,closedge,V2,V3,V4,V5,V6,V1,V2,V4,V3,V5,V6,6
7、,5,1,0,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,i,closedge,V2,V3,V4,V5,V6,V1,V2,V4,V3,V5,V6,5,5,1,0,5,v3,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,i,closedge,V2,V3,V4,V5,V6,V1,V2,V4,V3,V5,V6,5,5,1,0,5,v3,6,4,6,v3,4,v3,V1,V2,V4,V3,V5,V6,6,5,1,5,5,6,6,3,4,2,i,closedge,V2,V3,V4,V5,V6,0,5,v3,6,v3,4,v3,V1,V2,V4
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 第七 第四
链接地址:https://www.31ppt.com/p-6578930.html