算法之美6 - 图

╰半夏微凉° 2022-03-01 16:20 214阅读 0赞

## 图 ##

图的存储、拓扑排序、最短路径、关键路径、最小生成树、二分图、最大流

--------------------

### 30 | 图的表示：如何存储微博、微信等社交网络中的好友关系？ ###

另一种非线性表数据结构，图

我们就拿微信举例子吧。我们可以把每个用户看作一个**顶点**。如果两个用户之间互加好友，那就在两者之间建立一条**边**。所以，整个微信的好友关系就可以用一张**图**来表示。其中，每个用户有多少个好友，对应到图中，就叫作顶点的**度**（degree），就是跟顶点相连接的边的条数。

微博的社交关系跟微信还有点不一样，或者说更加复杂一点。微博允许单向关注，也就是说，用户 A 关注了用户 B，但用户 B 可以不关注用户 A。那我们如何用图来表示这种单向的社交关系呢？

对应到微博的例子，**入度**就表示有多少粉丝，**出度**就表示关注了多少人。

前面讲到了微信、微博、无向图、有向图，现在我们再来看另一种社交软件：QQ。

带权图（weighted graph）。在带权图中，每条边都有一个权重（weight），我们可以通过这个**权重**来表示 QQ 好友间的亲密度。

> 邻接矩阵存储方法

![625e7493b5470e774b5aa91fb4fdb9d2.jpg][]

缺点

*  浪费存储空间
 *  稀疏图：也就是说，顶点很多，但每个顶点的边并不多，那邻接矩阵的存储方法就更加浪费空间了。

优点：

*  邻接矩阵的**存储方式简单**、直接，因为基于数组，所以在获取两个顶点的关系时，就非常高效。
 *  用邻接矩阵存储图的另外一个好处是**方便计算**。这是因为，用邻接矩阵的方式存储图，可以将很多图的运算转换成矩阵之间的运算。

> 邻接表存储方法

![039bc254b97bd11670cdc4bf2a8e1394.jpg][]

*  每个顶点对应一条链表，链表中存储的是与这个顶点相连接的其他顶点。
 *  有向图的邻接表存储方式，每个顶点对应的链表里面，存储的是指向的顶点。
 *  对于无向图来说，每个顶点的链表中存储的，是跟这个顶点有边相连的顶点。

> 邻接矩阵与邻接表

*  邻接矩阵存储起来比较浪费空间，但是使用起来比较节省时间。相反，邻接表存储起来比较节省空间，但是使用起来就比较耗时间。
 *  链表的存储方式对缓存不友好。所以，比起邻接矩阵的存储方式，在邻接表中查询两个顶点之间的关系就没那么高效了。

> 改进升级版

在散列表那几节里，我讲到，在基于链表法解决冲突的散列表中，如果链过长，为了提高查找效率，我们可以将链表换成其他更加高效的数据结构，比如平衡二叉查找树等。我们刚刚也讲到，邻接表长得很像散列。所以，我们也可以将邻接表同散列表一样进行“改进升级”。

我们可以将邻接表中的链表改成平衡二叉查找树。实际开发中，我们可以选择用**红黑树**。这样，我们就可以更加快速地查找两个顶点之间是否存在边了。当然，这里的二叉查找树可以换成其他动态数据结构，比如**跳表**、**散列表**等。除此之外，我们还可以将链表改成**有序动态数组**，可以通过二分查找的方法来快速定位两个顶点之间否是存在边。

邻接矩阵存储方法的缺点是比较浪费空间，但是优点是查询效率高，而且方便矩阵运算。邻接表存储方法中每个顶点都对应一个链表，存储与其相连接的其他顶点。尽管邻接表的存储方式比较节省存储空间，但链表不方便查找，所以查询效率没有邻接矩阵存储方式高。针对这个问题，针对这个问题，邻接表还有改进升级版，即将链表换成更加高效的动态数据结构，比如平衡二叉查找树、跳表、散列表等。

