隣接行列とは？

隣接行列の意味

グラフを、頂点数n×nの2次元配列で表現する方法。行iと列jの要素に、頂点iから頂点jへの辺の有無（1／0）や重みを入れる。2頂点間に辺があるかを即座に判定できるが、記憶領域はn²必要で、辺が少ないグラフでは無駄が大きい。

隣接行列の具体例

頂点A・B・Cで、A→B、B→Cの有向辺があるなら、A行B列とB行C列が1、その他は0になる。無向グラフなら辺は双方向なので行列は対角線に対して対称になる。辺が少ない場合は、頂点ごとに隣の頂点をリストで持つ隣接リストが有利。

隣接行列は試験でどう引っ掛けられる？

無向グラフでは対称行列になるが、有向グラフでは対称にならない点が狙われる。また対角成分が1になるのは自分自身への辺（自己ループ）がある場合だけで、通常は0。頂点数が増えると領域がn²で増える点も弱点。

隣接行列と関連する用語

• グラフ