グラフをどのように表現しますか：隣接リスト対隣接行列？

Question

Accepted Answer

**グラフ**は**頂点**が**辺**で接続された集合です。2つの標準的な表現は、**隣接リスト**（各頂点がその隣接頂点を保存）と**隣接行列**（V×Vのブール値グリッド）です。選択はグラフの**密度**に依存します。

## 2つの形式

```text
Graph:  0 - 1
        |   |
        2 - 3

Adjacency list:          Adjacency matrix:
0: [1, 2]                    0 1 2 3
1: [0, 3]                 0 [0 1 1 0]
2: [0, 3]                 1 [1 0 0 1]
3: [1, 2]                 2 [1 0 0 1]
                          3 [0 1 1 0]
```

## Code

```python
# Adjacency list (dict of lists) — preferred for sparse graphs
adj = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}
neighbors = adj[1]            # O(1) to get a vertex's neighbors

# Adjacency matrix
matrix = [[0]*4 for _ in range(4)]
matrix[0][1] = matrix[1][0] = 1
has_edge = matrix[0][1] == 1  # O(1) edge lookup
```

## 比較（V個の頂点、E個の辺）

| | 隣接リスト | 隣接行列 |
|---|---|---|
| 空間 | O(V + E) | O(V²) |
| 辺が存在するか？ | O(次数) | O(1) |
| 隣接頂点を反復 | O(次数) | O(V) |
| 最適 | 疎グラフ | 密グラフ |

## なぜ重要なのか

ほとんどの実世界のグラフ（ソーシャルネットワーク、道路地図、依存グラフ）は**疎**であるため、隣接リストは膨大なメモリを節約し、BFS/DFSなどの走査を高速化します。

このトレードオフを理解することで、グラフアルゴリズムを効率的に保つ表現を選択でき、誤ってO(V²)のメモリを使用することを避けられます。

	隣接リスト	隣接行列
空間	O(V + E)	O(V²)
辺が存在するか？	O(次数)	O(1)
隣接頂点を反復	O(次数)	O(V)
最適	疎グラフ	密グラフ