> 如何存储微博、微信等社交网络中的好友关系？

数据结构是为算法服务的，所以具体选择哪种存储方法，与期望支持的操作有关系。针对微博用户关系，假设我们需要支持下面这样几个操作：

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

关于如何存储一个图，前面我们讲到两种主要的存储方法，邻接矩阵和邻接表。因为社交网络是一张**稀疏图**，使用邻接矩阵存储比较浪费存储空间。所以，这里我们采用**邻接表**来存储。

不过，用一个邻接表来存储这种有向图是不够的。我们去查找某个用户关注了哪些用户非常容易，但是如果要想知道某个用户都被哪些用户关注了，也就是用户的粉丝列表，是非常困难的。

基于此，我们需要一个**逆邻接表**。邻接表中存储了用户的关注关系，逆邻接表中存储的是用户的被关注关系。对应到图上，邻接表中，每个顶点的链表中，存储的是指向这个顶点的顶点。如果要查找某个用户关注了哪些用户，我们可以在邻接表中查找；如果要查找某个用户被哪些用户关注了，我们从逆邻接表中查找。

![501440bcffdcf4e6f9a5ca1117e990a1.jpg][]

基础的邻接表不适合快速判断两个用户之间是否是关注与被关注的关系，所以我们选择改进版本，将邻接表中的链表改为支持快速查找的动态数据结构。选择哪种动态数据结构呢？红黑树、跳表、有序动态数组还是散列表呢？

因为我们需要按照用户名称的首字母排序，分页来获取用户的粉丝列表或者关注列表，用**跳表**这种结构再合适不过了。这是因为，跳表插入、删除、查找都非常高效，时间复杂度是 O(logn)，空间复杂度上稍高，是 O(n)。最重要的一点，跳表中存储的数据本来就是有序的了，分页获取粉丝列表或关注列表，就非常高效。

如果对于小规模的数据，比如社交网络中只有几万、几十万个用户，我们可以将整个社交关系存储在内存中，上面的解决思路是没有问题的。但是如果像微博那样有上亿的用户，数据规模太大，我们就无法全部存储在内存中了。这个时候该怎么办呢？

我们可以通过**哈希算法等数据分片**方式，将邻接表存储在不同的机器上。你可以看下面这幅图，我们在机器 1 上存储顶点 1，2，3 的邻接表，在机器 2 上，存储顶点 4，5 的邻接表。逆邻接表的处理方式也一样。当要查询顶点与顶点关系的时候，我们就利用同样的哈希算法，先定位顶点所在的机器，然后再在相应的机器上查找。

![08e4f4330a1d88e9fec94b0f2d1bbe2f.jpg][]

除此之外，我们还有另外一种解决思路，就是利用外部存储（比如硬盘），因为外部存储的存储空间要比内存会宽裕很多。数据库是我们经常用来持久化存储关系数据的，所以我这里介绍一种**数据库的存储方式**。

我用下面这张表来存储这样一个图。为了高效地支持前面定义的操作，我们可以在表上建立多个索引，比如第一列、第二列，给这两列都建立索引。

![7339595c631660dc87559bec2ddf928f.jpg][]

> 课后思考

1.  关于开篇思考题，我们只讲了微博这种有向图的解决思路，那像微信这种无向图，应该怎么存储呢？你可以照着我的思路，自己做一下练习。

答：微信好友关系存储方式。无向图，也可以使用邻接表的方式存储每个人所对应的好友列表。为了支持快速查找，好友列表可以使用红黑树存储。

1.  除了我今天举的社交网络可以用图来表示之外，符合图这种结构特点的例子还有很多，比如知识图谱（Knowledge Graph）。关于图这种数据结构，你还能想到其他生活或者工作中的例子吗？

答：生活工作中应用图的例子。很多，互联网上网页之间通过超链接连接成一张有向图；城市乃至全国交通网络是一张加权图；人与人之间的人际关系够成一张图，著名的六度分割理论据说就是基于这个得到的。

