论文部分内容阅读
这是一种最小生成树算法,基于分治理念,采用破圈法。依据权值中位数,将图中的边一分为二,以降低边与边之间的耦合。破圈功能通过边合并操作实现,一次递归删除一些边,使得分解后子问题的总规模不大于原问题的规模。该算法效率较高,最坏情况下为O(|E|×log2|V|),一般情况下为O(|E|×log2(log2|V|))。