你如何表示一个图：邻接表 vs 邻接矩阵？

Question

Accepted Answer

一个**图**是由**顶点**通过**边**连接的集合。两种标准表示方法是**邻接表**（每个顶点存储其邻居）和**邻接矩阵**（一个 V×V 的布尔值网格）。选择取决于图的**密度**。

## 两种形式

```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(degree) | O(1) |
| 遍历邻居 | O(degree) | O(V) |
| 最适合 | 稀疏图 | 稠密图 |

## 为什么这很重要

大多数现实世界的图（社交网络、道路图、依赖图）都是**稀疏的**，因此邻接表可以节省大量空间并加快 BFS/DFS 等遍历的速度。

了解这种权衡可以帮助你选择能让图算法保持高效的表示方法，而不是不小心使用 O(V²) 的内存。

	邻接表	邻接矩阵
空间	O(V + E)	O(V²)
边存在?	O(degree)	O(1)
遍历邻居	O(degree)	O(V)
最适合	稀疏图	稠密图