--------------------

### 43 | 拓扑排序：如何确定代码源文件的编译依赖关系？ ###

依赖关系

穿衣顺序

> 算法解析

拓扑排序本身就是基于有向无环图的一个算法。

拓扑排序有两种实现方法，都不难理解。它们分别是Kahn 算法和DFS 深度优先搜索算法。

> Kahn 算法

贪心算法思想

定义数据结构的时候，如果 s 需要先于 t 执行，那就添加一条 s 指向 t 的边。所以，如果某个顶点入度为 0， 也就表示，没有任何顶点必须先于这个顶点执行，那么这个顶点就可以执行了。

我们先从图中，找出一个入度为 0 的顶点，将其输出到拓扑排序的结果序列中（对应代码中就是把它打印出来），并且把这个顶点从图中删除（也就是把这个顶点可达的顶点的入度都减 1）。我们循环执行上面的过程，直到所有的顶点都被输出。最后输出的序列，就是满足局部依赖关系的拓扑排序。

从 Kahn 代码中可以看出来，每个顶点被访问了一次，每个边也都被访问了一次，所以，Kahn 算法的时间复杂度就是 O(V+E)（V 表示顶点个数，E 表示边的个数）。

> DFS 算法

深度优先遍历

DFS 算法的时间复杂度我们之前分析过。每个顶点被访问两次，每条边都被访问一次，所以时间复杂度也是 O(V+E)。

> 拓扑排序的应用

*  凡是需要通过局部顺序来推导全局顺序的，一般都能用拓扑排序来解决。
 *  拓扑排序还能检测图中环的存在。对于 Kahn 算法来说，如果最后输出的顶点个数，少于图中顶点个数，图中还有入度不是 0 的顶点，那就说明，图中存在环。

> 思考

1、在今天的讲解中，我们用图表示依赖关系的时候，如果 a 先于 b 执行，我们就画一条从 a 到 b 的有向边；反过来，如果 a 先于 b，我们画一条从 b 到 a 的有向边，表示 b 依赖 a，那今天讲的 Kahn 算法和 DFS 算法还能否正确工作呢？如果不能，应该如何改造一下呢？

答：kahn算法找出度为0的节点删除。dfs算法直接用正邻接表即可

2、我们今天讲了两种拓扑排序算法的实现思路，Kahn 算法和 DFS 深度优先搜索算法，如果换做 BFS 广度优先搜索算法，还可以实现吗？

答：BFS也可以。其实与DFS一样，BFS也是从某个节点开始，找到所有与其相连通的节点。区别在于BFS是一层一层找（递归函数在for循环外），DFS是先一杆子插到底，再回来插第二条路、第三条路等等（递归函数在for循环内）。

--------------------

### 44 | 最短路径：地图软件是如何计算出最优出行路径的？ ###

地图软件的最优路线是如何计算出来的吗？底层依赖了什么算法呢？

> 算法解析

*  建模

我们之前也提到过，图这种数据结构的表达能力很强，显然，把地图抽象成图最合适不过了。我们把每个岔路口看作一个顶点，岔路口与岔路口之间的路看作一条边，路的长度就是边的权重。如果路是单行道，我们就在两个顶点之间画一条有向边；如果路是双行道，我们就在两个顶点之间画两条方向不同的边。这样，整个地图就被抽象成一个**有向有权图**。

*  单源最短路径算法

单源最短路径算法（一个顶点到一个顶点）。提到最短路径算法，最出名的莫过于 Dijkstra 算法了。

![e20907173c458fac741e556c947bb9a9.jpg][]

