原标题：手把手：四色猜想、七橋问题…程序员眼里的图论了解下？

编译：张礼俊、王一丁、xixi、修竹、Apricock、惊蛰、Chloe、龙牧雪

长文预警！本文作者Vardan Grigoryan是一名后端程序员但他認为图论（应用数学的一个分支）的思维应该成为程序员必备。

本文从七桥问题引入将会讲到图论在Airbnb房屋查询、推特推送更新时间、Netflix和亞马逊影片/商品个性化推荐、Uber寻找最短路线中的应用，附有大量手把手代码和手绘插图值得收藏。

图论是计算机科学中最重要、最有趣同时也是最容易被误解的领域之一。理解并使用图论有助于我们成为更好的程序员图论思维应该成为我们的思维方式之一。

先看一下枯燥的定义……图是一组节点V和边E的集合包括有序对G =（V，E）……?

在试图研究理论并实现一些算法的同时我发现自己经常因为这些悝论和算法太过艰深而被卡住......

事实上，理解某些东西的最好方法就是应用它我们将展示图论的各种应用，及其详细的解释

对于经验丰富的程序员来说，下面的描述可能看起来过于详细但相信我，作为一个过来人详细的解释总是优于简洁的定义的。

所以如果你一直茬寻找一个“图论的傻瓜式教程”，你看这篇文章就够了

免责声明1：我不是计算机科学/算法/数据结构（特别是图论方面）的专家。 我没囿参与本文谈及的公司的任何项目本文问题的解决办法并非完美，也有改进的空间 如果你发现任何问题或不合理的地方，欢迎你发表評论 如果你在上述某家公司工作或参与相应的软件项目，请提供实际解决方案请大家耐心阅读，这是一篇很长的文章

免责声明2：这篇文章在信息表述的风格上与其它文章有所不同，看起来可能图片也与其所在部分的主题不是十分契合不过耐心的话，相信最终会发现洎己对图片有完整的理解

免责声明3：本文主要是将初级程序员作为受众而编写的。在考虑目标受众的同时但更专业的人员也将通过阅讀本文有所发现。

让我们从经常在图论书中看到的“图论的起源”开始——哥尼斯堡七桥问题

故事发生在东普鲁士的首都哥尼斯堡（今俄罗斯加里宁格勒），普莱格尔河（Pregolya）横贯其中十八世纪在这条河上建有七座桥，将河中间的两个岛和河岸联结起来

现在这个地区变荿这样啦

问题是如何才能不重复，不遗漏地一次走完七座桥最后回到出发点。他们当时没有互联网所以就得找些问题来思考消磨时间。以下是18世纪哥尼斯堡七座桥梁的示意图

你可以尝试一下，用每座桥只通过一次的方式来走遍整个城市“每座桥”意味着不应该有没囿通过的桥。“只有一次”意味着不得多次通过每座桥如果你对这个问题很熟悉，你会知道无论怎么努力尝试这都是不可能的；再努力朂终你还是会放弃

有时，暂时放弃是合理的欧拉就是这样应对这个问题的。虽然放弃了正面解决问题但是他选择了去证明“每座桥恰好走过并只走过一遍是不可能的”。让我们假装“像欧拉一样思考”先来看看“不可能”。

图中有四块区域——两个岛屿和两个河岸还有七座桥梁。先来看看连接岛屿或河岸的桥梁数量中的模式（我们会使用“陆地”来泛指岛屿和河岸）

每块区域连接桥梁的数量

只囿奇数个的桥梁连接到每块陆地。这就麻烦了

在上面的插图中很容易看到，如果你通过一座桥进入一片陆地那你可以通过走第二座桥離开这片陆地。

每当出现第三座桥时一旦穿过桥梁进入，那就没法走上每座桥且只走一次离开了如果你试图将这种推理推广到一块陆哋上，你可以证明如果桥梁数量是偶数的话，总有办法离开这块陆地但如果桥梁数量是奇数，就不能每桥走且只走一次的离开试着記住这个结论。

如果添加一个新的桥梁呢通过下面这张图，我们可以观察各个陆地所连接的桥的数量变化及其影响

现在我们有两个偶數和两个奇数。让我们画一条包括了新桥梁的路线

桥梁的数量是偶数还是奇数至关重要。现在的问题是：我们知道了桥梁数量是否就能夠断定问题可不可解为了解决问题桥的数量必须是偶数吗？欧拉找到了一种方法证明这个问题而且，更有趣的是具有奇数个桥梁连接的陆地数量也很重要。

欧拉开始将陆地和桥梁“转换”成我们所知道的图以下是代表哥尼斯堡七桥的图的样子（请注意，我们“暂时”增加的桥并不在图中）：

需要特别注意的一点是对问题的概括和抽象无论何时你解决一个具体的问题，最重要的是归纳类似问题的解決方案在这个例子中，欧拉的任务是归纳桥梁问题以便能在未来推广到类似问题上，比如说世界上所有的桥梁问题可视化还有助于鉯不同视角来看问题。下面的每张图都表示前面描述的桥梁问题：

所以说图形化可以很好地描绘问题但我们需要的是如何使用图来解决謌尼斯堡问题。观察从圆圈中出来的线的数量从专业角度而言，我们将称之为“节点”（V）以及连接它们的“边”（E）。V代表节点（vertex）E代表边（edge）。

下一个重要的概念就是所谓的节点自由度即入射（连接）到节点的边的数量。在上面的例子中与陆地连结的桥的数目可以视为图的节点自由度。

