隣接行列

行列という名の通り、グラフを２次元配列で表現します。配列のインデックスが各ノードの番号に対応します。例えば、この２次元配列を 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 のスペースが必要