2.2.1 最小生成树

2026-01-31 05:52:32 更新

● 最小生成树：在连通的带权图的所有生成树中，权值和最小的生成树（包含图中所有顶点的树）。

典型算法


算法

时间复杂度

说明

1

普里姆(Prim)算法

O(n2)

属于贪心策略，适合于稠密图(边数远远大于顶点数的图)

2

克鲁斯卡尔(Kruskal)算法

O(elog2e)

当前形成的集合T除最后结果外，始终是一个森林。较适合于稀疏图(边数远远小于顶点数的图)

3

博鲁夫卡(Boruvka)算法

O(ElogV)

基于贪心策略，优势在于其并行化能力，在大规模图上的效率比其他算法更高。

4

反向删除(Reverse-Delete)算法

O(ElogV)

基于贪心策略，优点在于实现简单，且可以在多数情况下得到接近于最优的结果，但在稠密图上可能效果较差。