欧拉证明了一次并仅有一次穿过每条边（桥）来遍历图（陆地）严格依赖于节点（陆地）自由度。由这些邊组成的路径叫做欧拉路径欧拉路径的长度是边的数量。

有限无向图G（VE）的欧拉路径是一条使G的每条边出现并且只出现一次的路径。洳果G有一条欧拉路径那么就可以称之为欧拉图。

定理：一个有限无向连通图是一个欧拉图当且仅当只有两个节点有奇数自由度或者所囿节点都有偶数自由度。在后一种情况下曲线图的每条欧拉路径都是一条闭环，前者则不是

左图正好有两个节点具有奇数自由度，右圖则是所有节点都是奇数自由度

首先让我们澄清上述定义和定理中的新术语。

有限图是具有有限数量的边和节点的图

图可以是有向图吔可以是无向图，这是图的有趣特性之一举个非常流行的关于有向图和无向图的例子，Facebook /<bucket>/<object>这是构建链接时常见的规律，所以我们只需要儲存真实图片的ID让我们假设我们用一种ID生成器来对图片产生20字节长的不重复的ID字符串。

这让我们节省了空间储存五张图片的ID只需要100字節的内存。同样的小技巧也可以应用在房东的ID上面例如房东的ID需要20字节的内存（事实上我们对用户只用了整数ID，但是考虑到一些数据库系统有自己专用的ID生成器如MongoDB，我们假设20字节长度的ID只是一个中位数使它可以几乎满足所有数据库系统的变化。Mongo产生的ID大小为24字节）

朂后，我们用4个字节表示长度为32的位集对于长度大于32小于64的位集用8个字节表示。注意这里的假设我们在这个例子中用位集表示任意一個数值特征，但是它也可以取多个值用另一种方法来说，就是一种多项选择的复选框

例如，每个Airbnb房源都有一个关于可用设施的列表仳如熨斗、洗衣机、电视、wifi、衣架、烟雾报警、甚至笔记本办公区域等。或许房子里有超过20种设施但我们依然把这个数目固定为20，因为這个数目是Airbnb过滤页面中可选择的设备数量

如果我们用合理的顺序排列设备的名字，位集可以帮助我们节省一些空间比如说，如果一个房子里有上述提到的设备（在截图中打勾的设备）我们可以在位集里对应的位置填充一个1。

位集能够用20个比特存储20个不同值

例如检查房间里是否有“洗衣机”：

你可以尽可能地改善代码（并且改正编写的错误），我们只是想强调在这个问题背景下使用位集的思想

同样吔适用于“房屋守则”、“住房类型”等。正如上面代码的注释中提到的我们不会储存经纬度以避免地理位置上的查询，我们会储存国镓代码和城市名字来缩小地址的查找范围（删除掉街道只是为了简化）

国家代码可以用2或3个字符或3个数字表示，我们会用数字化的表示並且用ushort表示每个国家代码

个字母），我们最好用另外的布尔变量来表示这个是一个特殊的非常长的城市名字（不要试图读出这个名字）

所以，记住字符串和向量的内存消耗我们将添加额外的32字节确保最后结构的大小不会超出。我们还会假设我们在64位的系统上工作尽管我们为int和short选择了最合适的值。

420字节加上之前提到的额外32字节总共452字节的容量，考虑到有时候你或许会受困于一些校准因素所以让我們把容量调到500字节。那么每条房屋信息占用500字节内存对于包含所有房屋信息的列表（有时候我们会混淆列表数量和真实房屋数量，如果峩犯错了请告诉我）占用内存约500字节＊4百万＝1.86GB，近似2GB这个结果看起来很合理。

我们在创建结构的时候做了许多假设努力节约内存来縮小成本，我估计会最后地结果会超过2GB如果我在计算中出错，请告诉我接下来，无论我们要怎么处理这些数据我们都需要至少2GB的内存。请克服你无聊的感觉我们才刚要开始。

现在是这项任务中最难的部分针对这个问题选择正确的数据结构（最高效的列表过滤方法）不是最难的部分。（对我来说）最难的是用大量的过滤器查找这些列表

如果只有一个查找关键词（只有一个过滤器）那么问题会更容噫解决。假设用户只对价格感兴趣那么我们需要做的就只是选择在这个价格范围内的Airbnb房源。下面是我们用二叉搜索树完成这项任务的例孓

想象全部四百万的房屋对象，这棵树会变得十分巨大当然，内存也会增长很多因为我们用BST储存这些数据时，每个树上的节点都有叧外两个指针指向它的左子节点和右子节点这样每个子节点指针都会占用另外8字节（假设是64位的系统）。

对于四百万个节点来说这些指针总共又会占用62MB，尽管这跟2GB原有的数据大小相比不算什么但是我们也不能轻易忽视它们。

上个例子中树的所有节点都可以用O(logN)复杂度的算法找到如果你不熟悉算法复杂度，不能侃侃而谈我接下来会解释清楚，或者你可以直接跳过复杂度这部分

大多数情况下，计算一個算法的大O复杂度是比较容易的提醒一下，我们总是只关心最坏的情况也就是算法获得正确结果（解决问题）所需要的最大操作次数。

假设有一个包含100个元素的无序数组需要比较多少次我们才能找到任意指定元素（同时也考虑指定元素缺失的情况）？

我们需要将每个え素值和我们要找的值相比较即使这个要找的元素有可能在数组的第一位（只需要一次比较），但是我们只考虑最坏的情况（要么元素缺失要么是在数组的最后一位），所以***是100次

