手把手：四色猜想、七桥问……序员眼里的图论（第一部分） 分享 - 谷普下载手把手：四色猜想、七桥问……序员眼里的图论（第一部分）点击复制内容大数据文摘作品编译：张礼俊、王一丁、xixi、修竹、Apricock、惊蛰、Chloe、龙牧雪长文预警！本文作者Vardan Grigoryan是一名后端程序员，但他认为图论（应用数学的一个分支）的思维应该成为程序员必备。本文从七桥问题引入，将会讲到图论在Airbnb房屋查询、推特推送更新时间、Netflix和亚马逊影片/商品个性化推荐、Uber寻找最短路线中的应用，附有大量手把手代码和手绘插图，值得收藏。图论的傻瓜式教程图论是计算机科学中最重要、最有趣，同时也是最容易被误解的领域之一。懂得并使用图论有助于我们成为更好的程序员。图论思维应该成为我们的思维方法之一。先看一下枯燥的定义……图是一组节点V和边E的聚集，包含有序对G =（V，E）……??在试图研究理论并实现一些算法的同时，我发明自己经常因为这些理论和算法太过艰深而被卡住......事实上，懂得某些东西的最好方式就是应用它。我们将展示图论的各种应用，及其详细的解释。对于经验丰盛的程序员来说，下面的描述可能看起来过于详细，但相信我，作为一个过来人，详细的解释总是优于简洁的定义的。所以，如果你一直在寻找一个“图论的傻瓜式教程”，你看这篇文章就够了。免责声明免责声明1：我不是计算机科学/算法/数据结构（特别是图论方面）的专家。 我没有参与本文谈及的公司的任何项目。本文问题的解决办法并非完美，也有改良的空间。 如果你发明任何问题或不合理的地方，欢迎你发表评论。 如果你在上述某家公司工作或参与相应的软件项目，请提供实际解决方案。请大家耐心导语，这是一篇很长的文章。免责声明2：这篇文章在信息表述的风格上与其它文章有所不同，看起来可能图片也与其所在部分的主题不是十分契合，不过耐心的话，相信最终会发明自己对图片有完整的懂得。免责声明3：本文主要是将初级程序员作为受众而编写的。在考虑目标受众的同时，但更专业的人员也将通过导语本文有所发明。哥尼斯堡的七桥问题让我们从经常在图论书中看到的“图论的起源”开始――哥尼斯堡七桥问题。故事发生在东普鲁士的首都哥尼斯堡（今俄罗斯加里宁格勒），普莱格尔河（Pregolya）横贯其中。十八世纪在这条河上建有七座桥，将河中间的两个岛和河岸联结起来。现在这个地域变成这样啦问题是如何才能不重复，不遗漏地一次走完七座桥，最后回到出发点。他们当时没有互联网，所以就得找些问题来思考消磨时间。以下是18世纪哥尼斯堡七座桥梁的示意图。你可以尝试一下，用每座桥只通过一次的方法来走遍整个城市。“每座桥”意味着不应该有没有通过的桥。“只有一次”意味着不得多次通过每座桥。如果你对这个问题很熟悉，你会知道无论怎么努力尝试这都是不可能的；再努力最终你还是会废弃。Leonhard Euler（莱昂哈德?欧拉）有时，暂时废弃是合理的。欧拉就是这样应对这个问题的。虽然废弃了正面解决问题，但是他选择了去证明“每座桥恰好走过并只走过一遍是不可能的”。让我们假装“像欧拉一样思考”，先来看看“不可能”。图中有四块区域――两个岛屿和两个河岸，还有七座桥梁。先来看看连接岛屿或河岸的桥梁数量中的模式（我们会使用“陆地”来泛指岛屿和河岸）。每块区域连接桥梁的数量只有奇数个的桥梁连接到每块陆地。这就麻烦了。两座桥与陆地的例子在上面的插图中很容易看到，如果你通过一座桥进入一片陆地，那你可以通过走第二座桥离开这片陆地。每当出现第三座桥时，一旦穿过桥梁进入，那就没法走上每座桥且只走一次离开了。如果你试图将这种推理推广到一块陆地上，你可以证明，如果桥梁数量是偶数的话，总有办法离开这块陆地，但如果桥梁数量是奇数，就不能每桥走且只走一次的离开。试着记住这个结论。如果添加一个新的桥梁呢？通过下面这张图，我们可以察看各个陆地所连接的桥的数量变化及其影响。注意新出现的桥现在我们有两个偶数和两个奇数。让我们画一条包含了新桥梁的路线。Wow桥梁的数量是偶数还是奇数至关重要。现在的问题是：我们知道了桥梁数量是否就能够判断问题可不可解？为了解决问题桥的数量必须是偶数吗？欧拉找到了一种方式证明这个问题。而且，更有趣的是，具有奇数个桥梁连接的陆地数量也很重要。欧拉开始将陆地和桥梁“转换”成我们所知道的图。以下是代表哥尼斯堡七桥的图的样子（请注意，我们“暂时”增加的桥并不在图中）：需要特别注意的一点是对问题的概括和抽象。无论何时你解决一个具体的问题，最重要的是归纳类似问题的解决方案。在这个例子中，欧拉的任务是归纳桥梁问题，以便能在未来推广到类似问题上，比如说世界上所有的桥梁问题。可视化还有助于以不同视角来看问题。下面的每张图都表示前面描述的桥梁问题：所以说图形化可以很好地描绘问题，但我们需要的是如何使用图来解决哥尼斯堡问题。察看从圆圈中出来的线的数量。从专业角度而言，我们将称之为“节点”（V），以及连接它们的“边”（E）。V代表节点（vertex），E代表边（edge）。下一个重要的概念就是所谓的节点自由度，即入射（连接）到节点的边的数量。在上面的例子中，与陆地连结的桥的数目可以视为图的节点自由度。欧拉证明了，一次并仅有一次穿过每条边（桥）来遍历图（陆地）严格依赖于节点（陆地）自由度。由这些边组成的路径叫做欧拉路径。欧拉路径的长度是边的数量。有限无向图G（V，E）的欧拉路径是一条使G的每条边出现并且只出现一次的路径。如果G有一条欧拉路径，那么就可以称之为欧拉图。定理：一个有限无向连通图是一个欧拉图，当且仅当只有两个节点有奇数自由度或者所有节点都有偶数自由度。在后一种情况下，曲线图的每条欧拉路径都是一条闭环，前者则不是。左图正好有两个节点具有奇数自由度，右图则是所有节点都是奇数自由度首先，让我们澄清上述定义和定理中的新术语。有限图是具有有限数量的边和节点的图。图可以是有向图也可以是无向图，这是图的有趣特性之一。举个非常流行的关于有向图和无向图的例子，Facebook vs. Twitter。Facebook的友谊关系可以很容易地表示为无向图，因为如果Alice是Bob的朋友，那么Bob也必须是Alice的朋友。 没有方向，都是彼此的朋友。还要注意标记为“Patrick”的节点，它有点特别，因为没有任何连接的边。但“Patrick”点仍然是图的一部分，但在这种情况下，我们会说这个图是不连通的，它是非连通图（与“John”，“Ashot”和“Beth”相同，因为它们与图的其他部分分开）。在连通图中没有不可达的节点，每对节点之间必须有一条路径。与Facebook的例子相对，如果Alice在Twitter上关注Bob，那不需要Bob回粉Alice。所以一个“关注”关系必须有一个方向来指示是谁关注谁，图表示中就是哪个节点（用户）有一个有向边（关注）到另一个节点。现在，知道什么是有限连通无向图后，让我们回到欧拉图：为什么我们首先讨论了哥尼斯堡桥问题和欧拉图呢？通过思考实际问题和上述解决方案，我们触及了图理论的基础概念（节点，边，有向，无向），避免了只有枯燥的理论。然而我们还未完全解决欧拉图和上述问题。我们现在应该转向图的计算机表示，因为这对我们程序员来说是最重要的。通过在计算机程序中表示图，我们能设计一个标记图路径的算法，从而确定它是否是欧拉路径。图表示法：介绍这是一项非常乏味的任务，要有耐心。记得数组和链表之间的竞争吗？如果你需要对元素进行快速拜访，请使用数组；如果你需要对元素进行快速插入/删除等修改，请使用列表。我不相信你会在“如何表示列表”的问题上有困惑。但是就图的表示而言，实际上却有很多麻烦，因为首先需要你决定的是用什么来表示一个图。相信我，你不会喜欢这个进程的。邻接表，邻接矩阵，还是边表？抛个硬币来决定？决定了用什么表示图了吗？我们将从一棵树开始。你应该至少看过一次二叉树（以下不是二叉搜索树）。仅仅因为它由顶点和边组成，它就是一个图。你也许还记得最常见的一棵二叉树（至少在教科书中）的样子。对于已经熟悉“树”的人来说，这段文字可能看起来太细致致了，但我还是要详细解释以确保我们的懂得一致（请注意，我们仍在使用伪代码）。BinTreeNodeApple* root = new BinTreeNodeApple("Green");root-left = new BinTreeNodeApple("Yellow");root-right = new BinTreeNodeApple("Yellow 2");BinTreeNodeApple* yellow_2 = root-yellow_2-left = new BinTreeNodeApple("Almost red");yellow_2-right = new BinTreeNodeApple("Red");如果你不熟悉树，请仔细导语上面的伪代码，然后依照此插图中的步骤操作：颜色只是为了有好的视觉表现虽然二叉树是一个简单的节点“聚集”，每个节点都有左右子节点，但二叉搜索树却由于应用了一个允许快速键查找的简单规矩显得更加有用。二叉搜索树（BST）对各节点排序。你可以自由地使用任何你想要的规矩来实现你的二叉树（尽管可能依据规矩改变它的名字，例如最小堆或最大堆），BST一般满足二分搜索属性（这也是二叉搜索树名字的来源），即“每个节点的值必须大于其左侧子树中的任何值，并且小于其右侧子树中的任何值”。关于“大于”的阐述有个非常有趣的评论。这对于BST的性质也至关重要。当将“大于”更改为“大于或等于”，插入新节点后，BST可以保存重复的值，否则只将保存一个具有相同值的节点。你可以在网上找到关于二叉搜索树非常好的文章，我们不会提供二叉搜索树的完整实现，但为了坚持一致性，我们还是会举例说明一个简单的二叉搜索树。Airbnb房屋查询实例：二叉搜索树树是一种非常实用的数据结构，你可能在项目开始的时候没有打算应用树这种结构，但是不经意间就用到了。让我们来看一个构想的但非常有价值的例子，关于为什么要首先使用二叉搜索树。二叉搜索树中这个名字中包含了“搜索”，所以基础上所有需要快速查找的东西都应该放进二叉搜索树中。应该不代表必须，在编程中最重要的事情就是要牢记用适合的工具解决问题。在许多案例中用庞杂度为O(N)的简单链表查找比庞杂度为O(logN)的二叉搜索树查找更好。通常我们会使用一个库实现BST，最常用的是C++里面的std::set或是std::map，然而在这个教程中，我们完全可以重新造轮子，重写一个BST库（BST几乎可以通过任何通用的编程语言库实现，你可以找到你喜欢的语言的相应文档）。下面是我们将要解决的问题：Airbnb房屋搜索截图如何用一些过滤器尽可能快地依据一些查询语句搜索住房是一个困难的问题；当我们考虑到Airbnb储存了上百万的房源信息后这个问题会变得更困难。所以当用户搜索住房时，他们有机遇接触到数据库中大概四百万个房源记载。当然，网页主页上只能显示有限个排名靠前的住房列表，并且用户几乎不会好奇地去浏览住房列表里百万量级的住房信息。我没有任何关于Airbnb的剖析，但是我们可以用一个在编程中叫做“假设”的强大工具，所以我们假设一个用户最多浏览一千套房源。这里最重要的因素是实时用户数量，因为这会导致数据结构、数据库选择的不同和项目结构的不同。可以很明显的看出，如果只有100个用户，我们一点不必担心，但如果一个国度的实时用户数量远超过百万量级的阙值，我们必须要十分明智地做每一个决定。是的，“每一个”决定都需要明智的决策。这就是为什么公司在服务方面力求卓越而雇佣最好的员工。Google, Facebook, Airbnb, Netflix, Amazon, Twitter还有许多其他的公司，他们需要处理大量的数据，做出正确的选择以通过每秒数以百万的数据来服务数以百万的实时用户，这一切从招聘好的工程师开始。这就是为什么我们程序员在面试中要与数据结构、算法和解决问题的逻辑作奋斗，因为他们所需要工程师需要具有以最快最有效的方法解决大规模问题的能力。现在案例是，一个用户拜访Airbnb主页并且希望找到最适合的房源。我们如何解决这个问题？（注意这是一个后端问题，所以我们不需关怀前端或者网络阻塞或者多个http链接一个http或者Amazon EC2链接主集群等等）。首先，我们已经熟悉了一种强大的编程工具（是假设而不是抽象），让我们从假设我们所处理的数据都能放在内存中。你也可以假设我们的内存已经足够大。多大的内存是足够的呢？这是另外一个好问题。储存真实的数据需要多大的内存，如果我们正在处理四百万单位个数据（假设），而且我们或许知道每个单位的大小，那么我们就可以轻易的算出需要的内存大小，例如，4M＊一个单位的大小。让我们来考虑一个“home”对象和他的特征，事实上，让我们考虑至少一个在解决问题时需要处理的特征（一个“home”就是一个单位）。我们把它表示为C++语言结构的伪代码，你可以很轻松的将它转换成MongoDB架构或者其它你想要的形式，我们只是讨论特征名字和类型（联想为节约空间所使用的二元位域或位集）。// feel free to reorganize this struct to avoid redundant space// usage because of aligning factor// Remark 1: some of the properties could be expressed as enums,// bitset is chosen for as multi-value enum holder.// Remark 2: for most of the count values the maximum is 16// Remark 3: price value considered as integer,// int considered as 4 byte.// Remark 4: neighborhoods property omitted // Remark 5: to avoid spatial queries, we're // using only country code and city name, at this point won't consider // the actual coordinates (latitude and longitude)struct AirbnbHome{ // wide string
uint rating_
// list of photo URLs
string host_
uchar adults_
uchar children_ // max is 5
uchar infants_ // max is 5
bitset3 home_
uchar beds_
uchar bedrooms_
uchar bathrooms_
bitset34 property_
bitset32 host_
bitset3 house_
ushort country_};假设，上面的结构显然不是完美的，还有许多假设和未完成的部分（免责声明里我也说了）。我只是察看Airbnb的过滤器和设计属性列表来满足查找需求。这只是一个例子。现在我们要计算每个AirbnbHome对象需要占用多少内存。名字只是一个支持多种语言标题的wstring，这意味着每个字符会占用2字节（如果我们用其它语言可能不需要考虑字符大小，但是在C++中，char占用1字节，wchar占用2字节）。对于Airbnb住房列表的快速浏览让我们假设住房的名字最多包括100个字符（大多数都在50个字符左右，而不是100），所以我们将假设最大值为100，这就意味着占用不超过200字节的内存。uint是4字节，uchar为1字节，ushort为2字节（这些都是假设）。假设图片用第三方存储服务储存，比如Amazon S3（目前为止，我知道这个假设对于Airbnb来说很可能是真实的，但是这只是一个假设），另外我们有这些照片的链接，考虑到链接没有标准的大小限制，但通常都不会超过2083个字符，所以我们用这个当作链接的最大大小。因为每个房源平均会有5张照片，所以图片最多占用10KB内存。让我们重新考虑，通常存储服务提供的链接有一部分是固定的。例如http(s)://s3.amazonaws.com/bucket/object，这是构建链接时常见的规律，所以我们只需要储存真实图片的ID。让我们假设我们用一种ID生成器来对图片产生20字节长的不重复的ID字符串。那么每张图片的链接就会是这样： https://s3.amazonaws.com/some-know-bucket/unique-photo-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个不同值例如，检查房间里是否有“洗衣机”：bool HasWasher(AirbnbHome* h){
return h-amenities[2];}或者更专业的：const int KITCHEN = 0;const int HEATING = 1;const int WASHER = 2;//...bool HasWasher(AirbnbHome* h){
return (h != nullptr)
h-amenities[WASHER];}bool HasWasherAndKitchen(AirbnbHome* h){
return (h != nullptr)
h-amenities[WASHER]
h-amenities[KITCHEN];}bool HasAllAmenities(AirbnbHome* h, const std::vectorint amenities){
bool has = (h != nullptr);
for (const auto a : amenities) {
has = h-amenities[a];
}}你可以尽可能地改善代码（并且矫正编写的错误），我们只是想强调在这个问题背景下使用位集的思想。同样也适用于“房屋守则”、“住房类型”等。正如上面代码的注释中提到的，我们不会储存经纬度以避免地理地位上的查询，我们会储存国度代码和城市名字来缩小地址的查找范畴（删除掉街道只是为了简化）。国度代码可以用2或3个字符或3个数字表示，我们会用数字化的表示并且用ushort表示每个国度代码。城市往往比国度多，所以我们不能用“城市代码”（尽管我们可以生成一些作为内部使用），我们直接使用真实的城市名称，为每个名字平均预留50字节的内存，对于特殊的城市名比如Taumatawhakatangihangakoauauotamateaturipukakapikimaungahoronukupokaiwhenuakitanatahu (85 个字母），我们最好用另外的布尔变量来表示这个是一个特殊的非常长的城市名字（不要试图读出这个名字）。所以，记住字符串和向量的内存耗费，我们将添加额外的32字节确保最后结构的大小不会超出。我们还会假设我们在64位的系统上工作，尽管我们为int和short选择了最适合的值。// Note the commentsstruct AirbnbHome{ // 200 bytes // 4 bytes // 1 byte
uint rating_ // 4 bytes
// 100 bytes
string host_ // 20 bytes
uchar adults_ // 1 byte
uchar children_ // 1 byte
uchar infants_ // 1 byte
bitset3 home_ // 4 bytes
uchar beds_ // 1 byte
uchar bedrooms_ // 1 byte
uchar bathrooms_ // 1 byte
bitset21 // 4 bytes // 1 byte
bitset20 // 4 bytes
bitset6 // 4 bytes
bitset34 property_ // 8 bytes
bitset32 host_ // 4 bytes, correct me if I'm wrong
bitset3 house_ // 4 bytes
ushort country_ // 2 bytes // 50 bytes};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叉树节点的伪代码是这样的：struct NTreeNode{
vectorNTreeNode*};这个结构只表示这个树的一个节点，整棵树应该是这样的：// almost pseudocodeclass NTree{public:
void Insert(const T);
void Remove(const T);
// lines of omitted codeprivate:
NTreeNode* root_;};这个类模拟一个名为root_树节点。我们可以用它构建任意大小的树。这是树的起始点。为了增加一个新的树节点我们需要分配给它一个内存并将该节点添加到树的根节点上。图与N叉树虽然很像，但稍微有点不同。试着画出来一下。这个是图吗？说不是也是。它跟之前的N叉树是一样的，只是旋转了一下。依据经验来讲，不管何时你看到一棵树，也不管这是一颗苹果树，柠檬树还是二叉搜索树，你都可以确定他也是一个图。所以为图节点（图顶点）设计一个结构，我们可以得出相同的结构：struct GraphNode{
vectorGraphNode* adjacent_};这足以构成一个图吗？当然不能。看看之前的两个图有什么不同。都是图左边插图中的图中的树没有一个“输入”点（更像是一个森林而不是单独的树），相反的是右侧插图中的图没有不可到达的顶点。听起来很熟悉哈。定义：如果每对节点间都有一条路径，那么我们认为这个图是连通的。很明显，在“价格vs房屋”图中并不是每对节点间都有路径（如果从插图中看不出来，就假设价格节点并没有彼此相连吧）。尽管这只是一个例子来解释我们不能构造一个具有单个GraphNode struct的图，但有些情况下我们必须处理像这样的非连通图。看看这个类：class ConnectedGraph{public:
GraphNode* root_;就像N叉树是围绕一个节点（根节点）构建的，一个连通图也是围绕一个根节点构造的。树是“有根”的，也就是说存在一个起始点。连通图可以表示成一个有根树（和几个属性），这已经很明显了，但是要记住即使对于一个连通图，实际表示会因算法不同而异，因问题不同而异。然而考虑到图的基于节点的性质，非连通图可以表示为：class DisconnectedGraphOrJustAGraph{public:
std::vectorGraphNode* all_roots_;};对于像DFS/BFS这样的图遍历，很自然就使用树状表示了。这种表示方式辅助很大。然而，像有效路径跟踪这样的例子就需要不同的表示了。还记得欧拉图吗？为了找到一个图具有“欧拉性”，我们应该在其中找到一个欧拉路径。这意味着通过遍历每条边一次去拜访所有的节点，并且如果遍历结束还有未走过的边，那就说明这个图没有欧拉路径，因此也就不是欧拉图。还有一个更快些的方式，我们可以检查所有节点的自由度（假设每个节点都存有它的自由度），然后依据定义，如果图有个数不等于两个的奇自由度节点，那这个图就不是欧拉图。这个检查行为的庞杂度是O(|V|)，|V|是图中节点的个数。当插入新的边来增加奇/偶自由度时我们可以进行追踪，这个行为庞杂度为O(1)。这是非常快速。不过不用在意，我们只要画一个图就行了，仅此而已。下面的代码表示一个图和返回路径的Trace()函数。// A representation of a graph with both vertex and edge tables// Vertex table is a hashtable of edges (mapped by label)// Edge table is a structure with 4 fields// VELO = Vertex Edge Label Only (e.g. no vertex payloads)class ConnectedVELOGraph {public:
struct Edge {
Edge(const std::string f, const std::string t)
, used(false)
, next(nullptr)
std::string ToString() {
return (from + " - " + to + " [used:" + (used ? "true" : "false") + "]");
ConnectedVELOGraph() {}
~ConnectedVELOGraph() {
vertices_.clear();
for (std::size_t ix = 0; ix
edges_.size(); ++ix) {
delete edges_[ix];
void InsertEdge(const std::string from, const std::string to) {
Edge* e = new Edge(from, to);
InsertVertexEdge_(from, e);
InsertVertexEdge_(to, e);
edges_.push_back(e);
void Print() {
for (auto elem : edges_) {
elem-ToString()
std::vectorstd::string Trace(const std::string v) {
std::vectorstd::
Edge* e = vertices_[v];
while (e != nullptr) {
if (e-used) {
path.push_back(e-from + ":-:" + e-to);
e = vertices_[e-to];
void InsertVertexEdge_(const std::string label, Edge* e) {
if (vertices_.count(label) == 0) {
vertices_[label] =
vertices_[label]-next =
std::unordered_mapstd::string, Edge* vertices_;
std::vectorEdge* edges_;};注意这些无处不在的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左右，但这还是太大了。前面提到过，邻接矩阵过于稀疏，因此想要储存全部有效信息，需要很多额外空间，因此表示与顶点相连的边的邻接表是更佳选择。所谓更佳，是因为邻接矩阵既储存了“已关注”信息，也储存了“未关注”信息，而我们只需要知道关注情况，如下所示：作者：大数据文摘来源：谷普下载}