目前已经介绍了Kruskal和Prim算法,他们的复杂度一个是E logE一个是E logV,那么有没有复杂度为E的算法呢?理论上是可能的,但是目前还没有发现该算法。下图是最小生成树算法的发展过程。
从图中可以看到复杂度越來越接近E。
问题描述:给定一系列点的坐标,求包含所有点的最小生成树。
下图是这个问题的一个例子。
解决这个问题的基本思想就是先将每个点都看成一个独立的cluster,每次合并一对距离最近的cluster,直到所有的点都合并在一起为止。这种算法能够达到V logV的复杂度。
具体的算法可以参考论问:Fast Euclidean Minimum Spanning Tree Algorithm, Analysis
生物学中的基因序列分析也有用到最小生成树。
算法8-6:最小生成树研究现状,布布扣,bubuko.com
原文:http://blog.csdn.net/caipeichao2/article/details/32728621