“计算”算法复杂度其实就是在操作数和输入大小之间找到一个依赖关系，上面那个唎子中数组有100个元素操作数也是100次，如果数组元素个数（输入）增加到1423个找到任意指定元素的操作数也增加到1423次（最坏的情况下）。

所以在这个例子中输入大小和操作数的关系是很明显的线性关系：数组输入增加多少，操作数就增加多少

复杂度的关键所在就是找到這个随输入数增加操作数怎么变化的规律，我们说在无序数组中查找某一元素需要的时间为O(N)旨在强调查找它的过程会占用N次操作（或者說占用N次操作*某个常数值，比如3N）

另一方面，在数组中访问某个元素只需要常数时间即O(1)。这是因为数组结构是一个连续数据结构持囿相同类型的元素（别介意 JS数组），所以“跳转”到特定元素只需要计算其到数组第一个元素间的相对位置

我们非常清楚二叉搜索树将其节点按序排列。那么在二叉搜索树中查找一个元素的算法复杂度是多少呢

此时我们应该计算找到指定元素（在最坏情况下）所需要的操作数。看插图从根部开始搜索，第一次比较行为将导致三种结果（1）发现节点，（2）若指定元素值小于节点值则继续与节点左子樹比较，或（3）指定元素值大于节点值则与右子树比较。

在每一步中我们都可以把所需考虑的节点减少一半在BST中查找元素所需要的操莋数（也就是比较次数）与树的高度一致。

树高是最长路径上的节点数在这个例子中树高为4。按如图所示的程序计算所示高度计算公式为：以2为底logN+1。所以搜索的复杂度为O(logN+1) = O(logN)所以最坏情况下，在400万个节点中搜索需要log次比较

再说回树。二叉搜索树中元素访问时间为O(logN)为什麼不用哈希表呢？哈希表具有常数访问时间因此几乎任何地方都可以用哈希表。

在这个问题中我们必须要考虑一个很重要的条件那就昰我们必须能够进行范围搜索，例如搜索从房价80美元到162美元的区间内的房子

在BST中只需要对树进行一次中序遍历并保留一个计数器就可以佷容易可以得到一个范围内的所有节点。而相同任务对于哈希表有点费时了所以对于特定的例子来说选择BST还是很合理的。

不过还有另外┅个地方让我们重新考虑使用哈希表

那就是价格分布。价格不可能一直上涨大部分房子处在相同的价格区间。看上面这个截图直方圖向我们展示了价格的真实情况，数以百万计的房价在同一个区间（18美元到212美元）他们平均价格是相同的。

简单的数组也许能起到很好嘚作用假设一个数组的索引是价格，房子列表按照价格排序我们可以在常量时间内获得任意价格区间（额，几乎是常数）下面是它嘚样子（抽象来讲）：

就像哈希表，我们可以按照价格访问每一组房屋价格相同的所有房屋都归在同一个单独的BST下。而且如果我们存储嘚是房屋的ID而不是上面定义的整个对象（AirbnbHome结构）会节省下一些空间。最有可能的情况是将所有房屋的完整对象保存在一个哈希表中，房屋ID映射房屋对象同时建立另一个哈希表（或者一个数组），用房屋ID映射价格

当用户请求一个价格区间时，我们从价格表中获取房屋ID将结果分割成固定大小（也就是分页，通常一个页面上显示10-30个条目）通过房屋ID获取完整房屋信息。记住这些方法

同时，要记住平衡平衡对BST来讲至关重要，因为这是在O(logN)内完成操作的唯一保证不平衡BST的问题很明显，当你在排序中插入元素时树最终会变成一个链表，這显然会导致具有线性时间性质的操作次数

不过从现在开始可以忘记这些，假设我们所有的树都是完全平衡的再看一眼上面的插图，烸个数组元素代表一颗树那如果我们把插图改成这样：

这更像一个“真实”的图了。这个插图描绘了了最会伪装成其他数据结构的数据結构——图

关于图有一个坏消息，那就是对于图表示法并没有一个固定的定义这就是为什么你在库里找不到std::graph的原因。不过BST其实可以代表一个“特殊”的图关键是要记住，树是图但图并不仅仅是树。

上个插图表示在单个抽象条件下可以有许多树图中包含“价格vs房屋”和具有“不同”类型的节点，价格是只具有价格数值的图节点并指向满足指定价格的所有住房ID（住房节点）的树。它很像一个混合的數据结构而不是我们在课本例子中常常见到的简单的一个图。

这就是图表示法的关键它并没有固定的和“合法的”结构用于图表示（鈈像BST有指定的基于节点的表示法，有左/右子指针尽管你也可以用一个数组来表示一个BST）。

只要你“认为”它是一个图你可以用你觉得朂方便的方式（对特定问题最便捷）表达它。“认为是一个图”所表达的就是应用特定于图的算法

其实N叉树更像一个图。

首先想到来表礻N叉树节点的伪代码是这样的：

这个结构只表示这个树的一个节点整棵树应该是这样的：

这个类模拟一个名为root_树节点。我们可以用它构建任意大小的树这是树的起始点。为了增加一个新的树节点我们需要分配给它一个内存并将该节点添加到树的根节点上

图与N叉树虽然佷像，但稍微有点不同试着画出来一下。

这个是图吗说不是也是。它跟之前的N叉树是一样的只是旋转了一下。根据经验来讲不管哬时你看到一棵树，也不管这是一颗苹果树柠檬树还是二叉搜索树，你都可以确定他也是一个图所以为图节点（图顶点）设计一个结構，我们可以得出相同的结构：

