アルゴリズムクイックリファレンス 第2版

186

■

6

章 グラフアルゴリズム

プリム法

Prim's Algorithm

最良 平均 最悪

O((V

＋

E )*log V )

computeMST (G)

foreach v in V do

key[v] =

∞

❶

最初は全節点が到達不能と考える。

pred[v] = -1

key[0] = 0

PQ =

空の

Priority Queue

foreach v in V do

insert (v, key[v]) into PQ

while PQ is not

空

do

u = getMin(PQ)

❷

計算された距離が最小の節点を見つける。

foreach

辺

(u, v) in E do

if PQ

が

v

を含む

then

w =

辺

(u,v)

の重み

if w < key[v] then

❸

v

の推定コストを更新して、

pred[v]

に

MST

辺を記録する。

pred[v] = u

key[v] = w

decreasePriority (PQ, v, w)

end

6.8.1

 入出力

入力は無向グラフ

G

＝

(V, E)

。

出力は、

pred[]

配列に収められた

MST

。

MST

の根は

pred[v]

＝−

1

の節点。

6.8.2

 解

例6-8に示す

C

++

による実装は、

プリム法

の中心となる優先度付きキューの実装

に二分ヒープを用いている。通常は、二分ヒープを用いると、主ループでの節点が

優先度キューにあるかどうかのチェック（二分ヒープに組み込まれていない操作）の

ために効率が悪い。しかし、このアルゴリズム ...