设有两个顶点集合 S 和 T，集合 S 中存放图中已找到最短路径的顶点，集合 T 存放图中剩余顶点。初始状态时，集合 S 中只包含源点 v0，然后不断从集合 T 中选取顶点 v0 路径长度最短的顶点 vu 并入到集合 S 中。集合 S 每并入一个新顶点 vu，都要修改顶点 v0 到集合 T 中顶点的最短路径长度值。不断重复此过程，直到集合 T 的顶点全部并入到 S 中为止。

时间复杂度就是 O(E\*logV)。E 表示边的个数，V 表示顶点的个数

Dijkstra实际上可以看做动态规划

*  如何计算最优出行路线？

从理论上讲，用 Dijkstra 算法可以计算出两点之间的最短路径。但是，你有没有想过，对于一个超级大地图来说，岔路口、道路都非常多，对应到图这种数据结构上来说，就有非常多的顶点和边。如果为了计算两点之间的最短路径，在一个超级大图上动用 Dijkstra 算法，遍历所有的顶点和边，显然会非常耗时。那我们有没有什么优化的方法呢？

对于软件开发工程师来说，我们经常要根据问题的实际背景，对解决方案权衡取舍。类似出行路线这种工程上的问题，我们没有必要非得求出个绝对最优解。很多时候，为了兼顾执行效率，我们只需要计算出一个可行的次优解就可以了

*  对工程问题，求出可行的次优解

虽然地图很大，但是两点之间的最短路径或者说较好的出行路径，并不会很“发散”，只会出现在两点之间和两点附近的区块内。所以我们可以在整个大地图上，**划出一个小的区块**，这个小区块恰好可以覆盖住两个点，但又不会很大。我们只需要在这个小区块内部运行 Dijkstra 算法，这样就可以避免遍历整个大图，也就大大提高了执行效率。

不过你可能会说了，如果两点距离比较远，从北京海淀区某个地点，到上海黄浦区某个地点，那上面的这种处理方法，显然就不工作了，毕竟覆盖北京和上海的区块并不小。

对于这样两点之间距离较远的路线规划，我们可以把北京海淀区或者北京看作一个顶点，把上海黄浦区或者上海看作一个顶点，先规划大的出行路线。比如，如何从北京到上海，必须要经过某几个顶点，或者某几条干道，然后再细化每个阶段的小路线。

*  最少时间

前面讲最短路径的时候，每条边的权重是路的长度。在计算最少时间的时候，算法还是不变，我们只需要把边的权重，从路的长度变成经过这段路所需要的时间。不过，这个时间会根据拥堵情况时刻变化。如何计算车通过一段路的时间呢？这是一个蛮有意思的问题，你可以自己思考下。

*  最少红绿灯

每经过一条边，就要经过一个红绿灯。关于最少红绿灯的出行方案，实际上，我们只需要**把每条边的权值改为 1 即可**，算法还是不变，可以继续使用前面讲的 Dijkstra 算法。不过，边的权值为 1，也就**相当于无权图**了，我们还可以使用之前讲过的广度优先搜索算法。因为我们前面讲过，**广度优先搜索算法计算出来的两点之间的路径，就是两点的最短路径**。

不过，这里给出的所有方案都非常粗糙，只是为了给你展示，如何结合实际的场景，灵活地应用算法，让算法为我们所用，真实的地图软件的路径规划，要比这个复杂很多。而且，比起 Dijkstra 算法，*地图软件用的更多的是类似 A 的启发式搜索算法*\*，不过也是在 Dijkstra 算法上的优化罢了，我们后面会讲到，这里暂且不展开。

> 翻译句子

我们有一个翻译系统，只能针对单个词来做翻译。如果要翻译一整个句子，我们需要将句子拆成一个一个的单词，再丢给翻译系统。针对每个单词，翻译系统会返回一组可选的翻译列表，并且针对每个翻译打一个分，表示这个翻译的可信程度。

![91b68e47e0d8521cb3ce66bb9827c767.jpg][]