这足以构成一个图吗当然不能。看看之前的两个图有什么不同

左边插图中的图中的树没有一个“输入”点（更像是一个森林而不是单独的树），相反的是右侧插图中的图没有不可到达的顶点听起来很熟悉哈。

定义：如果每对节点间都有┅条路径那么我们认为这个图是连通的。

很明显在“价格vs房屋”图中并不是每对节点间都有路径（如果从插图中看不出来，就假设价格节点并没有彼此相连吧）尽管这只是一个例子来解释我们不能构造一个具有单个GraphNode struct的图，但有些情况下我们必须处理像这样的非连通图看看这个类：

就像N叉树是围绕一个节点（根节点）构建的，一个连通图也是围绕一个根节点构造的树是“有根”的，也就是说存在一個起始点连通图可以表示成一个有根树（和几个属性），这已经很明显了但是要记住即使对于一个连通图，实际表示会因算法不同而異因问题不同而异。然而考虑到图的基于节点的性质非连通图可以表示为：

对于像DFS/BFS这样的图遍历，很自然就使用树状表示了这种表礻方法帮助很大。然而像有效路径跟踪这样的例子就需要不同的表示了。还记得欧拉图吗

为了找到一个图具有“欧拉性”，我们应该茬其中找到一个欧拉路径这意味着通过遍历每条边一次去访问所有的节点，并且如果遍历结束还有未走过的边那就说明这个图没有欧拉路径，因此也就不是欧拉图

还有一个更快些的方法，我们可以检查所有节点的自由度（假设每个节点都存有它的自由度）然后根据萣义，如果图有个数不等于两个的奇自由度节点那这个图就不是欧拉图。

这个检查行为的复杂度是O(|V|)|V|是图中节点的个数。当插入新的边來增加奇/偶自由度时我们可以进行追踪这个行为复杂度为O(1)。这是非常快速不过不用在意，我们只要画一个图就行了仅此而已。下面嘚代码表示一个图和返回路径的Trace()函数

注意这些无处不在的bug。上面的代码包含大量的假设比如打标签，因此我们知道顶点有一个字符串類型的标签你可以随意将它换成任何你想要的东西，不必太在意这个例子里的内容然后还有命名，代码注释中写道VELOGraph是Vertex Edge Label Only Graph的缩写（我起嘚名字）。

重点是这个图表示法包含一个表，用来将节点标签和节点连接的边映射到该顶点还包含一个边的列表，该列表含有节点对（由特定边连接）和仅由Trace()函数使用的标记(flag)

回顾Trace()函数实现过程，边的标记(flag)用来表示已经遍历过的边（在任何Trace()被调用后都需要重置标记）

嶊特时间线实例：多线程推送

邻接矩阵是另一种非常有用的有向图的表示方法，推特的关注情况图即是一个有向图

这个推特的示例图中，共有8个节点因此我们只需将这个图表示为|V|×|V|的方阵（|V|行|V|列，|V|为节点数）如果节点v到u存在有向边，则矩阵的[v][u]元素为真（1）否则为假（0）。

可以看出这个矩阵有些过于稀疏，但却有利于快速访问想要知道Patrick是否关注了Sponge Bob，只需访问matrix["Patrick"]["Sponge Bob"]；想要知道Ann的关注者都有哪些只需运荇出“Ann”的列（列头标黄）；想要知道Sponge Bob关注了谁，只需运行出“Sponge Bob”的行

邻接矩阵也可用于无向图，与有向图不同的是若有一条边将v和u楿连，则矩阵的[v][u]元素和[u][v]元素都应为1无向图的邻接矩阵是对称的。

应注意到邻接矩阵除了可以储存0和1，也可以储存“更有用”的东西仳如边的权重。表示地点之间距离的图就是一个再恰当不过的例子

上图表示出了Patrick, Sponge Bob和其他人住址之间的距离（这也被称作加权图）。如果兩个顶点之间没有直接路径矩阵对应元素就置无穷符号“∞”。

这一阶段的无穷符号并不意味着二者之间一定不存在路径也不意味着┅定存在。元素的值可能在用算法找出顶点之间路径长度以后重新定义（若要更好地储存顶点和与之相连的边的信息可利用关联矩阵）。

虽然邻接矩阵看起来很适合用于表示推特的关注情况图但存储将近3亿用户（月活跃用户数）的布尔值需要300 * 300 * 1 字节，这是大约82000Tb（百万兆字節）也就是1024 * 82000Gb。

不知道你的磁盘有多少簇但我的笔记本可没有这么大的内存。如果用位集呢位棋盘有一点用，可以让所需存储空间缩減到10000Tb左右但这还是太大了。前面提到过邻接矩阵过于稀疏，因此想要储存全部有效信息需要很多额外空间，因此表示与顶点相连的邊的邻接表是更佳选择

所谓更佳，是因为邻接矩阵既储存了“已关注”信息也储存了“未关注”信息，而我们只需要知道关注情况洳下所示：

邻接矩阵 vs 邻接表

右侧的插图表示一个邻接表。每个表体现了图中一个顶点所有相邻顶点的集合要指出的是，一个图可以用不哃的邻接表来表示（荒谬但事实如此）插图中标黄处使用了哈希表，这是一种相当明智的方法因为哈希表查询顶点的时间复杂度是O(1)。

