隣接行列とは？りんせつぎょうれつ
隣接行列とは、グラフ（点＝頂点と、点どうしを結ぶ線＝辺でつながりを表した図）を、頂点数n×nの2次元配列で表す方法。i行j列の値に、頂点iから頂点jへ辺があるかどうか（1か0）や重みを入れる。2点間に辺があるかを添字の指定だけで判定できる反面、辺の少ないグラフでは0ばかりの表になり、記憶領域をnの2乗ぶん使う。
最終更新：2026-10-09
この語が出る過去問を解く →背景
路線図や友人のつながりを計算機で扱うには、つながり方を数値の並びに直さなければならない。表の形にすれば任意の2点を一度で引ける代わりに場所を食い、頂点ごとに隣を並べる形にすれば場所は節約できる代わりに探す手間が増える。どちらを選ぶかは辺の多さで決まる、という判断が問われる。
具体例
頂点A・B・Cで、AからBへ、BからCへ矢印があるグラフなら、A行B列とB行C列だけが1で残りは0になる。向きのないグラフでは辺が両方向に立つため、表は左上から右下へ引いた対角線を軸に対称の形になる。
試験での引っ掛け
向きのないグラフでは必ず対称になるが、向きのあるグラフでは対称になるとは限らない点が狙われる。対角の成分が1になるのは自分自身へ戻る辺がある場合だけで、通常は0。辺が少ないときは隣接リストのほうが有利という比較も問われる。
関連用語
出た過去問
出典：令和元年度 秋期 基本情報技術者試験 午前 問3（IPA）
ノードとノードの間のエッジの有無を、隣接行列を用いて表す。ある無向グラフの隣接行列が次の場合、グラフで表現したものはどれか。ここで、ノードを隣接行列の行と列に対…
正解：ノードを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つだけ）を数えるだけでも絞り込める。
出典：令和6年度 公開問題 基本情報技術者試験 科目B 問3（IPA）
次のプログラム中の に入れる正しい答えを、解答群の中から選べ。ここで、配列の要素番号は1から始まる。 図1に示すグラフの頂点には、1から順に整数で番号が付けられ…
正解：adjMatrix[u, v] ← 1 adjMatrix[v, u] ← 1
要点：無向グラフの隣接行列は対称。両方向の成分を1にする
隣接行列では、頂点uと頂点vを結ぶ辺があるときにu行v列を1にする。無向グラフなので辺に向きはなく、行列は対称になるためv行u列も同時に1にしなければならない。片方だけでは対称行列にならず、図2の隣接行列を再現できない。
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。