图的表示

复习

• 优先队列：每次取出最值
• 字典树（进阶）：字典树按字符逐层组织字符串
• 图：由节点和边组成

TL;DR

• 邻接矩阵用二维表表示边，查询快但费空间
• 邻接表为每个节点保存邻居列表，省空间
• 稠密图适合矩阵，稀疏图适合邻接表
• 选哪种表示，是典型的时空权衡

正文

　　图在纸上画着直观，可要存进计算机，就得选一种表示方式。常见的有两种，各有性格。

邻接矩阵：一张二维表

　　邻接矩阵（adjacency matrix）用一个二维表格来表示：

• 行和列都对应各个节点
• 第 i 行第 j 列的值，表示“节点 i 和节点 j 之间有没有边”（有则记为 1 或权重，没有记为 0）

　　它的优点是判断“两点之间有没有边”极快，一步查表，O(1)。

　　但代价是空间：一个 n 个节点的图，要开一张 n × n 的表。哪怕边很少，表格依然要占满 O(n²) 的空间，其中大部分格子还是 0。

邻接表：每个节点记一串邻居

　　邻接表（adjacency list）换个思路：为每个节点维护一个列表，里面记录它的所有邻居。

　　它的空间只用 O(n + e)（e 是边的数量），非常节省——毕竟只存“真的有边”的那些关系。遍历一个节点的所有邻居也很方便。

　　代价是：想知道“某两个具体节点之间有没有边”，得去那个节点的邻居列表里找，不如矩阵一步到位。

按图的“疏密”来选

　　选哪种，主要看图有多“密”：

• 稠密图（边多，接近 n²）：邻接矩阵不吃亏，还查询快
• 稀疏图（边远少于 n²）：邻接表省下大量空间，明显更优

　　现实中的图大多是稀疏的。比如社交网络：几十亿人，每个人却只认识几百个，绝不可能两两都有边。所以邻接表在实践中用得更多。

　　这又是那句老话：用空间换时间，还是用时间省空间，取决于你的数据长什么样。 同一个图，不同的表示，适合不同的操作和规模。

思考题 1

　　邻接矩阵和邻接表，各适合什么样的图？

思考题 2

　　为什么说“选择图的表示方式”是一种时空权衡？

小结

知识点

• 邻接矩阵用二维表表示边，查边 O(1)，空间 O(n²)
• 邻接表用邻居列表表示，空间 O(n + e)
• 稠密图适合矩阵，稀疏图适合邻接表
• 表示方式的选择是时空权衡

参考资料

1. Wikipedia(zh)：邻接矩阵：用二维数组表示图的边
2. Wikipedia(zh)：邻接表：用列表表示每个顶点的邻居

思考题答案（仅供参考）

思考题 1

　　邻接矩阵适合稠密图：边多时空间浪费不严重，且查询两点是否有边是 O(1)。邻接表适合稀疏图：只存储实际存在的边，空间开销小，遍历邻居也方便。

思考题 2

　　因为邻接矩阵用更多空间（O(n²)）换来了查边的 O(1) 速度；邻接表用更少空间（O(n+e)）换取了查单个边稍慢的代价。两者是在空间与时间之间做不同的取舍，选哪种取决于图的疏密和常用操作。

协议

　　本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

封面图

设计师 | 南国微雪