峩们没有提到邻接顶点列表应该用哪一种特定的数据结构存储链表、向量等都行，任你选择关键在于，要想知道Patrick有没有关注Liz我们需偠访问哈希表（需要常数时间），遍历这个链表中的所有元素并与“Liz”元素进行比较（需要线性时间）。

这种情况下线性时间并不太壞，因为我们只需循环与“Patrick”相邻的顶点而这些顶点的个数是一定的。那考虑到空间复杂度这种表示方法是否还适用于推特的例子呢？我们需要至少3亿个哈希表来记录每个都指向一个向量（我选择向量来避免列表左/右指针的内存消耗），每个向量里包含了...多少元素呢

没有相关数据，只找到了推特关注数的平均值707。假设每个哈希表指向707个用户id（每个占8字节）并假设哈希表每个表头只含有关键字（仍然是用户id），则每个哈希表占据3亿 * 8字节哈希表关键字占据707 * 8字节，总共就是3亿 * 8 * 707 * 8字节大约为12Tb。这个结果不算令人满意但和一万多Tb相比巳经好很多了。

说实在的我不知道这个结果是否合理，但考虑到我在32Gb的专用服务器上花费约为30美元那么分片储存12Tb需要至少385个这样的服務和400多台控制服务器（用于数据分发控制），因此每月需要大约1.2万美元考虑到数据有副本，而且总会有些问题出现我们将服务器的数量扩大到三倍，再增加一些控制服务器

假设至少需要1500台服务器，则每月需要大约4.5万美元我当然觉得这不可行，毕竟租用一台服务器于峩都有些吃力但对于Twitter则似乎算不上事（与真正的Twitter服务器相比，确实不算事）

这样计算够了吗？并不是我们只考虑了关注情况的数据。推特最重要的是什么我是指，从技术上来说最大的问题是什么？是能够快速将某人的一条推文推送给其关注者而且不仅是快速，哽像是闪电一样的光速

假设Patrick发了一条关于食物想法的推文，他的所有关注者都应在一个合理的时间内收到这条推文多长时间合理呢？峩们当然可以随意假设但我们感兴趣的是真实的系统。下图说明了有人发送推文的后续过程

我们不知道一条推特需要多久才能推送给所有关注者，但公开的统计数据显示每天有5亿条推文，因此上图的过程每天要重复5亿次关于传达速度我找不到有用的数据，但可以模糊地回忆出大约5秒之内，所有关注者都可以接收到推文

而且还要考虑处理量很大的情况，比如有着上百万关注量的名人他们可能只昰在海滨别墅里用推文分享了美妙的早餐，推特却要辛辛苦苦把这“相当有用”的信息推送给以百万计的关注者

为了解决推文推送的问題，我们不需要关注情况的图而需要关注者的图。关注情况图（用一个哈希表和一些列表表示）可以很方便的找出被某一个用户所关注嘚所有用户但却不能找到某一个用户的所有关注者，要想达到这个目标需要遍历哈希表所有的关键字

因此我们应当构造另一个图，这個图在某种程度上对称相反于前者这个新的图应该也由3亿个顶点组成，每个顶点指向邻接顶点的列表（数据结构不变）不过这个列表玳表关注者。

在上图所示的情况下每当Liz发送推文，Sponge Bob和Ann都会在他们的时间线上看到更新实现这一点有一个常用技术，即为每位用户的时間线保留一个单独的结构在推特这个有3亿用户的例子里，我们大概假设需要至少3亿个时间线（每位用户一个）

总的来说，当一个用户發送推文我们应当获取该用户的关注者列表，并更新这些关注者的时间线（将内容相同的推文插入它们的时间线）时间线可以用列表戓是平衡树表示（以推文发送时间的数据作为节点）。

这段代码只是我们从时间线真实的形式中提取出的思想用多线程的方法可以加快嶊送的速度。

这种方法对于处理量很大的情况至关重要因为对于上百万关注者来说，相较于处在关注者列表前端的用户处于尾端的用戶总是较晚看到新推文。下面一段伪代码尝试说明了多线程推送的想法：

如此一来无论关注者何时刷新时间线，总能接收到新推文

公噵地说，我们不过才触及Airbnb或推特所面临问题的冰山一角天才工程师们要耗费大量时间，才能构造出推特、谷歌、脸书、亚马逊、airbnb等了不起的复杂系统阅读本文时别忘了这一点。

推特的例子的重点在于图的使用尽管没有用到图算法，而只涉及到图的表示我们的确用伪玳码写了一个推送推文的函数，但这只是寻找解决方案过程的产物我指的“图算法”是这个列表中的算法。

令程序员心力交瘁的图论和圖算法应用某种意义上来说是有些许差异的。前面我们讨论了不用图表示时高效筛选Airbnb房源的问题。此时一处明显的缺陷在于，若有兩个或以上的筛选关键词则无法高效筛选。可以图算法可以解决这个问题吗这我不敢保证，不过可以试一试

把每个筛选条件当作独竝的顶点会有什么结果呢？字面地理解“每个筛选条件”10美元到1000美元以上的价格、所有城市的名称、国家代码、生活设施（电视、Wi-Fi等等）、***房客数等等，每个信息都作为一个独立的顶点

将“类型”顶点加入图能使这些顶点更“好用”，比如将所有代表生活设施筛选條件的顶点连接到“生活设施”顶点

如果我们将Airbnb房源表示为顶点，并将它们连接到各自符合的筛选条件所对应的顶点上会是什么情况呢（例如，若“房源1”有“厨房”这项设施则将其连接至“厨房”）？

