グラフのプロパティ

作成中

隣接リスト

各ノードが、そのノードに隣接するノードの番号のリストを持ちます。重みつきグラフの場合は、番号だけではなく重みもリストの要素に追加されます。リストの最後に番兵を設置しておくと便利です。

有向グラフ



重みつき有向グラフ

隣接リスト表現の特徴

• エッジの数に比例したメモリしか必要としない
• ノード u とノード v の関係を調べるには、リストを探索しなければならない
• エッジの追加・削除の操作が難しく、効率的に行えない
• 実装がやや難しい

隣接行列

行列という名の通り、グラフを２次元配列で表現します。配列のインデックスが各ノードの番号に対応します。例えば、この２次元配列を M とすると、M[i][j] がノード i とノード j の関係を表します。


無向グラフ
ノード i とノード j の間にエッジがある場合、M[i][j] と M[j][i] の値を 1 とします。エッジがない場合は 0 とします。隣接行列は右上と左下が対照になります。




有向グラフ
ノード i からノード j へ向かってエッジがある場合、M[i][j] の値を 1 とします。エッジがない場合は 0 とします。




重みつき無向グラフ
ノード i とノード j の間に重さ w のエッジがある場合、M[i][j] と M[j][i] の値を w とします。エッジがない場合は、問題上有り得ない値に設定します。例では∞としていますが、プログラムでは非常に大きな値に設定しておくと便利な場合が多いです。




重みつき有向グラフ
ノード i からノード j へ向かって重さ w のエッジがある場合、M[i][j] の値を w とします。エッジがない場合は、非常に大きな値に設定します。

隣接行列表現の特徴

• M[u][v] でエッジを参照できるので、ノード u とノード v の関係を定数時間でチェックすることができる
• エッジの追加や削除が簡単かつ効率的（定数時間）
• ノードの数が増えるとメモリをかなり消費する。ノード数を n とすると、n^2 のスペースが必要

グラフの表現

グラフはコンピュータ上で表されるデータ構造の一種です。コンピュータの中で、問題に応じたグラフ構造を効率的に表現し操作されるようなプログラムを実装しなければなりません。

プログラム上でグラフを表現し操作する代表的な方法に、
隣接行列 (adjacency matrices)による表現と、
隣接リスト (adjacency lists)による表現があります。

これらの方法とその特徴を簡単に紹介します。

グラフの種類

グラフの種類には大きく分けて４つあります。

名前	特徴
無向グラフ	エッジに方向がない
有向グラフ	エッジに方向がある
重みつき無向グラフ	エッジに重みがあり、方向がない
重みつき有向グラフ	エッジに重みがあり、方向がある

無向グラフの例

友達関係をグラフにした例です。この例ではエッジに方向をもたせていません。例えば、「友達の友達は友達としたとき、Ａ君とＢ君は友達ですか？」や「いくつの友達グループがありますか？」などの問題が考えられます。



有向グラフの例

物事の手順をグラフにした例です。朝起きてから学校に行くまでの簡単な手順を示していますが、このグラフから様々な要素が読み取れます。例えば、朝起きてから朝食を食べなくても学校へ行けますが、着替えなければ学校には行けないことが分かります。起きて→着替えて→学校へ行く、というのがこの手順の最短経路となります。



重みつき無向グラフの例

各ノードが市町を表し、エッジが市町を行き来するのにかかる時間を表しています（架空のもの）。ある町からある町への最短経路を求めたいなどの類の問題はよくあります。




ここで取り上げたものは、ほんの例でしかありません。「すべての問題はグラフで表せる」と言われるほど、グラフ構造は様々な問題で応用されます。

グラフとは

グラフ（Graph）とは「対象の集合と、それらのつながりの集合」を表すためのデータ構造で、様々な問題に応用されます。現実世界のあらゆる問題をモデル化することができるので、グラフに関する重要なアルゴリズムが数多く存在します。

簡単なグラフの例を以下に示します。






「対象」はノード(node)またはバーテックス(vertex)と呼ばれ、上図の円に相当します。「つながり」はノードとノードの関係を表し、エッジ(edge)と呼ばれ、上図で円と円を結んでいる線に相当します。

グラフには様々な種類があり、問題によって応用の方法も違ってきます。