隣接行列とは？りんせつぎょうれつ
隣接行列とは、グラフを頂点数n×nの2次元配列で表す方法で、i行j列に頂点iから頂点jへの辺の有無や重みを入れる。2頂点間に辺があるかを添字アクセスだけで判定できる一方、記憶領域はn²必要で、辺が少ない疎グラフでは無駄が大きい。対比されるのが隣接リストである。
最終更新：2026-10-06
この語が出る過去問を解く →背景
グラフの探索や最短経路の計算では、「ある頂点の隣は誰か」と「この2点はつながっているか」という二つの問いが繰り返し現れる。片方を速くする表現はもう片方を遅くするため、どちらの問いが多いかで表現を選ぶことになる。記憶領域と参照速度のどちらを取るかという交換条件が、この対比の要点である。
具体例
頂点A・B・Cで A→B と B→C の有向辺があるなら、A行B列とB行C列だけが1になる。全点間の最短経路を求めるワーシャル・フロイド法は、この行列を3重ループで更新していく解法で、隣接行列表現であることが前提になる。
試験での引っ掛け
無向グラフでは対角線について対称になるが、有向グラフでは対称にならない点が狙われる。対角成分が1になるのは自己ループがある場合だけ。辺の数が頂点数に比べて少ないほど隣接リストが有利で、n²の領域を無条件に良しとしない。
関連用語
出た過去問
出典：平成29年度 秋期 応用情報技術者試験 午前 問6（IPA）
ノード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年度 春期 応用情報技術者試験 午前 問3（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本を過不足なく描いたものが正解である。
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。