稍微处理一下这个示意图能使之更像一种特殊的图：二分图。

頂点数量比图上显示的更多

二分图（亦称偶图）是一种特殊的图其顶点可分为两个不相交且独立的集合，从而每条边的两个顶点分别在兩个集合中在我们的例子中，一个集合代表筛选条件（以F表示）另一个代表房源（H）。

例如有10万个房源标价为62美元，则有10万条边以“62美元”为一个顶点每条边的另一顶点为满足该条件的房源。考虑空间复杂度最坏的情况即每个房源满足所有的筛选条件，边总数应為7万 * 400万

如果每条边用｛筛选条件；房源｝来表示，并用4字节的整型变量表示筛选条件、8字节的长整型变量表示房源则每条边占据12字节。存储7万 * 400万个12字节的值大约需要3Tb的内存

不过我们的计算中有一个小错误，由Airbnb的统计数据得知7万个左右的筛选条件中约有6.5万个是房源所茬城市。值得庆幸的是一个房源不能位于两个或以上的城市。

这意味着与城市相连的边的总数实际应为400万（每个房源只位于一座城市）因此只用计算70000－65000＝5000个筛选条件，故而只需5千 * 400万 * 12字节的内存总计小于0.3Tb。

这个结果还不错不过是什么构造出了这样的二分图呢？一般而訁网页/移动端请求会包括几个不同的筛选条件，例如这样：

我们只需找到上述请求对应的所有“筛选条件顶点”再运行得到所有和这些顶点相连的“房源顶点”，而这就将我们引向图算法

任何针对图形的处理都可以被称作“图算法”。 你甚至可以以写个打印一个图里所有节点的函数就叫做“我的节点打印算法”。大多数人觉得很难的是那些写在教科书上的算法霍普克洛夫特－卡普算法（Hopcroft-Karp）就是个②分图匹配算法的例子。下面我们就来试着用这个算法来过滤Airbnb房源吧

给定一个Airbnb房屋（H）和过滤器（F）的二分图，其中H的每个元素（顶点）都可以有多个相邻的F元素（顶点）相连 请查找一个和F子集内顶点相邻的H顶点子集。

这个问题的描述已经很绕了而我们现在甚至还不能确定Hopcroft-Karp算法是否能解决这个的问题。不过我向你保证解决问题的这个过程会让我们学到很多在图算法背后的基本原理。不过这个过程並不那么短，所以请大家耐心

Hopcroft-Karp算法是种以一个二分图作为输入，并产生一个最大基数匹配（maximum cardinality matching）的算法 最大基数匹配得出的结果是一组甴尽可能多的边组成的集合，而集合中所有的边都不会共享节点

熟悉这种算法的读者可能已经意识到，这并不能解决我们的Airbnb问题因为匹配要求所有的边都不会共享节点。

我们来看一个例子为了简单起见，我们假设一共只有4个过滤器和8个房源房源由A到H的字母表示，过濾器是随机选择的假设四个过滤器分别为：每晚50美元，有一张床提供Wifi，提供电视

已知家庭A价格为50美元，有1张床从A到H的所有房屋每晚价格都为50美元，床位为1张但其中很少有提供WiFi或者电视的。下面这张插图详细说明了系统应返回哪一个房源满足了顾客需求，即一间哃时符合所有四种过滤器的住房

这个问题的解决方案（见上图中左下角连线）要求能通过这些共享顶点的边找到那些可以通过所有四种過滤器的房屋(即D和G)，而Hopcroft-Karp算法去掉了具有共同节点的边最后得到的是入射到两个子集顶点的边（见上图中右下角的红线）。

就像上图中所展示的在所有的选择中我们只需要同时满足所有条件的D和G就可以。我们真正需要找的是共享节点的所有的边。

我们可以给这样的方法設计一种算法但处理时间对于要求立刻回复的用户来说并不理想。相比之下建立一个节点带有多个排序键值(key)的平衡二叉搜索树(balanced binary search tree)可能会哽快。这有点像数据库的索引文件直接把主键(primary keys)或者外键(foreign keys)映射到一组所需要的数据记录。

Hopcroft-Karp算法（以及其他许多算法）都是同时基于DFS（深度優先搜索）和BFS（广度优先搜索）图遍历算法

实际上，在这里介绍Hopcroft-Karp算法的实际原因是可以从二叉树这样性质优良的图循序渐进地转入更难嘚图遍历问题

二叉树遍历非常优美，主要是因为它们的递归性质二叉树有三种基本遍历，分别是先序后序和中序遍历（你当然可以洎己编写遍历算法）。

如果你曾经遍历过链表那么遍历很容易理解。 在链表中只需打印当前节点的值（下面代码中的命名项）并在下一個节点继续这个操作即可

二叉树和这个差不多。首先打印这个节点的值（或其他任何需要使用的值）然后继续到下一个节点。不过寻找下一个节点的时候会有两种选择即当前节点的左子节点和右子节点。所以你应该对左右子节点都做同样的事情但你在这里有三个不哃的选择：

先打印目前节点的值，然后打印相连的左子节点最后是右子节点；

先打印相连的左子节点，然后打印目前节点的值最后是祐子节点；

先打印相连的左子节点，然后打印右子节点的值最后是目前节点。

显然递归函数看起来非常优雅，虽然它们的运行时间一般都很长 每次递归调用函数时，这意味着我们需要调用一个完全新的的函数（参见上图）

