图的表示

图的表示

图的常用表示方式包括**“邻接矩阵”和“邻接表”**。以下使用无向图进行举例。

（1）邻接矩阵

设图的顶点数量为 n ，「邻接矩阵 adjacency matrix」使用一个 n×n 大小的矩阵来表示图，每一行（列）代表一个顶点，矩阵元素代表边，用 1 或 0 表示两个顶点之间是否存在边。 如图所示，设邻接矩阵为M、顶点列表为 V ，那么矩阵元素 M[i, j]=1 表示顶点 V[i] 到顶点 V[j] 之间存在边，反之 M[i, j]=0 表示两顶点之间无边。

邻接矩阵具有以下特性。

• 顶点不能与自身相连，因此邻接矩阵主对角线元素没有意义。
• 对于无向图，两个方向的边等价，此时邻接矩阵关于主对角线对称。
• 将邻接矩阵的元素从 1 和 0 替换为权重，则可表示有权图。

使用邻接矩阵表示图时，我们可以直接访问矩阵元素以获取边，因此增删查改操作的效率很高，时间复杂度均为 O(1) 。然而，矩阵的空间复杂度为$O(N^2)$，内存占用较多。

（2）邻接表

「邻接表 adjacency list」使用 n 个链表来表示图，链表节点表示顶点。第 i 个链表对应顶点 i ，其中存储了该顶点的所有邻接顶点（与该顶点相连的顶点）。图展示了一个使用邻接表存储的图的示例。

邻接表仅存储实际存在的边，而边的总数通常远小于 $n^2$，因此它更加节省空间。然而，在邻接表中需要通过遍历链表来查找边，因此其时间效率不如邻接矩阵。

观察图，邻接表结构与哈希表中的“链式地址”非常相似，因此我们也可以采用类似的方法来优化效率。比如当链表较长时，可以将链表转化为 AVL 树或红黑树，从而将时间效率从 O(n) 优化至 O(log⁡n) ；还可以把链表转换为哈希表，从而将时间复杂度降至 O(1) 。

（3）应用

许多现实系统可以用图来建模，相应的问题也可以约化为图计算问题。

	顶点	边	图计算问题
社交网络	用户	好友关系	潜在好友推荐
地铁线路	站点	站点间的连通性	最短路线推荐
太阳系	星体	星体间的万有引力作用	行星轨道计算
解决 Top K 问题
获取数据流中位数