第三十节-图的表示
2018-12-10 本文已影响20人
wean_a23e
邻接矩阵存储方法
图最直观的一种存储方法就是，邻接矩阵 (Adjacency Matrix)。邻接矩阵的底层依赖一个二维数组。
对于无向图来说，如果顶点 i 和 j 之间有边，我们就将 A[i][j] 和 A[j][i] 标记为 1；对于有向图来说，如果顶点 i 到顶点 j 之间，有一条箭头从顶点 i 指向顶点 j 的边，我们就将 A[i][j] 标记为 1。同理，如果有一条箭头从顶点 j 指向顶点 i 的边，我们就将 A[j][i] 标记为 1。对于带权图，数组中存储的就是相应的权重。
邻接矩阵存储法的优点是，直观，简单，可以利用 CPU 的缓存机制。缺点是，浪费空间。
对于无向图来说，一条边要重复存储两个位置，浪费了一半空间。对于稀疏图来说，，很多顶点之间并没有联系，他们相关的边的标记位的空间就浪费了。
但邻接矩阵简单的存储方式也使得在此基础上的算法都实现起来比较简单。比如：
- 获取两个顶点间的关系，直接按数组下标就可以获得，非常迅速。
- 用弗洛伊德算法求最短路径，只要利用矩阵相乘若干次即可得到结果。
邻接表存储方法
邻接表 (Adjacency List) 最简单的实现方式如下：
如图可以看到，每个顶点对应一条链表，链表中存储的是这个顶点出发的边。
与邻接矩阵相反，邻接表存储起来比较节省空间，但是计算起来比较耗时。不过有办法对邻接表进行优化。
常见的邻接表存储方式的优化操作有：
- 如果链表过长，可以进行“树化”。
- 如果有按顺序查找某一顶点相关顶点的需求。比如按拼音首字母分页查找微博粉丝列表，就可以选择将链表改装成跳表。
- 也可以将链表改装成动态数组，这样就可以合理利用 cpu 的缓存，也可以应用二分查找算法进行高效查找。
- 还可以将链表改装成哈希表，在常数时间内获取是否两个顶点之间有相关关系。
如何存储微博用户关系？
数据结构是为特定算法服务的，具体选择那种储存方法，与期望支持的操作有关系。假设针对微博用户关系，假设我们需要支持以下操作：
- 判断用户 A 是否关注了用户 B
- 判断用户 A 是否是用户 B 的粉丝
- 用户 A 关注用户 B
- 用户 A 取消关注用户 B
- 根据用户名称首字母排序，分页获取用户的粉丝列表
- 根据用户名称首字母排序，分页获取用户的关注列表
- 那在存储方式上，因为社交网络是一张稀疏图，所以我们选择用邻接表来存储。
- 因为要查询用户被关注的列表，仅用邻接图是非常浪费效率的，所以我们再增加一张逆邻接图，存储用户的被关注关系。加快获取粉丝列表的速度。
- 基础的邻接表查找一个用户是否在另一个用户的关注列表中，速度不够快，所以我们选择对邻接表进行优化。
- 因为要按首字母排序获取用户的关注列表，所以我们选择用跳表来代替邻接表中的链表。
- 假设用户规模比较大，一台机器装不下一整个表，我们可以用哈希分片的方式在不同的机器上存储这个表。
- 假设表的大小需要扩容，可以把哈希分片方式升级为一致性哈希分片。
假设数据需要持久性保存，可以用关系数据库保存。并在表上建立索引。
假设数据海量，可以使用专业的图数据库。
