adjacency matrix

adjacency matrix（隣接行列）は、グラフ理論においてネットワークの構造を数学的に表現するための最も基本的な手法の一つです。頂点間の接続関係を０と１の二値で表現するため、コンピューターによる処理と非常に相性が良く、アルゴリズムの実装に広く利用されています。

計算効率とメモリのトレードオフ

隣接行列は、特定の２つの頂点が隣接しているかを確認する操作を非常に高速に行えるという利点があります。しかし、頂点の数に対してエッジ（辺）の数が少ない疎なグラフの場合、行列の大部分が０で埋まってしまい、メモリ空間を無駄に消費するという欠点があります。そのため、大規模なネットワークを扱う際は、adjacency list（隣接リスト）などのより効率的なデータ構造が検討されます。

有向グラフと無向グラフでの挙動

グラフの種類によって、行列の性質が異なります。

無向グラフの場合：辺に方向がないため、行列は対角線に対して対称になります。つまり、頂点ＡからＢへの接続があれば、必ずＢからＡへの接続も存在します。
有向グラフの場合：辺に方向があるため、行列は必ずしも対称にはなりません。これにより、どちらの頂点からどちらへ向かっているかという方向性を厳密に管理することが可能です。