目前已经介绍了Kruskal和Prim算法,他们的复杂度一个是E logE一个是E logV,那么有没有复杂度为E的算法呢?理论上是可能的,但是目前还没有发现该算法。下图是最小生成树算法的发展过程。
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIiclRnblN0LclHdpZXYyd2LcBzNvwVZ2x2bzNXak9CX90TQNNkRrFlQKBTSvwFbslmZvwFMwQzLcVmepNHdu9mZvwFVywUNMZTY18CX052bm9CX9kkeihGaykFcWd0YwZkMZZXUYpVd1kmYr50MZV3YyI2cKJDT29GRjBjUIF2LcRHelR3LcJzLctmch1mclRXY39TOwYDOwgDN5EDMyYDM0EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
从图中可以看到复杂度越來越接近E。
最小生成树的应用
欧几里德最小生成树
问题描述:给定一系列点的坐标,求包含所有点的最小生成树。
下图是这个问题的一个例子。
解决这个问题的基本思想就是先将每个点都看成一个独立的cluster,每次合并一对距离最近的cluster,直到所有的点都合并在一起为止。这种算法能够达到V logV的复杂度。
具体的算法可以参考论问:Fast Euclidean Minimum Spanning Tree Algorithm, Analysis
生物学
生物学中的基因序列分析也有用到最小生成树。