• / 32
  • 下载费用:10 金币  

最小生成树算法讲解.ppt

关 键 词:
最小生成树算法讲解.ppt
资源描述:
单元实验五 ------最小生成树,生成树的概念,生成树 一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但只有足以构成一棵树的n-1条边。 生成树不唯一,生成树,最小代价生成树,生成树的代价等于其边上的权值之和。,V4,,,,,,V1,V3,V2,V6,V5,,,,,,6,5,1,2,6,6,5,5,3,4,,,最小代价生成树,两种常用的构造最小生成树的方法: 普里姆算法 克鲁斯卡尔算法,假设N=(V,E)是连通网,TE是N上最小生成树中边的集合。 算法从U={u0}(u0∈V),TE={}开始,重复执行下述操作: 在所有u∈U,v∈V-U的边(u,v)中找一条代价最小的边(u0 ,v0),将其并入集合TE,同时将v0并入U集合。 当U=V则结束,此时TE中必有n-1条边,则T=(V,{TE})为N的最小生成树。 普里姆算法构造最小生成树的过程是从一个顶点U={u0}作初态,不断寻找与U中顶点相邻且代价最小的边的另一个顶点,扩充到U集合直至U=V为止。,普里姆(Prim)算法,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,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,普里姆算法求最小生成树:从生成树中只有一个顶点开始,到顶点全部进入生成树为止,最小代价生成树,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,普里姆算法求最小生成树:从生成树中只有一个顶点开始,到顶点全部进入生成树为止,最小代价生成树,普里姆算法求最小生成树:从生成树中只有一个顶点开始,到顶点全部进入生成树为止,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?,,是,否,,,结束,,,开始,,基本要求,从键盘(或数据文件)输入图的信息,用普里姆算法求解给定无向连通图的最小生成树,最后输出最小生成树中的权值和所有的边,图的存储结构自行设定。,例如 下图的输出为,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; }closedge[MAX_VERTEX_NUM];,,closedge[i].adjvex=k,closedge[i].lowcost,顶点i与顶点k邻接顶点k已经在U集合中,顶点i加入U集合时,普里姆算法的实现,= 0,closedge[2].adjvex=1.lo
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:最小生成树算法讲解.ppt
链接地址:https://www.weizhuannet.com/p-9861313.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

微传网博客

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开