图算法二.ppt
《图算法二.ppt》由会员分享,可在线阅读,更多相关《图算法二.ppt(23页珍藏版)》请在三一文库上搜索。
1、图算法(二),最小生成树 minimum spanning tree,最小生成树定义,问题背景: 图模型中的边与边权重(开销,代价)关联的各种应用 航空领域: 边-航线, 权重-距离,价格或时间 电路: 边-电线, 权重-长度,开销或时间 工作规划: 边-任务, 权重-执行任务的时间开销,最小生成树定义,求开销最小值问题包含两类算法: (1) 查找将所有点连接在一起的最低开销路径. 最小生成树 多用于无向图 (2) 查找两个已知点之间的最低开销路经. 最短路径 多用于有向图,最小生成树定义,生成树 如果连通图G的一个子图是一棵包含G的所有顶点的树,则该子图称为G的生成树(SpanningTre
2、e)。 图的生成树不惟一。 最小生成树 生成树T各边的权值总和称为该树的权;权最小的生成树称为G的最小生成树(Minimum SpannirngTree)。最小生成树可简记为MST,最小生成树,假设要在 n 个城市之间建立通讯联络网,则连通 n 个城市只需要修建 n-1条线路,如何在最节省经费的前提下建立这个通讯网?,问题:,构造网的一棵最小生成树,即: 在 e 条带权的边中选取 n-1 条边(不构成回路),使“权值之和”为最小。,算法二:(克鲁斯卡尔算法),该问题等价于:,算法一:(普里姆算法),取图中任意一个顶点 v(一般取第一个点) 作为生成树的根,之后往生成树上添加新的顶点 w。在添加
3、的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边,并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点,直至生成树上含有 n-1 个顶点为止。,普里姆算法的基本思想:,例如:,a,e,d,c,b,g,f,14,8,5,3,16,21,所得生成树权值和,= 14+8+3+5+16+21 = 67,1)图采用邻接矩阵存储。 2)第一个点为树根。 2)找到目前情况下能连上的权值最小的边的另一端点,加入之,重复n-1次。,在生成树的构造过程中,图中 n 个顶点分属两个集合:已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U ,则应在所有连通U中顶点
4、和V-U中顶点的边中选取权值最小的边。,一般情况下所添加的顶点应满足下列条件:,设置一个辅助数组closedge,对当前VU集中的每个顶点,记录和顶点集U中顶点相连接的代价最小的边:,int clomaxv;,a,e,d,c,b,a,a,a,19,14,18,14,例如:,e,12,e,e,8,16,8,d,3,d,d,7,21,3,c,5,5,19 m m 14 m 18 19 5 7 12 m m m 5 3 m m m m 7 3 8 21 m 14 12 m 8 m 16 m m m 21 m 27 18 m m m 16 27,1)顶点1作为树的根,初始化clo数组 cloi=map
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法
链接地址:https://www.31doc.com/p-3196591.html