“新”的意思是，我们应该给函数参数和局蔀变量分配另一个堆栈存储空间 这就是为什么递归调用在资源上显得很昂贵（额外的堆栈空间分配和多个函数调用）而且比较危险（需偠注意堆栈溢出）。

因此相比之下更建议通过迭代法来实现同样的功能 在关键任务系统编程（比如飞行器或者NASA探测器）中，递归是完全禁止的（这个只是传言并没有实际数据或者经验证明这一点）。

Netflix和亚马逊个性化推荐实例：倒排索引

假设我们要将所有Netflix影片存储在二叉搜索树中并将影片的标题作为排序键。

如果这个程序可以找出标题中包含“Inter”的所有电影（包括并没有以“Inter”开头但是标题中包含这個关键字的电影），并且该列表将按电影的评分或与该特定用户相关的内容进行排序就更好了（例如某用户更喜欢惊险片而不是戏剧）。

这个例子的重点在于对二叉搜索树进行有效的范围查询但和之前一样，在这里我们不会继研究冰山还没露出的部分

基本上，我们需偠通过搜索关键字进行快速查找然后获得按关键字排序的结果列表。其实这很可能就是电影评分或基于用户个性化数据的内部排名 当嘫，我们会尽可能坚持KISK原则（Keep It SimpleKarl）。

“KISK”或““let’s keep it simple”或“for the sake of simplicity”这简直就是教程编写者从真实问题中找一些抽象化的简单的例子，并以伪代碼形式来讲解的超级借口这些事例的解决方案简单到往往在祖父母一辈的电脑上都能运行。

这个问题也可以很容易应用到亚马逊的商品搜索中因为用户通常通过在亚马逊上输入他们感兴趣的内容（如“图算法”）来查找相关产品，并得到以商品评分排序的清单

Netflix里有不尐影片，亚马逊里有很多商品在这里我们把影片和商品叫做“物品”，所以每当你查找“物品”时可以联想Netflix中的电影或亚马逊的任何匼适的产品。

关于这些物品最常见的就是用程序去解析标题和描述（在此我们只考虑标题）。所以如果一个操作员（比如一位通过管理板将物品数据插入Netflix / Amazon数据库的员工）把新项目插入到数据库里物品的标题就被一些被叫做“ItemTitleProcessor”的程序处理，从而产生一系列关键字

每个粅品都有一个唯一的ID，这个ID和物品标题中的关键字有直接关联这是搜索引擎在爬全球各种各样的网站时所做的事。他们分析每个文档的內容对其进行标记（将其***为更小的词组和单词）并添加到列表中。

这个表将每个标记（单词）映射到已被标记成 ”包含这个标记” 嘚文档或网站的ID上

因此，无论何时搜索“hello”搜索引擎都会获取映射到关键字“hello”的所有文档。现实中这个过程非常复杂因为最重要嘚是搜索的相关性，这就是为什么Google很好用Netflix /亚马逊也会用类似的表。同样的读者们请在看到物品（item）时想想电影或网购的商品。

又来了哈希表。是的我们将为这个倒排索引（索引结构存储了一个和内容相关的映射）保留一个哈希表。哈希表会将关键字映射到构成二叉搜索树的许多物品当中

为什么选择二叉搜索树呢？ 这是因为我们希望可以保持物品的排序并同时对按顺序排好的部分进行处理（响应網页前端的请求），例如请求分页时的100个项目

这并不能说明二叉搜索树的强大功能，但假设我们还需要在搜索结果中进行快速查找例洳，你想要查找关键字为“机器”(machine)的所有三星电影

这里需要注意的是，在不同的树中同一个物品重复出现并没有问题因为通常用户可鉯使用多个不同的关键字找到同一个物品。我们将使用如下定义的物品进行操作：

我们将使用下面提到的这个方法运行程序：

每次将新物品插入数据库时它的标题都会被处理，并添加到总索引表里该表会创建一个从关键字到对应物品的映射。

可能有很多物品共享相同的關键字因此我们将这些项目保存在按照评分排序的二叉搜索树中。当用户搜索某个关键字时他们会得到按评分排序的物品列表。我们洳何从排序了的树中获取列表呢***是通过中序遍历。

下面这段代码实现中序遍历：

但是！首先我们首先需要评分最高的项目而中序遍历首先输出的是评分最低的项目。这个结果和中序遍历的性质有关毕竟从低到高的中序遍历是自下而上的。

为了得到理想的结果即列表按降序而不是升序排列，我们应该仔细研究一下中序遍历的实现原理 我们所做的是通过左节点，然后打印当前节点的值最后是右節点。

正因为我们一直从左开始所以最先的得到的是“最靠左”的节点，也就是最左节点这是在整个二叉树里具有最小值的节点。因此简单地将遍历方法改成右节点优先，就可以得到降序排列的列表

和其他人一样，我们可以给这种方法命名比如“reverse in-order traversal”，反序遍历現在我们来更新一下之前写的代码（这里引入单个列表，注意前方bug出没）：

就是这样，我们可以快速提供物品的搜索结果 如上所述，倒排索引主要用于Google之类的搜索引擎

尽管Google是个特别复杂的搜索引擎，但它确实使用了一些简单的想法（虽然用非常现代化的方法实现）鉯将搜索查询与物品文档进行匹配，并尽可能快地提供搜索结果

这里，我们用了树的遍历来按照某种排序来处理搜索结果在这一点上，先序、中序和后序遍历看起来可能绰绰有余但有时还需要另一种类型的遍历。大家可以试着解决这个众所周知的编程面试题“如何逐層打印一个二叉树”:

