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

184

■

6

章 グラフアルゴリズム

含む可能性があるので、

O(E)

性能の実行となる。

6.8

 最小被覆木アルゴリズム

無向連結グラフ

G

＝

(V, E)

が与えられたとき、すべての節点を連結していると

いう意味で、グラフを「覆う」

E

の辺の部分集合

ST

を求めたいことがある。さら

に、

ST

の辺の重みの総和が可能な

ST

の中で最小であるとき、それを最小被覆木

（

MST

）と呼ぶ。

プリム法

（

Prim's Algorithm

）は、そのような連結グラフから、貪欲法で以前の

決定を覆すことなく

MST

を構築する方法を示す。

プリム法

は、

MST

に到達する（得

られた被覆木が最小と証明できる）まで

1

つずつ辺を追加して被覆木

T

を成長させ

ていく。まず、成長集合

S

に属する開始節点

s

∈

V

をランダムに選ぶ。これは

T

が

s

を根とする木となることを意味する。

プリム法

は、

MST

が得られるまで、貪欲に

T

に辺を順次加えていく。このアルゴリズムの背後にあるのは、直感的には、

u

∈

S

と

v

∈

V-S

との間の最小重みを持つ辺

(u, v)

は、きっと

MST

に含まれるはずだという

考えだ。最小重みの辺

(u, v)

が見つかったら、それを

T

に加え、節点

v

を

S

に加える。

このアルゴリズムは優先度付きキューを用いて節点

v

∈

V-S

を貯える。ここで優

先度キーは辺

(u, v)

（ただし、

u)

∈

S

）の最小重みに等しいとする。このキー値は、

優先度キューにおける要素の優先度を反映する。値が小さいほど優先度が高い。

図6-16に小さな無向グラフに対する

プリム法

の振る舞いを示す。優先度