最小生成树算法详解.ppt
《最小生成树算法详解.ppt》由会员分享,可在线阅读,更多相关《最小生成树算法详解.ppt(35页珍藏版)》请在三一办公上搜索。
1、最小生成树算法-prim&Kruskal,生成树的概念,生成树一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但只有足以构成一棵树的n-1条边。生成树不唯一,生成树,最小代价生成树,生成树的代价等于其边上的权值之和。,V4,V1,V3,V2,V6,V5,6,5,1,2,6,6,5,5,3,4,最小代价生成树,两种常用的构造最小生成树的方法:普里姆算法(prim)克鲁斯卡尔算法(Kruskal),普里姆(Prim)算法,假设N=(V,E)是连通网,TE是N上最小生成树中边的集合。算法从U=u0(u0V),TE=开始,重复执行下述操作:在所有uU,vV-U的边(u,v)中找一条代价最小的
2、边(u0,v0),将其并入集合TE,同时将v0并入U集合。当U=V则结束,此时TE中必有n-1条边,则T=(V,TE)为N的最小生成树。普里姆算法构造最小生成树的过程是从一个顶点U=u0作初态,不断寻找与U中顶点相邻且代价最小的边的另一个顶点,扩充到U集合直至U=V为止。,V4,V1,V3,V2,V6,V5,6,5,1,2,6,6,5,5,3,4,V4,V1,V3,V2,V6,V5,1,2,5,3,4,U,V-U,V1,V2,V3,V4,V5,V6,步骤,(0),最小代价生成树,普里姆算法求最小生成树:从生成树中只有一个顶点开始,到顶点全部进入生成树为止,V4,V1,V3,V2,V6,V5,1
3、,6,5,V1,V3,1,V1,V2,V3,V4,V5,V6,步骤,(0),U,V-U,普里姆算法求最小生成树:从生成树中只有一个顶点开始,到顶点全部进入生成树为止,最小代价生成树,V4,V1,V3,V2,V6,V5,6,5,V1,V3,1,V1,V2,V3,V4,V5,V6,步骤,(0),V6,4,6,5,5,4,U,V-U,普里姆算法求最小生成树:从生成树中只有一个顶点开始,到顶点全部进入生成树为止,最小代价生成树,V4,V1,V3,V2,V6,V5,6,5,V4,V1,V3,1,V1,V2,V3,V4,V5,V6,步骤,(0),V6,4,6,5,5,2,6,2,U,V-U,普里姆算法求最
4、小生成树:从生成树中只有一个顶点开始,到顶点全部进入生成树为止,最小代价生成树,V4,V1,V3,V2,V6,V5,6,V4,V1,V3,1,V1,V2,V3,V4,V5,V6,步骤,(0),V2,V6,4,6,5,6,2,5,U,V-U,普里姆算法求最小生成树:从生成树中只有一个顶点开始,到顶点全部进入生成树为止,最小代价生成树,V4,V1,V3,V2,V6,V5,V4,V1,V3,1,V1,V2,V3,V4,V5,V6,步骤,(0),V2,V6,V5,4,6,6,2,5,3,3,U,V-U,普里姆算法求最小生成树:从生成树中只有一个顶点开始,到顶点全部进入生成树为止,最小代价生成树,普里姆
5、算法求最小生成树:从生成树中只有一个顶点开始,到顶点全部进入生成树为止,V4,V1,V3,V2,V6,V5,V4,V1,V3,1,V1,V2,V3,V4,V5,V6,步骤,(0),V2,V6,V5,4,2,5,3,U,V-U,最小代价生成树,普里姆(Prim)算法,生成树中只放置一个顶点,在关联生成树顶点的边中(即边的一个顶点在生成树中,另一个顶点不在)取权值最小者,将选中的边加入生成树,同时将该边的关联顶点加入生成树中,生成树中顶点数小于n?,是,否,结束,开始,从键盘(或数据文件)输入图的信息,用普里姆算法求解给定无向连通图的最小生成树,最后输出最小生成树中的权值和所有的边,图的存储结构自
6、行设定。,基本要求,例如 下图的输出为,weight:15(v1,v3)(v3,v6)(v6,v4)(v3,v2)(v2,v5)或者(1,3)(3,6)(6,4)(3,2)(2,5),普里姆算法的实现,顶点集合如何表示?最小边如何选择?一个顶点加入U集合(生成树中)如何表示?,struct int adjvex;double lowcost;closedgeMAX_VERTEX_NUM;,closedgei.adjvex=k,closedgei.lowcost,顶点i与顶点k邻接顶点k已经在U集合中,顶点i加入U集合时,=0,closedge2.adjvex=1.lowcost=6,close
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最小 生成 算法 详解
链接地址:https://www.31ppt.com/p-5750714.html