隣接行列とは？りんせつぎょうれつ
隣接行列とは、グラフを頂点数n×nの2次元配列で表す方法。行iと列jの要素に、頂点iから頂点jへの辺の有無（1／0）や重みを入れる。2頂点間に辺があるかを一手で判定できる一方、記憶領域はn²必要で、辺が少ない網では空欄ばかりになる。経路計算の入力としてそのまま使える形である。
最終更新：2026-10-06
ネットワークSPを最短で暗記・合格する →背景
経路を計算する前に、網の形を計算機が扱える形へ置き換えなければならない。行と列の交点に重みを置く表現は、添字を指定するだけで隣接関係を引けるので、行列演算や最短経路の計算をそのまま当てはめられる。ただし網は一般に1台あたり数本しかリンクを持たない疎な形になるため、規模が大きくなると表現の選び方自体が性能を左右する。
具体例
OSPFの同一エリア内の各ルータは、集めたリンク情報から同じ網の地図を組み立て、そこにダイクストラ法を当てて最短経路木を求める。地図を行列で持てば重みの参照は即座だが、数百台規模では隣接リストのほうが領域も走査量も少なくて済む。
試験での引っ掛け
無向グラフでは対称行列になるが、有向グラフでは対称にならない点が狙われる。対角成分が1になるのは自己ループがある場合だけで、通常は0。上りと下りでコストが違うリンクは、図の上では1本に見えても行列としては非対称になる。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。