隣接行列とは？りんせつぎょうれつ
隣接行列とは、グラフを頂点数n×nの2次元配列で表し、行iと列jの要素に頂点iから頂点jへの辺の有無や重みを入れる表現。2頂点が繋がっているかを一定の手数で判定できる代わりに、記憶領域が頂点数の2乗必要で、辺の少ないグラフでは空欄ばかりになる。
最終更新：2026-10-06
情報処理安全確保支援士を最短で暗記・合格する →背景
グラフを扱う処理は「この2点は繋がっているか」を何度も問い合わせる。辺を並べただけの表現では毎回探し直しになり、経路探索のような繰り返しの多い処理には耐えない。問い合わせの速さを記憶領域と引き換えに買う表現が隣接行列で、辺が疎なら隣接リスト、密なら隣接行列という選び分けが定石になった。
具体例
頂点A・B・CでA→B、B→Cの有向辺があるなら、A行B列とB行C列だけが1になる。無向グラフでは辺が双方向なので行列は対角線について対称になり、重み付きグラフなら1の代わりに距離や帯域を入れる。
試験での引っ掛け
無向グラフでは対称行列になるが、有向グラフでは対称にならない点が狙われる。対角成分が1になるのは自己ループがある場合だけで、通常は0。記憶領域は辺の数ではなく頂点数の2乗で効くという、隣接リストとの違いも取り違えやすい。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。