隣接行列（Adjacency Matrix）
グラフのノード間の接続関係を行列で表したもの
📌隣接行列とは
隣接行列（Adjacency Matrix）とは、グラフのノード間のつながり（隣接関係）を、0 と 1 を並べた表（行列）で表したものです。行と列にすべてのノードを並べ、「行のノードから列のノードへ辺があるか」を 1（あり）か 0（なし）で書き込みます。
身近な例で言うと、出席確認の表に似ています。縦に「自分」、横に「相手」を並べ、つながりがあるマスに○（=1）、なければ空欄（=0）を書く感覚です。グラフを文章や絵ではなく、コンピュータが扱いやすい数値の格子に変換したものと考えてください。
上のツールでプリセットを切り替えると、左のグラフに対応する隣接行列が右にリアルタイム生成されます。行列のマスや辺にカーソルを合わせると、グラフと行列の対応する部分が同時に光ります。
🔁グラフと行列の対応
グラフと行列は次のように1対1で対応します。
・行（横の並び）：辺の「出発点」となるノード
・列（縦の並び）：辺の「到着点」となるノード
・マスの値 1：そのマスの行→列に辺がある
・マスの値 0：辺がない
重要な性質として、無向グラフの隣接行列は必ず対角線で対称になります。「A—B」という線は「A→B」かつ「B→A」を意味するため、A[i][j] と A[j][i] が同じ値になるからです。一方、有向グラフでは矢印に向きがあるため対称になるとは限りません。
また、対角成分 A[i][i] は「自分自身への辺（自己ループ）」を表します。通常は 0 ですが、プリセット「自己ループを含む有向グラフ」のように自分へ向かう矢印があると 1 になります。
🛠️用途(経路探索の高速化)
隣接行列の最大の利点は「2つのノードがつながっているかを一瞬で判定できる」ことです。A[i][j] のマスを見るだけで辺の有無が分かるため、計算時間は O(1)（一定）です。
主な用途は次のとおりです。
・経路探索の高速化：ダイクストラ法やワーシャル・フロイド法など、辺の有無を何度も調べるアルゴリズムで威力を発揮
・行列の累乗で到達判定：行列を2乗すると「2ステップで行ける経路の数」が求まる便利な性質がある
・密なグラフの管理：辺が多いグラフではコンパクトに扱える
ただし注意点もあります。ノード数 n に対して n × n のマスが必要なので、ノードが多く辺が少ない（疎な）グラフではメモリの無駄が大きくなります。その場合は、各ノードのつながり先だけをリストで持つ隣接リストのほうが省メモリです。「密なら隣接行列・疎なら隣接リスト」という使い分けが基本です。
