首页 > 代码库 > 算法8-6:最小生成树研究现状

算法8-6:最小生成树研究现状

目前已经介绍了Kruskal和Prim算法,他们的复杂度一个是E logE一个是E logV,那么有没有复杂度为E的算法呢?理论上是可能的,但是目前还没有发现该算法。下图是最小生成树算法的发展过程。



从图中可以看到复杂度越來越接近E。


最小生成树的应用


欧几里德最小生成树


问题描述:给定一系列点的坐标,求包含所有点的最小生成树。


下图是这个问题的一个例子。



解决这个问题的基本思想就是先将每个点都看成一个独立的cluster,每次合并一对距离最近的cluster,直到所有的点都合并在一起为止。这种算法能够达到V logV的复杂度。


具体的算法可以参考论问:Fast Euclidean Minimum Spanning Tree Algorithm, Analysis


生物学


生物学中的基因序列分析也有用到最小生成树。