グラフの隣接行列表現
グラフを隣接行列として表現する方法を学びます。空間計算量、辺の検索時間、隣接リストよりも行列が効率的な場合を理解します。
Graph Representations
詳細な説明
隣接行列
隣接行列は2D配列で、行i、列jのエントリがノードiからノードjへの辺の有無（およびオプションで重み）を示します。
構造
V個のノードを持つグラフの場合、行列はV × Vです：
- 無向グラフ: 行列は対称（M[i][j] = M[j][i]）
- 有向グラフ: 行列は非対称の場合がある
- 重み付きグラフ: 1の代わりに重みを格納、辺なしは0または∞
時間計算量
| 操作 | 時間 |
|---|---|
| 辺の存在確認 | O(1) |
| 辺の追加/削除 | O(1) |
| すべての隣接ノード | O(V) |
| 空間 | O(V²) |
利点
- 定数時間の辺検索 — M[i][j]を直接確認
- シンプルな実装 — 2D配列のみ
- 行列演算 — 隣接行列のk乗が長さkのパス数を示す
欠点
- 疎なグラフでもO(V²)の空間（ほとんどのエントリがゼロ）
- 隣接ノードの反復にO(V) — 行全体をスキャンする必要がある
使用場面
隣接行列はEがV²に近い密なグラフ、または頻繁なO(1)辺存在確認が必要な場合に最適です。
ユースケース
隣接行列は、行列の乗算や固有値計算がグラフの構造的特性を明らかにする数学的グラフ分析で使用されます。密なネットワークシミュレーション、画像処理（ピクセル隣接）、Floyd-Warshallのようなすべてのノードペアを系統的に調べるアルゴリズムで一般的です。