算法技术手册（原书第2 版）

156

｜

第

6

章

Prim

算法

展示了如何从图中构造一个

MST

。它采用了一种贪心策略，算法的每一步都

朝着解前进，并且不会推翻之前的决定。在扩展一棵树

T

时，

Prim

算法

每次添加一条边，

直到生成

MST

（可以证明这是最小的）。它随机选择一个开始顶点

s

∈

V

，将

s

添加到

一个不断增长的集合

S

中，并确保

T

是由

S

中的边构成的树。

Prim

算法

是贪心算法，它

增量地将边添加到

T

中，直到计算出

MST

。其背后的原理是，在

u

∈

S

和

v

∈

V

-

S

之间

具有最小权值的边

(

u

,

v

)

必然属于

MST

。当找到最小权值的边

(

u

,

v

)

之后，将其被加入

T

中，

并将顶点

v

添加到集合

S

中。

该算法使用优先队列来存储属于

V

-

S

的顶点

v

，相关联的

优先级键值

等于某条边

(

u

,

v

)

的最低权值，其中

u

∈

S

。键值反应了优先队列中元素的优先级，值越低越重要。

Prim 算法小结

最好情况、平均情况和最坏情况：

O

((

V

+

E

)

*

log

V

)

computeMST (G)

foreach v in V do

key[v] =

∞

❶

pred[v] = -1

key[0] = 0

PQ = empty Priority Queue

foreach v in V do

insert (v, key[v]) into PQ

while PQ is not empty do

u = getMin(PQ)

❷

foreach edge(u,v) in E do

if PQ contains v then ...