fc2ブログ



隣接行列

2006.04.21 00:00  グラフ

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


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

UUMatrix.gif


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

DUMatrix.gif


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

UWMatrix.gif


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


隣接行列表現の特徴
  • M[u][v] でエッジを参照できるので、ノード u とノード v の関係を定数時間でチェックすることができる
  • エッジの追加や削除が簡単かつ効率的(定数時間)
  • ノードの数が増えるとメモリをかなり消費する。ノード数を n とすると、n^2 のスペースが必要
スポンサーサイト



| コメント(0) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