最小支撑树问题的三个算法

Three Algorithms for Minimum Support Tree Problem

最小支撑树是指找图G的一棵权重最小的支撑树,探讨最小支撑树问题的三个算法(避圈法、破圈法、反圈法)及其时间复杂性,证明了反圈法的时间复杂性最优。

The minimum support tree is a support tree with the least weight in finding graph g.Three algorithms （cycle avoidance method, loop breaking method, anti-cycle method） and its timecomplexity are discussed. The optimal time complexity of the inverse cycle method is proved.