1、30|图的表示：如何存储微博、微信等社交网络中的好友关系？ file:/F/temp/geektime/数据结构与算法之美/30图的表示：如何存储微博、微信等社交网络中的好友关系？.html2019/1/15 15:36:06 30|图的表示：如何存储微博、微信等社交网络中的好友关系？ 微博、微信、LinkedIn这些社交软件我想你肯定都玩过吧。在微博中，两个人可以互相关注；在微信中，两个人可以互加好友。那你知道，如何存储微博、微信等 这些社交网络的好友关系吗？ 这就要用到我们今天要讲的这种数据结构：图。实际上，涉及图的算法有很多，也非常复杂，比如图的搜索、最短路径、最小生成树、二分图等等。我
2、们今天聚 焦在图存储这一方面，后面会分好几节来依次讲解图相关的算法。 如何理解“图”？ 我们前面讲过了树这种非线性表数据结构，今天我们要讲另一种非线性表数据结构，图（Graph）。和树比起来，这是一种更加复杂的非线性表结构。 我们知道，树中的元素我们称为节点，图中的元素我们就叫作顶点（vertex）。从我画的图中可以看出来，图中的一个顶点可以与任意其他顶点建立连接关系。我 们把这种建立的关系叫作边（edge）。 我们生活中就有很多符合图这种结构的例子。比如，开篇问题中讲到的社交网络，就是一个非常典型的图结构。 我们就拿微信举例子吧。我们可以把每个用户看作一个顶点。如果两个用户之间互加好友，那就
3、在两者之间建立一条边。所以，整个微信的好友关系就可以用一 30|图的表示：如何存储微博、微信等社交网络中的好友关系？ file:/F/temp/geektime/数据结构与算法之美/30图的表示：如何存储微博、微信等社交网络中的好友关系？.html2019/1/15 15:36:06 张图来表示。其中，每个用户有多少个好友，对应到图中，就叫作顶点的度（degree），就是跟顶点相连接的边的条数。 实际上，微博的社交关系跟微信还有点不一样，或者说更加复杂一点。微博允许单向关注，也就是说，用户A关注了用户B，但用户B可以不关注用户A。那我们如 何用图来表示这种单向的社交关系呢？ 我们可以把刚刚讲的
4、图结构稍微改造一下，引入边的“方向”的概念。 如果用户A关注了用户B，我们就在图中画一条从A到B的带箭头的边，来表示边的方向。如果用户A和用户B互相关注了，那我们就画一条从A指向B的边，再画一 条从B指向A的边。我们把这种边有方向的图叫作“有向图”。以此类推，我们把边没有方向的图就叫作“无向图”。 我们刚刚讲过，无向图中有“度”这个概念，表示一个顶点有多少条边。在有向图中，我们把度分为入度（In-degree）和出度（Out-degree）。 顶点的入度，表示有多少条边指向这个顶点；顶点的出度，表示有多少条边是以这个顶点为起点指向其他顶点。对应到微博的例子，入度就表示有多少粉丝，出 度就表示关
5、注了多少人。 前面讲到了微信、微博、无向图、有向图，现在我们再来看另一种社交软件：QQ。 QQ中的社交关系要更复杂的一点。不知道你有没有留意过QQ亲密度这样一个功能。QQ不仅记录了用户之间的好友关系，还记录了两个用户之间的亲密度，如果 两个用户经常往来，那亲密度就比较高；如果不经常往来，亲密度就比较低。如何在图中记录这种好友关系的亲密度呢？ 30|图的表示：如何存储微博、微信等社交网络中的好友关系？ file:/F/temp/geektime/数据结构与算法之美/30图的表示：如何存储微博、微信等社交网络中的好友关系？.html2019/1/15 15:36:06 这里就要用到另一种图，带权图
6、（weighted graph）。在带权图中，每条边都有一个权重（weight），我们可以通过这个权重来表示QQ好友间的亲密度。 关于图的概念比较多，我今天也只是介绍了几个常用的，理解起来都不复杂，不知道你都掌握了没有？掌握了图的概念之后，我们再来看下，如何在内存中存储 图这种数据结构呢？ 邻接矩阵存储方法 图最直观的一种存储方法就是，邻接矩阵（Adjacency Matrix）。 邻接矩阵的底层依赖一个二维数组。对于无向图来说，如果顶点i与顶点j之间有边，我们就将Aij和Aji标记为1；对于有向图来说，如果顶点i到顶点j之间，有 一条箭头从顶点i指向顶点j的边，那我们就将Aij标记为1。同理
7、，如果有一条箭头从顶点j指向顶点i的边，我们就将Aji标记为1。对于带权图，数组中就存储 相应的权重。 30|图的表示：如何存储微博、微信等社交网络中的好友关系？ file:/F/temp/geektime/数据结构与算法之美/30图的表示：如何存储微博、微信等社交网络中的好友关系？.html2019/1/15 15:36:06 用邻接矩阵来表示一个图，虽然简单、直观，但是比较浪费存储空间。为什么这么说呢？ 对于无向图来说，如果Aij等于1，那Aji也肯定等于1。实际上，我们只需要存储一个就可以了。也就是说，无向图的二维数组中，如果我们将其用对角线划 分为上下两部分，那我们只需要利用上面或者下
8、面这样一半的空间就足够了，另外一半白白浪费掉了。 30|图的表示：如何存储微博、微信等社交网络中的好友关系？ file:/F/temp/geektime/数据结构与算法之美/30图的表示：如何存储微博、微信等社交网络中的好友关系？.html2019/1/15 15:36:06 还有，如果我们存储的是稀疏图（Sparse Matrix），也就是说，顶点很多，但每个顶点的边并不多，那邻接矩阵的存储方法就更加浪费空间了。比如微信有好几亿 的用户，对应到图上就是好几亿的顶点。但是每个用户的好友并不会很多，一般也就三五百个而已。如果我们用邻接矩阵来存储，那绝大部分的存储空间都被浪 费了。 但这也并不是说
9、，邻接矩阵的存储方法就完全没有优点。首先，邻接矩阵的存储方式简单、直接，因为基于数组，所以在获取两个顶点的关系时，就非常高效。 其次，用邻接矩阵存储图的另外一个好处是方便计算。这是因为，用邻接矩阵的方式存储图，可以将很多图的运算转换成矩阵之间的运算。比如求解最短路径问 题时会提到一个Floyd-Warshall算法，就是利用矩阵循环相乘若干次得到结果。 邻接表存储方法 针对上面邻接矩阵比较浪费内存空间的问题，我们来看另外一种图的存储方法，邻接表（Adjacency List）。 我画了一张邻接表的图，你可以先看下。乍一看，邻接表是不是有点像散列表？每个顶点对应一条链表，链表中存储的是与这个顶点
10、相连接的其他顶点。另外我 需要说明一下，图中画的是一个有向图的邻接表存储方式，每个顶点对应的链表里面，存储的是指向的顶点。对于无向图来说，也是类似的，不过，每个顶点的 链表中存储的，是跟这个顶点有边相连的顶点，你可以自己画下。 30|图的表示：如何存储微博、微信等社交网络中的好友关系？ file:/F/temp/geektime/数据结构与算法之美/30图的表示：如何存储微博、微信等社交网络中的好友关系？.html2019/1/15 15:36:06 还记得我们之前讲过的时间、空间复杂度互换的设计思想吗？邻接矩阵存储起来比较浪费空间，但是使用起来比较节省时间。相反，邻接表存储起来比较节省空 间
11、，但是使用起来就比较耗时间。 就像图中的例子，如果我们要确定，是否存在一条从顶点2到顶点4的边，那我们就要遍历顶点2对应的那条链表，看链表中是否存在顶点4。而且，我们前面也讲 过，链表的存储方式对缓存不友好。所以，比起邻接矩阵的存储方式，在邻接表中查询两个顶点之间的关系就没那么高效了。 在散列表那几节里，我讲到，在基于链表法解决冲突的散列表中，如果链过长，为了提高查找效率，我们可以将链表换成其他更加高效的数据结构，比如平衡二 叉查找树等。我们刚刚也讲到，邻接表长得很像散列。所以，我们也可以将邻接表同散列表一样进行“改进升级”。 我们可以将邻接表中的链表改成平衡二叉查找树。实际开发中，我们可以选
12、择用红黑树。这样，我们就可以更加快速地查找两个顶点之间是否存在边了。当然， 这里的二叉查找树可以换成其他动态数据结构，比如跳表、散列表等。除此之外，我们还可以将链表改成有序动态数组，可以通过二分查找的方法来快速定位两 个顶点之间否是存在边。 30|图的表示：如何存储微博、微信等社交网络中的好友关系？ file:/F/temp/geektime/数据结构与算法之美/30图的表示：如何存储微博、微信等社交网络中的好友关系？.html2019/1/15 15:36:06 解答开篇 有了前面讲的理论知识，现在我们回过头来看开篇的问题，如何存储微博、微信等社交网络中的好友关系？ 前面我们分析了，微博、微
13、信是两种“图”，前者是有向图，后者是无向图。在这个问题上，两者的解决思路差不多，所以我只拿微博来讲解。 数据结构是为算法服务的，所以具体选择哪种存储方法，与期望支持的操作有关系。针对微博用户关系，假设我们需要支持下面这样几个操作： 判断用户A是否关注了用户B； 判断用户A是否是用户B的粉丝； 用户A关注用户B； 用户A取消关注用户B； 根据用户名称的首字母排序，分页获取用户的粉丝列表； 根据用户名称的首字母排序，分页获取用户的关注列表。 关于如何存储一个图，前面我们讲到两种主要的存储方法，邻接矩阵和邻接表。因为社交网络是一张稀疏图，使用邻接矩阵存储比较浪费存储空间。所以，这里 我们采用邻接表来
14、存储。 不过，用一个邻接表来存储这种有向图是不够的。我们去查找某个用户关注了哪些用户非常容易，但是如果要想知道某个用户都被哪些用户关注了，也就是用户 的粉丝列表，是非常困难的。 基于此，我们需要一个逆邻接表。邻接表中存储了用户的关注关系，逆邻接表中存储的是用户的被关注关系。对应到图上，邻接表中，每个顶点的链表中，存储 的就是这个顶点指向的顶点，逆邻接表中，每个顶点的链表中，存储的是指向这个顶点的顶点。如果要查找某个用户关注了哪些用户，我们可以在邻接表中查 找；如果要查找某个用户被哪些用户关注了，我们从逆邻接表中查找。 30|图的表示：如何存储微博、微信等社交网络中的好友关系？ file:/F/
15、temp/geektime/数据结构与算法之美/30图的表示：如何存储微博、微信等社交网络中的好友关系？.html2019/1/15 15:36:06 基础的邻接表不适合快速判断两个用户之间是否是关注与被关注的关系，所以我们选择改进版本，将邻接表中的链表改为支持快速查找的动态数据结构。选择哪 种动态数据结构呢？红黑树、跳表、有序动态数组还是散列表呢？ 因为我们需要按照用户名称的首字母排序，分页来获取用户的粉丝列表或者关注列表，用跳表这种结构再合适不过了。这是因为，跳表插入、删除、查找都非常 高效，时间复杂度是O(logn)，空间复杂度上稍高，是O(n)。最重要的一点，跳表中存储的数据本来就是有
16、序的了，分页获取粉丝列表或关注列表，就非常高效。 如果对于小规模的数据，比如社交网络中只有几万、几十万个用户，我们可以将整个社交关系存储在内存中，上面的解决思路是没有问题的。但是如果像微博那 样有上亿的用户，数据规模太大，我们就无法全部存储在内存中了。这个时候该怎么办呢？ 我们可以通过哈希算法等数据分片方式，将邻接表存储在不同的机器上。你可以看下面这幅图，我们在机器1上存储顶点1，2，3的邻接表，在机器2上，存储顶 点4，5的邻接表。逆邻接表的处理方式也一样。当要查询顶点与顶点关系的时候，我们就利用同样的哈希算法，先定位顶点所在的机器，然后再在相应的机器上 查找。 30|图的表示：如何存储微博
17、、微信等社交网络中的好友关系？ file:/F/temp/geektime/数据结构与算法之美/30图的表示：如何存储微博、微信等社交网络中的好友关系？.html2019/1/15 15:36:06 除此之外，我们还有另外一种解决思路，就是利用外部存储（比如硬盘），因为外部存储的存储空间要比内存会宽裕很多。数据库是我们经常用来持久化存储关 30|图的表示：如何存储微博、微信等社交网络中的好友关系？ file:/F/temp/geektime/数据结构与算法之美/30图的表示：如何存储微博、微信等社交网络中的好友关系？.html2019/1/15 15:36:06 系数据的，所以我这里介绍一种数
18、据库的存储方式。 我用下面这张表来存储这样一个图。为了高效地支持前面定义的操作，我们可以在表上建立多个索引，比如第一列、第二列，给这两列都建立索引。 30|图的表示：如何存储微博、微信等社交网络中的好友关系？ file:/F/temp/geektime/数据结构与算法之美/30图的表示：如何存储微博、微信等社交网络中的好友关系？.html2019/1/15 15:36:06 30|图的表示：如何存储微博、微信等社交网络中的好友关系？ file:/F/temp/geektime/数据结构与算法之美/30图的表示：如何存储微博、微信等社交网络中的好友关系？.html2019/1/15 15:36:
19、06 内容小结 今天我们学习了图这种非线性表数据结构，关于图，你需要理解这样几个概念：无向图、有向图、带权图、顶点、边、度、入度、出度。除此之外，我们还学习 了图的两个主要的存储方式：邻接矩阵和邻接表。 邻接矩阵存储方法的缺点是比较浪费空间，但是优点是查询效率高，而且方便矩阵运算。邻接表存储方法中每个顶点都对应一个链表，存储与其相连接的其他顶 点。尽管邻接表的存储方式比较节省存储空间，但链表不方便查找，所以查询效率没有邻接矩阵存储方式高。针对这个问题，邻接表还有改进升级版，即将链表 换成更加高效的动态数据结构，比如平衡二叉查找树、跳表、散列表等。 课后思考 1. 关于开篇思考题，我们只讲了微博
20、这种有向图的解决思路，那像微信这种无向图，应该怎么存储呢？你可以照着我的思路，自己做一下练习。 2. 除了我今天举的社交网络可以用图来表示之外，符合图这种结构特点的例子还有很多，比如知识图谱（Knowledge Graph）。关于图这种数据结构，你还能想 到其他生活或者工作中的例子吗？ 欢迎留言和我分享，我会第一时间给你反馈。 30|图的表示：如何存储微博、微信等社交网络中的好友关系？ file:/F/temp/geektime/数据结构与算法之美/30图的表示：如何存储微博、微信等社交网络中的好友关系？.html2019/1/15 15:36:06 精选留言： 传说中的成大大 2018-11
21、-30 02:39:20 学了这么久的数据结构和算法，今天突然顿悟，基础的数据结构就是数组和链表， 而后面更加复杂的 树 队列 图 等等 都可以通过数组和链表等方式存储， 出现树 队列 图 等数据结构的原因 就是为了解决 部分问题处理过程中时间复杂度过高的问题， 所以数据结构就是为了算法而生的！ 尤其是学习了时间复杂 度过后 在工作和学习过程中 就应该分析自己的代码复杂度 以进行优化或者选择更好的数据结构和算法！这样才能写出更好的代码更好的解决问题 66赞 30|图的表示：如何存储微博、微信等社交网络中的好友关系？ file:/F/temp/geektime/数据结构与算法之美/30图的表示：
22、如何存储微博、微信等社交网络中的好友关系？.html2019/1/15 15:36:06 Jerry银银 2018-11-29 23:43:41 地图 网络 Gradle这个编译工具，内部组织task的方式用的是有向图 Android framework层提供了一个CoordinatorLayout，其内部协调子view的联动，也是用的图 15赞 作者回复2018-11-30 01:51:58 花见笑 2018-12-01 11:29:26 学到现在有一种特别明显的感受就是描述一种需求模型可以有很多种组合数据结构，而这些复杂数据结构都是基础数据结构组合起来的，而这些数据结构去 的选择又是基于需
23、求模型对时间和空间这两个维度来的，所以解决问题的关键是我们都需求的理解以及我们对数据结构的熟练运用。 9赞 黄金的太阳 2018-12-04 00:28:54 请教老师 解决现实问题的时候当存储图有多种选择，例如: 1.用邻接表自己存 2.关系型库 3.图数据库 那么这三种方式每一种的适用场景，优缺点分别是什么呢？该如何取舍 7赞 作者回复2018-12-04 01:35:03 1 内存中用临界表 2 要持久化存储就用数据库 2 超大图 并且涉及大量图计算。用专业的图数据库 五岳寻仙 2018-11-29 23:49:42 课后思考题： 1. 微信好友关系存储方式。无向图，也可以使用邻接表的方
24、式存储每个人所对应的好友列表。为了支持快速查找，好友列表可以使用红黑树存储。 2. 生活工作中应用图的例子。很多，互联网上网页之间通过超链接连接成一张有向图；城市乃至全国交通网络是一张加权图；人与人之间的人际关系够成一 张图，著名的六度分割理论据说就是基于这个得到的。 7赞 30|图的表示：如何存储微博、微信等社交网络中的好友关系？ file:/F/temp/geektime/数据结构与算法之美/30图的表示：如何存储微博、微信等社交网络中的好友关系？.html2019/1/15 15:36:06 作者回复2018-11-30 01:51:48 姜戈 2018-11-29 16:43:30 有
25、序动态数组能否讲解一下 7赞 作者回复2018-11-30 01:52:24 数据有序排列的动态数组 ppingfann 2018-11-30 07:30:34 微信社交关系的存储方式 因为顶点的数量大且关系相对少，所以不适合用邻接矩阵来存储，应该用邻接表来存储。 微信社交关系的相关操作：1. 判断A、B是否为好友关系 2. A删除B，断开与B的好友关系 3. 展示出A的所有好友，并按名称首字母进行排序 因为是无向图，所以我们仅需要一个邻接表就行了，然后将链表改造为跳表增加查找速度且在列出好友是会比较方便。最后，若有n台机器可供使用，那么 我们可以对n取余来划分这些数据到不同的机器上，毕竟微信
26、的用户量太大，一个机器的内存应该是不够用的。 5赞 鹏程万里 2018-12-03 06:30:10 判断用户 A 是否关注了用户 B； 判断用户 A 是否是用户B的粉丝。这两个操作我怎么觉得是一个意思呢？ 4赞 作者回复2018-12-04 01:54:16 好像是的 第二个应该是 判断a是否被b关注 汝林外史 2018-12-06 13:38:54 真心感谢王老师，以前看见数据结构和算法都直接略过，感觉很难啃直接就放弃了，不求甚解，经过这段时间得学习发现自己还是可以学的会的，而且也慢 慢喜欢看这些数据结构了，老师的功力真的很深厚！ 3赞 您的好友William 2018-11-30 03:
27、49:04 刚刚还在写Topology Sort，就是leetcode那个给课程先后顺序排列的题。我还知道社交Graph在推荐系统中应用非常广泛（腾讯的人亲口说这是他们很多产品 的最大亮点，因为可以做社交）。使用了social trust的推荐系统非常的robust且能够经受嬀鬀戀挀搀愀挀攀搀戀攀愀挀戀戀愀攀戀昀昀挀搀搀昀攀挀愀昀昀攀戀ef2e7e6d798ac369827df3ffb228faff0be86a8572ae1ee01dff19de0aa152d00;買=翾嬀鬀搀搀搀攀攀戀挀攀愀昀戀挀戀愀攀挀攀搀愀戀搀搀昀戀搀愀cd793f1a7be760d87b90f28e79e2cf056b
28、235909cf2b6bcfcaf6b624e3adbd210;貸=翾嬀鬀搀挀攀愀戀攀搀搀戀愀戀攀挀愀攀攀攀戀搀愀搀1cf96c2f7e7be8df3f7c19fc280b3d6af64e19f45be4d3dfe28acb01c4f142a50;貺=翾嬀鬀挀戀昀搀愀搀戀攀戀攀愀挀攀昀昀戀昀昀戀攀戀昀攀昀c8671f8ef622dc57c9d02cc7f8fb6d5c6d8d1cd8d140dc70a434be77abc845700;貼=翾嬀鬀攀攀愀攀愀昀搀戀攀挀戀搀搀攀搀搀搀昀挀挀挀搀戀挀攀39cb34a256a0cd49a2b58953d22d6167757d7157ec52d19de55
29、b10ead57ee4530;貾=翾嬀鬀昀挀搀昀挀挀攀戀挀挀挀挀愀挀搀戀愀昀戀挀挀愀愀ee391cd35afe62057c365a7774033b37c7467e31e78d60f0a467c6cb97352a4c0;賀=翾嬀鬀挀戀戀戀攀戀昀愀攀挀挀昀攀攀攀攀愀昀愀攀挀1823298bb6686e0eb671f6b213e5838c6ca12f02256868af43bef17b2c7559a30;賂=翾嬀鬀攀挀挀戀愀愀戀搀搀戀挀昀攀搀攀戀愀戀愀昀戀攀攀2b07eed37f52100836a4e92301a7ebd3f3fa5b027d60d92c9b72041f8c1abe770;賄=翾嬀鬀挀攀昀搀昀愀搀攀昀愀戀戀昀攀攀昀攀挀攀戀昀搀愀攀攀搀戀攀戀昀愀be67dedf345f67a594a97530f57132302fa3c1330fe6d11681da1729da858feb0;賆=翾嬀鬀挀戀搀昀攀愀昀昀攀攀愀愀戀戀攀挀戀搀愀搀挀挀戀戀攀愀搀4ac36f57e18647ac153322df895ffa0f5fbf3a902312b8857a09a967e385f3940;賈=翾嬀鬀攀挀昀挀昀昀挀戀愀挀昀戀攀愀戀戀搀昀搀6cc5b66caa804320c03bedb0e9c3eb3d8c8
个人主页