针对每个单词，我们从可选列表中，选择其中一个翻译，组合起来就是整个句子的翻译。每个单词的翻译的得分之和，就是整个句子的翻译得分。随意搭配单词的翻译，会得到一个句子的不同翻译。针对整个句子，我们希望计算出得分最高的前 k 个翻译结果，你会怎么编程来实现呢？

![769cab20f6a50c0b7a4ed571c9f28a53.jpg][]

当然，最简单的办法还是借助回溯算法，穷举所有的排列组合情况，然后选出得分最高的前 k 个翻译结果。但是，这样做的时间复杂度会比较高，是 O(m^n)，其中，m 表示平均每个单词的可选翻译个数，n 表示一个句子中包含多少个单词。

实际上，这个问题可以借助 Dijkstra 算法的核心思想，非常高效地解决。每个单词的可选翻译是按照分数从大到小排列的，所以 a0b0c0 肯定是得分最高组合结果。我们把 a0b0c0 及得分作为一个对象，放入到优先级队列中。

我们每次从优先级队列中取出一个得分最高的组合，并基于这个组合进行扩展。扩展的策略是每个单词的翻译分别替换成下一个单词的翻译。比如  
a0b0c0 扩展后，会得到三个组合，a1b0c0 、a0b1c0 、a0b0c1 。我们把扩展之后的组合，加到优先级队列中。重复这个过程，直到获取到 k 个翻译组合或者队列为空。

![e71f307ca575d364ba2b23a022779f6c.jpg][]

时间复杂度：O(k*n*log(k\*n))，n个单词，k个组合

> 思考

1、在计算最短时间的出行路线中，如何获得通过某条路的时间呢？这个题目很有意思，我之前面试的时候也被问到过，你可以思考看看。

答：获取通过某条路的时间：通过某条路的时间与①路长度②路况(是否平坦等)③拥堵情况④红绿灯个数等因素相关。获取这些因素后就可以建立一个回归模型(比如线性回归)来估算时间。其中①②④因素比较固定，容易获得。③是动态的，但也可以通过a.与交通部门合作获得路段拥堵情况；b.联合其他导航软件获得在该路段的在线人数；c.通过现在时间段正好在次路段的其他用户的真实情况等方式估算。

2、今天讲的出行路线问题，我假设的是开车出行，那如果是公交出行呢？如果混合地铁、公交、步行，又该如何规划路线呢？

答：混合公交、地铁和步行时：地铁时刻表是固定的，容易估算。公交虽然没那么准时，大致时间是可以估计的，步行时间受路拥堵状况小，基本与道路长度成正比，也容易估算。总之，感觉公交、地铁、步行，时间估算会比开车更容易，也更准确些。

[625e7493b5470e774b5aa91fb4fdb9d2.jpg]: /images/20220301/ae9677fd74954bbf830771087abf8ccb.png
[039bc254b97bd11670cdc4bf2a8e1394.jpg]: /images/20220301/771fb8d29b214851b1c3b4995c6d7da2.png
[501440bcffdcf4e6f9a5ca1117e990a1.jpg]: /images/20220301/7772ce028fd44b0284686daf266b7b4c.png
[08e4f4330a1d88e9fec94b0f2d1bbe2f.jpg]: /images/20220301/357318a831ca4706a32d1a53ca0413f9.png
[7339595c631660dc87559bec2ddf928f.jpg]: /images/20220301/0b9ede88a32449e68dea4c4344cb01ea.png
[e20907173c458fac741e556c947bb9a9.jpg]: /images/20220301/fefe1e7f623d4ad9a8a88bdd3c972672.png
[91b68e47e0d8521cb3ce66bb9827c767.jpg]: /images/20220301/765df046d3e545d8a7d5f0cef7c7cacc.png
[769cab20f6a50c0b7a4ed571c9f28a53.jpg]: /images/20220301/f5661371783e4fa19e4e311049d56658.png
[e71f307ca575d364ba2b23a022779f6c.jpg]: /images/20220301/abbe9c2248ef47ae8fd8df238cd849bf.png