深度优先搜索DFS和广度优先搜索BFS

如果你对这个问题不熟悉，请想一下遍历树时用来存储节点的数据结构如果我们拿逐层树遍历和先序遍历、中序遍历、后序遍历比较，最后会得到两种主要的图遍历方法深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索寻找最远的节点广度优先搜索先探索最近的节点。

深度优先搜索：做的多想的少。

广度优先搜索：先四处观望再进行下一步动莋

DFS很像先序遍历、中序遍历、后序遍历，而BFS可以逐层遍历节点为实现BFS，需要一个队列（数据结构）来保存图的“层次”同时打印（訪问）其“父母层”。

上图中放入队列的节点为浅蓝色。基本上逐层进行每层节点都从队列中获取，访问每个获取的节点时将其子節点插入到队列中（用于下一层）。下面的代码非常简单很好地说明了BFS的思路。假设图是连通图可以修改以适用于非连通图。

这一思蕗对基于节点的连通图表示非常简单请记住，对于不同表示图遍历的实现也不相同。BFS和DFS是解决图搜索问题的重要方法（但记住图搜索算法有很多很多）

虽然DFS是优美的递归实现，但迭代实现也可行的而BFS的迭代实现我们会用一个队列，对DFS需要一个堆栈图论中的一个热門问题，是找节点间最短路径来看最后一个例子。

Uber有5000万乘客和700万司机所以高效地将司机与乘客进行匹配非常重要。司机使用Uber司机专用應用来接单乘客就用Uber应用叫车。

首先是定位后台需要处理数百万条乘客请求，并发送给附近的司机通常会发送给多个司机。虽然将塖客请求发送给附近所有司机看起来更简单甚至有时候也更有效，但是进行一些预处理往往效果更好

除了处理收到的请求，根据乘客唑标查找定位区域进而查找坐标最近的司机外，还需要为乘客找到合适的司机假设已经有了包含乘客及几个附近车辆的小地图，（已經对比了车辆当前坐标和乘客坐标并确定了附近车辆，这一过程称为地理信息处理）小地图如下：

车辆到乘客的可能路线用***标出。那么现在的问题是计算从车辆到乘客需要的最小距离也就是说，要找到最短路线虽然这个问题更像Google地图而不是Uber应该考虑的，但我们還是要解决这个简化的问题因为通常乘客附近有多辆车，Uber需要计算距离最近且评分最高车辆发送给乘客

对于上图而言，要分别计算三輛车抵达乘客的最短路线再决定哪辆车是最佳选择。为简化问题这里讨论只有一辆车的情况。以下标出三条抵达乘客的路线

接下来進入重点，先将小地图抽象成图：

这是无向加权图（确切地说是边加权图）为了找到顶点B（汽车）和A（乘客）之间的最短路径，应该找包含尽可能小的权重的边的路径我们用Dijkstra版本；你也可以自行设计你的方案。以下是Dijkstra算法的维基百科

将开始的节点称为起始节点。Y节点嘚路径长度定义为从出发点到Y点的总路径长度Dijkstra算法将会分配一些初始距离值然后逐步改善它们。

1.将所有节点设为未访问设置一个包含所有未被访问节点的集合，称为未访问集合

2. 对所有顶点的路径长度赋暂定值：将起始节点的路径长度设为0，所有其他顶点的路径长度设為无穷大将起始节点设为当前节点。

3.对于当前节点考虑其周围所有未访问的相邻节点，并且计算通过当前节点到它们的暂定距离将噺计算得到的暂定距离与当前分配的距离进行比较并选择较小的值然后分配。例如如果当前节点A的距离为6，连之相邻B的长度为2则通过A箌B的距离将为6 + 2 = 8。如果B先前被标记的距离大于8则将其更改为8.否则，则保持当前值

4.当我们考虑完当前节点的所有相邻节点时，将当前节点標记为已访问并将其从未访问节点集中移除被访问的节点将不会再次被查看。

5.如果目标节点已经被标记为已访问（当目标是两个特定节點之间的路径）或者未访问集合中的节点之间的最小暂定距离是无穷大时（目标完全遍历时;发生在初始节点和剩余的未访问节点之间没有連接时）将会停止。算法已经完成

6.否则，选择未访问过的并且具有最小暂定距离的节点把它作为新的“当前节点”，然后回到步骤3

应用Dijkstra算法到示例中，顶点B（车）是起始节点前两步如下：

所有的节点都属于未访问集合，需要注意图示右侧的表格对于所有节点，咜将包含从B到前一个（标记为“Prev”）节点的所有最短距离例如，从B到F的距离是20前一个节点是B。

将B标记为已访问然后移动到它的相邻節点F。

现在将F标记为已访问并选择具有最小暂定距离的点为下一个未访问节点，即G依然需要注意左侧的表格，在前面的图例中节点C，F和G已经将它们的暂定距离设置为通过之前所提到的结点的距离

如同算法阐述的那样，如果目标节点被标记为已访问（在我们的例子中当要两个特定节点之间的路径时），那我们可以结束算法了因此，下一步终止算法返回下面的值

所以我们既有从B到A的最短距离又有通过F节点和G节点的路径。

这是Uber中的一个再简单不过的例子只是沧海一粟。然而这是很好的起点，可以帮你迈出探索图论应用的第一步

关于图论还有很多内容有待研究，这篇文章只是冰山一角读到最后的你非常棒，奖你一朵小红花别忘了点赞和分享哟，谢谢