目前已經介紹了Kruskal和Prim算法，他們的複雜度一個是E logE一個是E logV，那麼有沒有複雜度為E的算法呢？理論上是可能的，但是目前還沒有發現該算法。下圖是最小生成樹算法的發展過程。
從圖中可以看到複雜度越來越接近E。
最小生成樹的應用
歐幾裡德最小生成樹
問題描述：給定一系列點的坐标，求包含所有點的最小生成樹。
下圖是這個問題的一個例子。
解決這個問題的基本思想就是先将每個點都看成一個獨立的cluster，每次合并一對距離最近的cluster，直到所有的點都合并在一起為止。這種算法能夠達到V logV的複雜度。
具體的算法可以參考論問：Fast Euclidean Minimum Spanning Tree Algorithm, Analysis
生物學
生物學中的基因序列分析也有用到最小生成樹。