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

6.9

 グラフについての考察

■

189

2012

年の国際空港協会（

Airports Council International, ACI

）の報告では、世界

の

159

ヶ国に

1,598

の空港があり、これは

2,553,604

要素の

2

次元行列に対応する。

ここで、「どれだけの要素が値を持つか」という質問の答えは、直行便の数に依存す

る。

ACI

の報告では、

2012

年に

7,900

万の「航空便」があり、これは、

1

日にほぼ

215,887

便となる。このすべてが直行便であるとしても（明らかに、直行便はもっ

と少ないはず）、これは行列の

92

％が空であることを意味する。疎行列の好例だろ

う。

6.9.2

 グラフ分析

本章のアルゴリズムを適用するに際して、隣接リストと隣接行列のいずれを使う

べきかの基本的な判断基準は、グラフが疎かどうかである。アルゴリズムの性能は

グラフの節点の個数

V

と辺の個数

E

から計算できる。ここでは、一般的なアルゴリ

ズムの教科書と同

様に、最良、平均、最悪時性能の式を

V

と

E

の

O

表記で表してい

る。すなわち、

O(V)

は、計算がグラフの節点数に比例したステップ数を要するこ

とを意味する。一方で、グラフ中の辺の密度も大いに関わる。疎グラフなら、

O(E)

は

O(V)

のオーダーだが、密グラフでは

O(V

2

)

に近くなる。

後で述べるが、同じアルゴリズムでもグラフの構造によって性能が異なる。例え

ば、

1

つの変形は

O((V

＋

E)*log V)

時間、もう

1

つの変形は

O(V

2

＋

E)

時間かかる

とする。どちらが効率的だろうか。表