最小生成树论文摘要

问：最小生成树是否唯一求解答

1. 答：当连通图中各边权值不相等时，最小生成树唯一；当有相等的权值时最小生成树可能唯一可能不唯一，具体情况具体分析。

问：谁知道最小生成树的o(n)算法， 姚期智提出的?

1. 答：姚期智进入计算机科学领域最早的论文之一《寻找最小生成
   树的O(|E|log log|V|)算法》一文就引起轰动，因为学术界原先认为，
   寻找最小生成树算法的时间复杂度的下界是O(E log V)，而姚期智的论
   文证明这个极限是可以打破的。在姚的这一开创性工作的基础上，经过近
   20年的努力，人们终于设计出了寻找最小生成树的线性时间算法。
   关于该算法具体的实现你可以参看<算法设计与分析导论/计算机科学丛书>
   (机械工业出版社)中的
   11.6 最小生成树的随机线性时间算法

问：欧几里德 平面最小生成树算法

1. 答：去看Winter Camp 2006 王栋的论文
   可以做到n log n

本文来源: https://www.85lw.cn/article/5b9c5d334f0cb3b7207a0fc1.html