隣接行列とは？

隣接行列の意味

グラフを、頂点数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²で増える点も弱点。

隣接行列と関連する用語

• 幅優先探索
• 配列

隣接行列が出た過去問

• ノード1〜5をもつグラフを隣接行列で表したもののうち、木となるものはどれか。ここで、隣接行列のi行j列目の成分は、ノードiとノードjを結ぶエッジがある場合は1、…

  正解：イ：5×5の隣接行列 [[0,1,0,0,1],[1,0,1,1,0],[0,1,0,0,0],[0,1,0,0,0],[1,0,0,0,0]]

  要点：nノードの木は連結・閉路なし・辺がn-1本

  nノードのグラフが木であるためには、連結であり、かつ閉路をもたず、辺の本数がn-1本である必要がある。ノードが5個なので辺は4本でなければならない。イは1-2、1-5、2-3、2-4の4本の辺で全ノードが連結され、閉路も無いので木となる。

  出典：平成29年度 秋期 応用情報技術者試験 午前 問6（IPA）

• ノードとノードの間のエッジの有無を，隣接行列を用いて表す。ある無向グラフの隣接行列が次の場合，グラフで表現したものはどれか。ここで，ノードを隣接行列の行と列に対…

  正解：ウ：ノードをa,b,c,d,e,fの順に横一列に配置。直線で結ばれているのはa-b、b-c、c-d、e-f。d-e間は非連結。上側の弧でc-eを結び、下側の弧でb-dを結ぶ。

  要点：隣接行列の1の位置とグラフのエッジは一対一に対応する

  隣接行列で1になっている位置がそのままエッジになる。この行列ではa-b、b-c、b-d、c-d、c-e、e-fの6本が存在し、d-eのエッジは存在しない。横一列に並べた図のうち、この6本を過不足なく描いたものが正解である。

  出典：平成29年度 春期 応用情報技術者試験 午前 問3（IPA）