1. 概述
在图算法中，图的表示方式直接影响算法的性能。常见的图表示方法有两种：邻接矩阵（Adjacency Matrix） 和 邻接表（Adjacency List）。它们在时间和空间复杂度上各有优劣。
选择哪种表示方式，取决于图的结构以及具体的应用场景。本文将从时间和空间复杂度角度对比这两种表示方法，帮助你在不同场景下做出更优的选择。
2. 图的基本结构
图由一组顶点 V 和边 E 构成。边是顶点对，表示为 
。若图为无向图，则边是双向的，即 
。
以下是一个示例无向图：
该图包含 5 个顶点和 6 条边。
3. 邻接矩阵
3.1 定义与结构
邻接矩阵是一个大小为 
的二维数组，其中每个元素表示两个顶点之间是否存在边。对于无向图，邻接矩阵是对称的。
3.2 示例
下图是上述示例图的邻接矩阵表示：
矩阵中对角线为 0，其余 1 表示存在边。
3.3 时间与空间复杂度
- 空间复杂度：
- 构建时间复杂度：
3.4 优缺点
✅ 优点：
- 判断两个顶点是否有边：O(1) 时间复杂度
❌ 缺点：
- 占用空间大，尤其在稀疏图中浪费严重
4. 邻接表
4.1 定义与结构
邻接表使用一个数组或列表，每个元素是一个链表，存储与该顶点相连的所有顶点。
4.2 示例
下图是示例图的邻接表表示：
4.3 时间与空间复杂度
- 空间复杂度：
- 构建时间复杂度：
在完全图中退化为
4.4 优缺点
✅ 优点：
- 节省空间，尤其适合稀疏图
❌ 缺点：
- 判断两个顶点是否相连：O(n) 时间复杂度
5. 删除操作的复杂度比较
5.1 删除顶点
| 表示方式 | 时间复杂度 |
|---|---|
| 邻接矩阵 | ✅ O(n) |
| 邻接表 | ❌ O(n²) |
邻接矩阵只需将该顶点所在行和列清零即可；邻接表需要遍历所有邻接链表，删除所有相关边。
5.2 删除边
| 表示方式 | 时间复杂度 |
|---|---|
| 邻接矩阵 | ✅ O(1) |
| 邻接表 | ❌ O(n) |
邻接矩阵直接定位到对应位置设为 0；邻接表需要遍历链表删除节点。
6. 总结
| 特性 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 空间复杂度 | ✅ O(n²) | ✅ O(n + m) |
| 判断边存在 | ✅ O(1) | ❌ O(n) |
| 添加/删除边 | ✅ O(1) | ❌ O(n) |
| 添加/删除顶点 | ✅ O(n) | ❌ O(n²) |
✅ 推荐使用场景：
- 邻接矩阵： 图稠密，频繁查询边是否存在
- 邻接表： 图稀疏，内存敏感，主要操作为遍历邻接点
选择合适的图表示方式，可以显著提升算法性能。在实际开发中，建议根据图的密度和操作类型进行权衡。