Prim 算法及其高效实现

文章预览

背景 最小生成树 （Minimum Spanning Trees） ，简称MST。是图论中一个非常重要的概念。解决这个问题有两种算法，今天暂且先来讨论一下Prim Algorithm。不做特别说明，讨论的都是无向图。 首先介绍一下最小生成树的概念，我们知道，图可以这样定义 G=(V,E) ，其中 G 表示图，V 表示顶点集合，E 表示边集合。最小生成树是这样一棵树，它满足： 通俗地讲，就是使得图GG连通时，所选取的边的长度的和最小。 如上图，加粗的路径就是在最小生成树上的路径。 算法讲解： 现在，我们开始讨论Prim Algorithm。这个算法可以分为下面几个步骤： 将顶点集 V 分成两个集合 A 和 B，其中集合 A 表示目前已经在MST中的顶点，而集合 B 则表示目前不在 MST 中的顶点。 寻找与集合 A 连通的 ………………………………