从七桥问题开始：全面介绍图论及其应用

图论是计算机科学中最重要、最有趣的领域之一，同时也是最容易被误解的。本长文从图论最基础的七桥问题开始，进而结合推特与 Facebook 实例解释无向图与有向图。此外，本文还是用大量的实例解释表征图、搜索树、哈希表等关键概念。最后本文描述了基于深度的搜索和基于广度的搜索等十分流行的图算法。 理解和使用图帮助我们成为更好的程序员。用图思考帮助我们成为最好的，至少我们应该那么思考。图是很多节点 V 和边 E 的集合，即可以表示为有序对 G=(V, E)。 尽管尝试研究过图论，也实现了一些算法，但是我还是非常困惑，因为它实在太无聊了。 事实上，理解一件事物的最佳方式是理解其应用。我们将展示图论的多个应用，最重要的是，有很多插图。 七桥问题 让我们首先从《图论的起源》中的「柯尼斯堡（Königsberg）的七座桥」开始。在加里宁格勒（Kaliningrad）有七座桥，连接着由普雷戈里亚（Pregolya）河分割而成的两个岛屿和两大陆地。 在 18 世纪，这里被称为柯尼斯堡，隶属普鲁士，这一区域有很多桥。当时，有一个与柯尼斯堡的桥相关的脑筋急转弯：如何只穿过桥一次而穿过整个城市。下图为柯尼斯堡七座桥的简化图。 你可以尝试一下，在穿过每座桥仅一次的情况下穿过这个城市。每座桥，意味着所有桥都被穿过；只穿过一次，意味着每座桥不能被穿越两次及以上。如果你对这一问题有所了解，就知道这不可能。 Leonhard Euler  有时候，放弃这一问题是合理的。这就是 Leonhard Euler 的解决方法，他没有试图解决这一问题，而是证明其不可解决。让我们试着去理解 Euler 的内在想法，做到像 Euler 一样思考。首先我们从下图开始。 图中有四块彼此分隔的区域，两个岛屿和两块陆地，以及七座桥。探讨每一区域的桥数是否有一定模式很有趣。 每块区域的桥数 如图所示，每块区域的桥数皆为奇数。如果你只能穿过桥一次，区域有两座桥，那么你就可以进入并离开该区域。 有两座桥的区域的示例 通过图示很容易发现，如果你通过一座桥进入一个区域，那么你也要通过第二座桥离开它。但是当第三座桥出现，则无法只穿过桥一次而离开。所以对于一块区域，当桥数为偶时，则可以每座桥只穿过一次而离开；当桥数为奇时，则不能。请牢记。 让我们再添加一座新桥，如下图所示，看看其是否能解决问题。 注意添加的新桥 现在我们有两个偶数和两个奇数。让我们在添加新桥的图上画一条新路线。 我们已经看到了桥的奇偶数是重要的。这里有个问题：桥的数量解决问题了吗？难道这个数不应该一直是偶数吗？后来发现不是的。这就是 Euler 做的，他发现了一个显示桥数量很重要的办法。更有意思的事，有奇数个连接点的「陆地」也很重要。这时候 Euler 开始把陆地和桥转化成我们看得懂的图。下面是一幅表示了哥尼斯堡七桥（Königsberg bridges）的图（注意：我们「临时」加的桥不在这里）： 抽象化七桥问题 问题的泛化和提取是需要注意的。当你解决一个特定问题时，最重要的是为类似的问题概括答案。在这个实际问题里，Euler 的任务是泛化过桥问题从而在将来可以解决类似的问题。比如：对于世界上所有的桥。可视化也可以帮助我们从另一个角度看问题，如下面的图也全是七桥问题的抽象： 所以，可视化图是解决该问题的好选择，因此我们需要去找出哥尼斯堡七桥问题是怎样被这张图解决的。注意从圈里面向外出来的线。因此我们命名圈为节点（或节点），连接他们的线为边。你也许看到了字母表达法，V 是节点（vertex），E 是边（edge）。 下一个重要的事是所谓节点自由度（Degree），即连接到节点的边数量。在我们上面的例子里，连接陆地和桥的边的数量可以被表达成节点的自由度。 在 Euler 的努力下，他证明了在图上（城市里）每次只走过一条边（桥）并且走过每一条边是严格取决于节点自由度。由这样的边组成的路径被叫做 Euler 路径（Euler path），Euler 路径的长度就是边的数量。 有限无向图 G(V,E) 的 Euler 路径是指 G 的每一个边都只出现一次的路径。如果 G 有一条 Euler 路径，它就被称之 Euler 图。[注释 1] 定理：有且仅有两个确定的节点存在奇数自由度，其它的节点都有偶数自由度，那么该有限无向图为 Euler 图。【1】 左图：有两个节点有奇数自由度的图像。右图：所有节点都有奇数自由度。 首先，让我们分清楚上面定理和理论中的新名词。有限图（Finite graph）是指有限数量的边和节点的图。 图可以为有向的或无向的，这也是图非常有趣的性质。你肯定看到过将 Facebook 和 Twitter 的作为有向图和无向图的例子。Facebook 朋友关系也许可以很简单地表示为一个无向图，因为如果 Alice 是 Bob 的朋友的话，Bob 也必须是 Alice 的朋友。 而且也要注意「Patrick」节点，因为它没有连接一条边（edges）。虽然它还是图的一部分，但在这个案例中我们可以说该图没有连接上，这是个失联图（disconnected graph）（「John」、「Ashot」和「Beth」也是同样的，因为它们是和别的节点都是分离的）。在一个连接的图里没有到达不了的节点，这里必须在每一对节点之间有一条路。 与 Facebook 的例子相反的是，如果 Alice 在 Twitter 上关注了 Bob，Bob 并不需要关注 Alice。所以「关注」关系必须是有向的连接，其表示节点（用户）有一条有向边（关注）连接到其它的节点（用户）。 现在，我们了解了什么是有限无向图，让我们再一次思考 Euler 图： 所以为什么我们最开始就讨论了哥尼斯堡七桥问题和 Euler 图呢？在接触答案之前接触一下问题背后的因素（节点、边、有向、无向）也能避免枯燥的理论方法。我们现在应该更关注于用电脑表示图，因为这是我们最大的兴趣。用电脑程序表示图将使我们设计出一个算法来跟踪图路径（graph path），这样就能发现它是不是 Euler 路径了。 图表征：前言 这是一个很沉闷的任务，要有耐心。记得数组和链表之间的战争吗？用如果你需要快速访问元素就用数组，如果你需要快速插入/删除元素就用链表等。我很难相信你会在像「怎样表示列表」这样的问题上纠结。当然，在图论中真正的表达是非常无聊的，因为首先你应该决定你将怎样确切地表达图。 现在我们以一个树来开始。你肯定已经至少一次见到了二叉树（下面的不是二叉搜索树）。 因为它是由节点和边构成的，所以它就是图。你也要想到一般最常见的二叉树是怎样表示的（至少在教科书上）。 struct BinTreeNode {  T value; // don't bother with template<>  TreeNode* left;  TreeNode* right; }; class BinTree { public:  // insert, remove, find, bla bla private:  BinTreeNode* root_; }; 这个对于已经非常熟悉树的人来说太详细了，但是我必须确保我们在同一阶段。（注意我们还是在用伪代码）。 BinTreeNode* root = new BinTreeNode("Green"); root->left = new BinTreeNode("Yellow"); root->right = new BinTreeNode("Yellow 2"); BinTreeNode* yellow_2 = root->right; yellow_2->left = new BinTreeNode("Almost red"); yellow_2->right = new BinTreeNode("Red"); 如果你不是新手，仔细的读上面的伪代码然后阅读以下图解： 当一个二叉树是简单的节点「集合」，每一个父节点有左子节点和右子节点的节点。二叉树在应用简单规则的时候是非常有意义的，例如允许快速的关键字查找。二叉搜索树（BST）按序储存他们的关键字。我们可以根据任何规则实现二叉树（即使它会根据不同的规则而有不同的名字，比如，min—heap 或者 max——heap），最常见的 BST 规则是它符合二项搜索性质（也是名字的由来），即「任意节点的键值必须比它左边子树的键值要大，比右边子树上的键值要小。「更大」是 BST 重要的本质，当你把它改成「比更大或一样」时，你的 BST 可以在插入新节点时解决复制键值得问题，除此之外它将只保留唯一键值的节点。你可以在网上找到很好的二项树的文章，我们不会提供一个二元搜索树的全面实现，但我们将展示一个简单的二元搜索树。 Airbnb 树是非常有用的数据结构，你也许还没有实现过树型结构，但你也许无意间用过它们。像你注意到的，二叉搜索树（Binary Search Tree）中有「搜索」，简单来说，所有需要快速查找的事，应该被放到二叉搜索树中。「应该」不意味着一定，在编程中最重要的事情是用合适的工具去解决问题。这里有很多案例可以看到简单链表（O(N) 复杂度）搜索相比 BST（O(logN) 复杂度）搜索更受欢迎。一般来说我们可以用一个库来实现一个 BST，但是在这个教程中我们可以重新发明我们自己的轮子（BST 是基本在所有多用途编程语言库都有实现）。接近了「一个真实世界例子」，这里是我们试着去处理的问题： Airbnb 房源搜索一瞥： 怎样用滤波器基于词条尽可能快的搜索房源，这是一项很难的任务。如果我们考虑到 Airbnb 储存了几百万条表格的情况下，这个任务更难了。 所以当用户搜索房源时，他们也许就会「接触」到四百万条数据库中的记录。的确，在网站主页上能够展现的「top listings」有限，而用户对浏览百万条列表也并不感兴趣。我没有任何 Airbnb 的分析记录, 但我们可以用编程语言中叫做「假设」的强大工具，所以我们假设单个用户查看最多 1 千个房源就会发现中意的房源。并且最重要的因子是即时用户的数量，因为它会影响数据结构、数据库和项目构架的选择。就像这看起来的那么明显，如果这里总共有 100 个用户，我们就不用去操心。相反，如果即时用户数量超过了百万级，我们必须去思考每一个决定到底对不对。每个决策都被正确的使用，这是为什么巨头们雇佣最好的人才，为提供卓越的服务而努力的原因（Google、Facebook、Airbnb、Netflix、Amazon、Twitter 和许多其他公司都在处理大量的数据；招聘正确的工程师来做正确的选择，为数百万实时用户每秒处理百万级字节的数据。这就是为什么我们码农纠结于可能遇见的数据结构，算法和问题处理，因为需要的是工程师有能力快速、有效地解决这样大的问题）。 所以在 Airbnb 的案例里，用户浏览了他们的房源主页，Airbnb 试着去过滤房源来找出最适合的。我们怎样处理这个问题呢？（注意这个问题是后端的，所以我们不需要管前端或者网络流量或者 https over http 或者 Amazon EC2 over home cluster 等。首先，因为我们已经熟悉了程序员仓库中最强大的工具（在说假设而不是抽象），我们假设处理的是完全适配 RAM 的数据。然后你也可以假设我们的 RAM 是足够大的。足够大去支持，但这是多大呢？这是另一个非常好的问题。需要多大的内存来存储真正的数据呢？如果我们处理的是四百万单元的数据（还是假设），如果我们大概知道每一个单元的大小，之后我们可以简单地驱动需要的内存，就是 4M*sizeof(one_unit)。考虑下「房源」及其性质（properties），事实上，至少考虑一下处理这一问题必要的性质（一个「房源」是我们的单元）。我们需要用 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 {  wstring name; // wide string  uint price;  uchar rating;  uint rating_count;  vector photos; // list of photo URLs  string host_id;  uchar adults_number;  uchar children_number; // max is 5  uchar infants_number; // max is 5  bitset<3> home_type;  uchar beds_number;  uchar bedrooms_number;  uchar bathrooms_number;  bitset<21> accessibility;  bool superhost;  bitset<20> amenities;  bitset<6> facilities;  bitset<34> property_types;  bitset<32> host_languages;  bitset<3> house_rules;  ushort country_code;  string city; }; 假设。上面的结构不是完美的（很显然），而且这里有很多假设或者不完整的地方，去再读一下免责声明。我只是看了下 Airbnb 的过滤器和应该存在的符合搜索查询的设计性产权表。这只是个例子。现在我们应该能计算每一个 AirbnbHome 对象会在内存中占用多少空间。name 是一个 wstring 来支持多语言的名字/头衔的，这个意味着每一个字符占了 2 字节（我们不想担心字符大小如果我们需要用其他的语言，但在 C++中，char 是 1 字节然后 wchar 是 2 字节）。 快速的看一下 Airbnb 的表可以让我们估计房源的名字可以占到最多 100 个字符（虽然最多的是 50 个左右，而不是 100 个），我们会认为 100 个字符是最多的量，这占了差不多 200 字节的内存。uint 是 4 字节，uchar 是 1 字节,ushort 是 2 字节（还是假设）。假设图片是在储存服务旁边，像 Amazon S3（目前据我所知，这个假设对于 Airbnb 来说是最可能实现的，当然这也是假设）而且我们有这些照片的 URL，而且考虑这里没有 URL 的标准尺寸的限制，但这事实上有一个众所周知的上线-2083 字符，我们将要用这个当成任何 URL 的最大尺寸。所以考虑到这个，平均每个房源有 5 张照片，这可以占到 10Kb 内存。 让我们重新想一下，一般储存用同样的基础 URL 服务，像 http(s)://s3.amazonaws.com// 机器知心