最小生成树算法讲解

上传人:kms****20 文档编号:53561873 上传时间:2018-09-02 格式:PPT 页数:32 大小:515KB
返回 下载 相关 举报
最小生成树算法讲解_第1页
第1页 / 共32页
最小生成树算法讲解_第2页
第2页 / 共32页
最小生成树算法讲解_第3页
第3页 / 共32页
最小生成树算法讲解_第4页
第4页 / 共32页
最小生成树算法讲解_第5页
第5页 / 共32页
点击查看更多>>
资源描述

《最小生成树算法讲解》由会员分享,可在线阅读,更多相关《最小生成树算法讲解(32页珍藏版)》请在金锄头文库上搜索。

1、单元实验五 -最小生成树,生成树的概念,生成树 一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但只有足以构成一棵树的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(u0V),TE=开始,重复执行下述操作: 在所有uU,vV-U的边(u,v)中找一条代价最小的边(u0 ,v0),将其并入集合TE,同时将v0并入U集合

2、。 当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,V

3、1,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

4、,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,普里姆算法求最小生成树:从生成树

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

7、邻接顶点k已经在U集合中,顶点i加入U集合时,普里姆算法的实现,= 0,closedge2.adjvex=1.lowcost=6,closedge3.adjvex=1.lowcost=1,closedge4.adjvex=1.lowcost=5,V4,V1,V3,V2,V6,V5,1,6,5,当U集合中加入一个新顶点时,V-U集合中的顶点到U的最小代价边可能会更新,U集合的成员:,V-U集合的成员:,closedge5.adjvex=1.lowcost=,closedge6.adjvex=1.lowcost=,V4,V1,V3,V2,V6,V5,5,5,6,4,U集合的成员:,V-U集合的成员

8、:,当U集合中加入一个新顶点时,V-U集合中的顶点到U的最小代价边可能会更新,closedge2.adjvex=3.lowcost=5,closedge4.adjvex=1.lowcost=5,closedge5.adjvex=3.lowcost=6,closedge6.adjvex=3.lowcost=4,V4,V1,V3,V2,V6,V5,5,6,2,当U集合中加入一个新顶点时,V-U集合中的顶点到U的最小代价边可能会更新,U集合的成员:,V-U集合的成员:,closedge2.adjvex=3.lowcost=5,closedge4.adjvex=6.lowcost=2,closedge

9、5.adjvex=3.lowcost=6,V4,V1,V3,V2,V6,V5,5,6,当U集合中加入一个新顶点时,V-U集合中的顶点到U的最小代价边可能会更新,U集合的成员:,V-U集合的成员:,closedge2.adjvex=3.lowcost=5,closedge5.adjvex=3.lowcost=6,V4,V1,V3,V2,V6,V5,3,当U集合中加入一个新顶点时,V-U集合中的顶点到U的最小代价边可能会更新,U集合的成员:,V-U集合的成员:,V4,V1,V3,V2,V6,V5,U集合的成员:,V-U集合的成员:,普里姆算法求最小生成树, 6 1 5 6 5 3 1 5 5 6

10、45 5 2 3 6 6 4 2 6 ,1 2 3 4 5 6,1 2 3 4 5 6,图采用邻接矩阵表示,G.arcs =,#define MaxVnum 50 typedef int AdjMatrixMaxVnumMaxVnum; /double typedef struct int vexnum,arcnum; /顶点数、边数AdjMatrix arcs; /邻接矩阵 Graph; Graph G;,void MiniSpanTree_PRIM (Graph G, int u)/用普里姆算法从顶点u出发构造G的最小生成树for(j = 0; j G.vexnum; +j) /辅助数组初

11、始化if ( j != u ) closedgej = u, G.arcsuj;,struct int adjvex; double lowcost; closedgeMAX_VERTEX_NUM;,closedgeu.lowcost = 0; /初始,U=ufor(i = 1; i G.vexnum; +i) k = minimum(closedge); /求生成树的下一个顶点kcout closedgek.adjvex G.vexsk;closedgek.lowcost = 0;for(j = 0; j G.vexnum; +j)if (G.arcskj.adj 0, vi v-u,cou

12、t “(“ k “,“ closedgek.adjvex “)“; /输出生成树的边 closedgek.lowcost = 0; /顶点k并入U集合,for(j = 0; j G.vexnum; +j)if (G.arcskj closedgej.lowcost)closedgej.adjvex = k, closedgej.Lowcost = G.arcskj;,算法的时间复杂度为:O(n2),closedgej.adjvex = u; closedgej.lowcost = G.arcsuj;,选做内容,从键盘输入(或从文件读入)图的信息,用克鲁斯卡尔算法求解给定无向连通图的最小生成树,

13、最后输出最小生成树中的权值和所有的边。,克鲁斯卡尔(Kruskal)算法,假设连通网N=(V,E),则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,),图中每个顶点自成一个连通分量。在E中选择代价最小的边,若该边依附的顶点落在T中不同的连通分量上,则将此边加入到T中,否则舍去此边而选择下一条代价最小的边。依次类推,直至T中所有顶点都在同一连通分量上为止。,克鲁斯卡尔算法求最小生成树,V4,V1,V3,V2,V6,V5,6,5,1,2,6,6,5,5,3,4,V4,V1,V3,V2,V6,V5,1,2,3,4,最小代价生成树,克鲁斯卡尔算法求最小生成树,V4,V1,V3,V2,V

14、6,V5,6,5,1,2,6,6,5,5,3,4,V4,V1,V3,V2,V6,V5,1,2,3,4,5,V3、V4依附在同一个连通分量,最小代价生成树,克鲁斯卡尔算法求最小生成树,V4,V1,V3,V2,V6,V5,6,5,1,2,6,6,5,5,3,4,V4,V1,V3,V2,V6,V5,1,2,3,4,V1、V4依附在同一个连通分量,5,最小代价生成树,克鲁斯卡尔算法求最小生成树,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,最小代价生成树,克鲁斯卡尔(Kruskal)算法,否,将堆顶的边加入生成树后 是否形成回路?,在生成树中放置n个孤立顶点,根据边上的权值建小顶堆,是,将该边加入生成树中,

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 生活休闲 > 科普知识

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号