Prim算法以及优化实现.doc
《Prim算法以及优化实现.doc》由会员分享,可在线阅读,更多相关《Prim算法以及优化实现.doc(3页珍藏版)》请在三一文库上搜索。
1、Prim算法以及优化实现最小生成树(Minimum Spanning Trees),简称MST。是图论中一个非常重要的概念。解决这个问题有两种算法,今天暂且先来讨论一下Prim Algorithm。不做特别说明,讨论的都是无向图。首先介绍一下最小生成树的概念,我们知道,图可以这样定义 G=(V,E) ,其中 G 表示图,V 表示顶点集合,E 表示边集合。最小生成树是这样一棵树,它满足:通俗地讲,就是使得图GG连通时,所选取的边的长度的和最小。如上图,加粗的路径就是在最小生成树上的路径。算法讲解:现在,我们开始讨论Prim Algorithm。这个算法可以分为下面几个步骤:将顶点集 V 分成两个
2、集合 A 和 B,其中集合 A 表示目前已经在MST中的顶点,而集合 B 则表示目前不在 MST 中的顶点。寻找与集合 A 连通的最短的边 (u,v),将这条边加入最小生成树中。(此时,与(u,v) 相连的顶点,不妨设为 Bi,也应加入集合 A 中)重复第二步,直至集合 B 为空集。算法的大体思想就是这样了。为了方便理解,我们先来看一下下面一张图片:对照上面的图片,想必对于Prim Algorithm也有了一定的理解。下面我们来设计算法,显然,我们需要遍历集合 A 中所有顶点及与之相连的边,取连接到集合B的权值最小的边,加入最小生成树。这样一来,复杂度将达到 O(n3)。我们可以对这个想法进行
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Prim 算法 以及 优化 实现
链接地址:https://www.31doc.com/p-3271672.html