图的表示

作者: seniusen | 来源:发表于2018-11-30 13:52 被阅读58次

1. 如何理解 “图”

图由顶点（vertex）和边（edge）组成，顶点之间通过边来建立一种联系。

生活中有很多符合图结构的例子，比如社交网络，就是一个非常典型的图结构。在微信中，每个用户可以看作是一个顶点，如果两个用户互为好友，那就在这两个顶点之间建立一条边。一个用户的好友数量，也就是和这个顶点相连接的边的个数，称为这个顶点的度（degree）。

在微博中，还允许单向关注，也就是说用户 A 关注了 B，但用户 B 可以不关注用户 A。对此，我们引入边的 “方向” 这个概念。用户 A 关注了用户 B，我们就用一条从 A 到 B 的带箭头的边来表示。反之，用户 B 关注了用户 A，我们就用一条从 B 到 A 的带箭头的边来表示。这种有方向的图称为 “有向图”，反之则称为 “无向图”。

在有向图中，我们将指向这个顶点的所有边的数量叫作入度（In-degree），以这个顶点为起点而指向其他顶点的所有边的数量叫作出度（Out-degree）。在微博中，入度就是粉丝数量，出度就是关注数量。

另外，在 QQ 中，两个用户之间的亲密度则是通过带权图（weighted graph）来表示的。所谓带权图，就是每条边都有一个权重，这个权重大小就可以作为两个用户之间的亲密度的度量。

2. 邻接矩阵存储方法

图最直观的一种存储方法，就是邻接矩阵（Adjacency Matrix）。

邻接矩阵其实就是一个二维数组。对于无向图，如果顶点 i 和顶点 j 之间有边，那么 A[i][j] 和 A[j][i] 就等于 1。对于有向图，如果边从顶点 i 指向顶点 j ，那么 A[i][j] 就等于 1，如果边从顶点 j 指向顶点 i ，那么 A[j][i] 就等于 1。而对于带权图，数组中存储的就是对应边的权重。

用邻接矩阵来表示图非常简单、直观，但是比较浪费内存空间。

对无向图来说， A[i][j] 和 A[j][i] 始终是相同的，邻接矩阵是一个对称矩阵，只需要一半空间就可以了。

另外，如果存储的是稀疏图（Sparse Graph），也就是顶点非常多，但每个顶点的边并不多，那邻接矩阵就更加浪费空间了。比如，微信有几亿用户，但每个用户的好友却不会很多。

邻接矩阵的优点就是简单、直接，因为是基于数组存储，因此获取两个顶点的关系就非常高效。而且，将图存储为邻接矩阵，还可以将很多图的运算转换为矩阵之间的运算，计算非常方便。

3. 邻接表存储方法

由于邻接矩阵比较浪费内存，我们提出了另一种图的存储方法——邻接表（Adjacency List）。

邻接表有点类似于散列表，每个顶点对应一个链表，链表中存储的是与这个顶点相连接的其它顶点。

邻接矩阵存储起来比较浪费空间，但是使用起来比较节省时间；邻接表虽然存储起来比较节省空间，但使用起来就会比较耗时。比如，我们要在邻接表中查找两个顶点之间是否有相连接的边，就要去其中一个顶点对应的链表中查询是否存在另一个顶点。其实，一切都是以时间来换空间的。

此外，我们还可以对链表进行一些改进升级，比如替换成平衡二叉查找树、跳表、散列表或者是有序动态数组等，来快速查找两个顶点之间是否存在边。

4. 微信微博是怎么存储好友关系的？

微信是无向图，微博是有向图，但二者的解决思路是差不多的，我们拿微博来举例说明。针对微博用户，假设我们需要支持以下这几个操作：

判断用户 A 是否关注了用户 B；
判断用户 A 是否是用户 B 的粉丝；
用户 A 关注用户 B；
用户 A 取消关注用户 B；
根据用户名称的首字母排序，分页获取用户的粉丝列表；
根据用户名称的首字母排序，分页获取用户的关注列表；

因为社交网络是一张稀疏图，因此我们选取邻接表来存储。但是邻接表只能知道某一个用户关注了哪些用户，而不能知道哪些用户关注了他。因此，我们需要一个逆邻接表来表示用户的被关注情况。逆邻接表中，每个顶点的链表存储的是以哪个顶点开始的边指向了这个顶点。

基础的邻接表不适合快速判断两个用户是否是关注与被关注的关系，我们需要对链表进行改进。因为我们需要按照用户名称的首字母排序，分页获取用户的粉丝列表和关注列表，这时候，用跳表这种结构就再合适不过了。跳表插入、删除、查找的时间复杂度都是 $O(logn)$ ，空间复杂度稍高，为 $O(n)$ ，但是跳表中的数据本来就是有序的了，分页获取粉丝列表或者关注列表，就非常高效。