图的邻接矩阵与邻接表：时间与空间复杂度分析

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²)

✅ 推荐使用场景：

邻接矩阵： 图稠密，频繁查询边是否存在

邻接表： 图稀疏，内存敏感，主要操作为遍历邻接点

选择合适的图表示方式，可以显著提升算法性能。在实际开发中，建议根据图的密度和操作类型进行权衡。

500万人研究揭示基因与身高关系
怎么画短袖