グラフおける隣接行列について

グラフにおける隣接行列について、概念をまとめたいと思います。

隣接行列とは

隣接行列は、2次元の配列でグラフを表現する方法です。
配列のインデックスが各々の頂点番号を表します。

隣接行列の2次元配列をMとするとM[i][j]が、頂点iと頂点jの関係を示します。
頂点と頂点が辺でつながれている場合は1やtrueで表し、
頂点と頂点間で繋がりがない場合は、0やfalseで表現します。

無効グラフにおける隣接行列

隣接行列の2次元配列をMとします。
無効グラフの隣接行列では、頂点i,jの間に辺があるとすると、
、M[i][j]、M[j][i]の両方の値を1にし、辺がない場合は0にします。 隣接行列は、右上と左下が対象になります。

下図のような無効グラフがあるとします。

これを隣接行列に直すと以下のようになります。
頂点と頂点が辺でつながれている場合は配列の要素が1になります。

有効グラフにおける隣接行列

有効グラフにおける隣接行列では、頂点iから頂点jに向かって辺がある場合、
M[i][j]の値を1とし、辺がない場合0とします。
無効グラフと違い頂点同士必ず相互に1とはなりません。

下図のような有効グラフがあるとします。

この有効グラフの隣接行列は以下のようになります。

隣接行列の長所

配列M[i][j]により、辺(u,v)を参照できるので、頂点uと頂点vの関係をO(1)で参照することができます。

隣接行列の短所

• 一つの隣接行列では頂点uから頂点vへの関係を一つしか記録できない点
  
• 頂点の数の2乗のメモリを使用する点

参考
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造