隣接行列とは？

隣接行列の意味

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

隣接行列と関連する用語

• グラフ
• 幅優先探索
• 配列

隣接行列が出た過去問

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

  正解：ノードをa,b,c,d,[すき間]e,fの順に並べ、直線でa-b、b-c、c-d、e-fを結び、さらに弧でc-e（dの上を通る）とb-d（cの下を通る）を結んだグラフ

  要点：隣接行列の1の位置＝辺。次数を数えて図と照合する

  無向グラフの隣接行列は対称行列になり、値が1のマス（行,列）の組がそのまま辺を表す。この行列で1が立っているのは a-b、b-c、b-d、c-d、c-e、e-f の6組であり、辺の数は6本、各頂点の次数は a=1、b=3、c=3、d=2、e=2、f=1 となる。この6本の辺をすべて過不足なく備えた図が正解であり、次数の分布（次数1の頂点が a と f の2つだけ）を数えるだけでも絞り込める。

  出典：令和1年度 秋期 基本情報技術者試験 午前 問3（IPA）

• 次のプログラム中の に入れる正しい答えを、解答群の中から選べ。ここで、配列の要素番号は1から始まる。 図1に示すグラフの頂点には、1から順に整数で番号が付けられ…

  正解：adjMatrix[u, v] ← 1 adjMatrix[v, u] ← 1

  要点：無向グラフの隣接行列は対称。両方向の成分を1にする

  隣接行列では、頂点uと頂点vを結ぶ辺があるときにu行v列を1にする。無向グラフなので辺に向きはなく、行列は対称になるためv行u列も同時に1にしなければならない。片方だけでは対称行列にならず、図2の隣接行列を再現できない。

  出典：令和6年度 （公開問題） 基本情報技術者試験 kamokuB 問3（IPA）