グラフの隣接リスト表現
隣接リストが疎なネットワークでグラフを効率的に表現する方法を理解します。データ構造、メモリ使用量、探索パフォーマンス、隣接行列との比較を学びます。
Graph Representations
詳細な説明
隣接リスト
隣接リストは、各ノードについて隣接ノードのリスト（およびオプションで辺の重み）を格納します。ほとんどの実世界のグラフは疎であるため、実際に最も一般的なグラフ表現です。
構造
各ノードが接続されたノードのリストにマッピングされます：
A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C]
時間計算量
| 操作 | 時間 |
|---|---|
| 辺の存在確認 | O(次数) |
| 辺の追加 | O(1) |
| 辺の削除 | O(次数) |
| すべての隣接ノード | O(次数) |
| 空間 | O(V + E) |
利点
- 疎なグラフで空間効率が良い — O(V + E) vs O(V²)
- 高速な隣接ノード反復 — 実際の隣接ノードのみを訪問
- BFS/DFSに自然 — 探索アルゴリズムが隣接ノードを直接反復
比較
| 隣接行列 | 隣接リスト | |
|---|---|---|
| 空間 | O(V²) | O(V + E) |
| 辺確認 | O(1) | O(次数) |
| 隣接ノード | O(V) | O(次数) |
| 最適 | 密なグラフ | 疎なグラフ |
ユースケース
隣接リストはソフトウェアエンジニアリングでグラフを表現するデフォルトの選択です。SNSバックエンド、パッケージマネージャ、Webクローラー、競技プログラミングやコーディング面接のほぼすべてのグラフアルゴリズム実装で使用されています。