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

6.1

 グラフ

■

153

図6-4　有向重み付きグラフの隣接行列表現

隣接リストを使って無向グラフを貯える場合、同じ辺

(u, v)

が

2

度、

u

と

v

との両

方のリンク付きリストに現れる。したがって、隣接リストでの無向グラフのストレー

ジ使用量は、同じ個数の節点と辺を持つ有向グラフの

2

倍になる。しかし、こうす

ることで、節点

u

の近傍を探すのにかかる時間が実際の近傍点の個数に比例した時

間で済む。隣接行列を使って無向グラフを貯える場合には、

A[i ][ j ]=A[ j ][i ]

と

なる。

6.1.1

 データ構造の設計

有向（および無向）グラフを貯える

C

++

の

Graph

クラスを、

C

++

標準テンプレート

ライブラリ（

STL

）のコアクラスによる隣接リスト表現を用いて実装する。具体的に

は

list

の配列を保持し、

1

つの

list

が

1

節点に対応する。各節点

u

の

list

には、オ

ブジェクト

IntegerPair

が貯えられ、重み

w

の辺

(u, v)

を表す。

グラフの操作は、い

くつかの種類に分けられる。

作成（Create）

グラフは、有向であれ無向であれ、最初に

n

個の節点の集合から構築さ

れる。グラフが無向なら、辺

(u, v)

の追加に際して、辺

(v, u)

も追加する。

検査（Inspect）

グラフが有向かどうか、ある節点から出ている辺はどれか、ある辺が実

際に存在するかどうか、あるいは辺の重みはどれだけかなどを知ること

ができる。必要であれば、グラフ内の任意の節点に対して、隣接辺（およ