理解和使用圖幫助我們成為更好的程序員。用圖思考幫助我們成為最好的捐名，至少我們應(yīng)該那么思考辨萍。圖是很多節(jié)點 V 和邊 E 的集合，即可以表示為有序?qū)?G=(V, E)湘纵。

盡管嘗試研究過圖論脂崔，也實現(xiàn)了一些算法，但是我還是非常困惑梧喷，因為它實在太無聊了砌左。

事實上脖咐，理解一件事物的最佳方式是理解其應(yīng)用。我們將展示圖論的多個應(yīng)用汇歹，最重要的是屁擅，有很多插圖。

七橋問題

讓我們首先從《圖論的起源》中的「柯尼斯堡（Knigsberg）的七座橋」開始产弹。在加里寧格勒（Kaliningrad）有七座橋派歌，連接著由普雷戈里亞（Pregolya）河分割而成的兩個島嶼和兩大陸地。

在 18 世紀痰哨，這里被稱為柯尼斯堡硝皂，隸屬普魯士，這一區(qū)域有很多橋作谭。當時稽物，有一個與柯尼斯堡的橋相關(guān)的腦筋急轉(zhuǎn)彎：如何只穿過橋一次而穿過整個城市。下圖為柯尼斯堡七座橋的簡化圖折欠。

你可以嘗試一下贝或，在穿過每座橋僅一次的情況下穿過這個城市。每座橋锐秦，意味著所有橋都被穿過咪奖；只穿過一次，意味著每座橋不能被穿越兩次及以上酱床。如果你對這一問題有所了解羊赵，就知道這不可能。

Leonhard Euler

有時候扇谣，放棄這一問題是合理的昧捷。這就是 Leonhard Euler 的解決方法，他沒有試圖解決這一問題罐寨，而是證明其不可解決靡挥。讓我們試著去理解 Euler 的內(nèi)在想法，做到像 Euler 一樣思考鸯绿。首先我們從下圖開始跋破。

圖中有四塊彼此分隔的區(qū)域，兩個島嶼和兩塊陸地瓶蝴，以及七座橋毒返。探討每一區(qū)域的橋數(shù)是否有一定模式很有趣。

每塊區(qū)域的橋數(shù)

如圖所示舷手，每塊區(qū)域的橋數(shù)皆為奇數(shù)拧簸。如果你只能穿過橋一次，區(qū)域有兩座橋聚霜，那么你就可以進入并離開該區(qū)域狡恬。

有兩座橋的區(qū)域的示例

通過圖示很容易發(fā)現(xiàn)珠叔，如果你通過一座橋進入一個區(qū)域，那么你也要通過第二座橋離開它弟劲。但是當?shù)谌鶚虺霈F(xiàn)祷安，則無法只穿過橋一次而離開。所以對于一塊區(qū)域兔乞，當橋數(shù)為偶時汇鞭，則可以每座橋只穿過一次而離開；當橋數(shù)為奇時庸追，則不能霍骄。請牢記。

讓我們再添加一座新橋淡溯，如下圖所示读整，看看其是否能解決問題。

注意添加的新橋

現(xiàn)在我們有兩個偶數(shù)和兩個奇數(shù)咱娶。讓我們在添加新橋的圖上畫一條新路線米间。

我們已經(jīng)看到了橋的奇偶數(shù)是重要的。這里有個問題：橋的數(shù)量解決問題了嗎膘侮？難道這個數(shù)不應(yīng)該一直是偶數(shù)嗎屈糊？后來發(fā)現(xiàn)不是的。這就是 Euler 做的琼了，他發(fā)現(xiàn)了一個顯示橋數(shù)量很重要的辦法逻锐。更有意思的事，有奇數(shù)個連接點的「陸地」也很重要雕薪。這時候 Euler 開始把陸地和橋轉(zhuǎn)化成我們看得懂的圖昧诱。下面是一幅表示了哥尼斯堡七橋（Knigsberg bridges）的圖（注意：我們「臨時」加的橋不在這里）：

抽象化七橋問題

問題的泛化和提取是需要注意的。當你解決一個特定問題時蹦哼，最重要的是為類似的問題概括答案鳄哭。在這個實際問題里，Euler 的任務(wù)是泛化過橋問題從而在將來可以解決類似的問題纲熏。比如：對于世界上所有的橋〕恚可視化也可以幫助我們從另一個角度看問題局劲，如下面的圖也全是七橋問題的抽象：

所以，可視化圖是解決該問題的好選擇奶赠，因此我們需要去找出哥尼斯堡七橋問題是怎樣被這張圖解決的鱼填。注意從圈里面向外出來的線。因此我們命名圈為節(jié)點（或節(jié)點）毅戈，連接他們的線為邊苹丸。你也許看到了字母表達法愤惰，V 是節(jié)點（vertex），E 是邊（edge）赘理。

下一個重要的事是所謂節(jié)點自由度（Degree）宦言，即連接到節(jié)點的邊數(shù)量。在我們上面的例子里商模，連接陸地和橋的邊的數(shù)量可以被表達成節(jié)點的自由度奠旺。

在 Euler 的努力下，他證明了在圖上（城市里）每次只走過一條邊（橋）并且走過每一條邊是嚴格取決于節(jié)點自由度施流。由這樣的邊組成的路徑被叫做 Euler 路徑（Euler path）响疚，Euler 路徑的長度就是邊的數(shù)量。

有限無向圖 G(V,E) 的 Euler 路徑是指 G 的每一個邊都只出現(xiàn)一次的路徑瞪醋。如果 G 有一條 Euler 路徑忿晕，它就被稱之 Euler 圖。[注釋 1]定理：有且僅有兩個確定的節(jié)點存在奇數(shù)自由度银受，其它的節(jié)點都有偶數(shù)自由度践盼，那么該有限無向圖為 Euler 圖◎就粒【1】

左圖：有兩個節(jié)點有奇數(shù)自由度的圖像宏侍。右圖：所有節(jié)點都有奇數(shù)自由度。

首先蜀漆，讓我們分清楚上面定理和理論中的新名詞谅河。有限圖（Finite graph）是指有限數(shù)量的邊和節(jié)點的圖。

圖可以為有向的或無向的确丢，這也是圖非常有趣的性質(zhì)绷耍。你肯定看到過將 Facebook 和 Twitter 的作為有向圖和無向圖的例子。Facebook 朋友關(guān)系也許可以很簡單地表示為一個無向圖鲜侥，因為如果 Alice 是 Bob 的朋友的話褂始，Bob 也必須是 Alice 的朋友。

而且也要注意「Patrick」節(jié)點描函，因為它沒有連接一條邊（edges）崎苗。雖然它還是圖的一部分，但在這個案例中我們可以說該圖沒有連接上舀寓，這是個失聯(lián)圖（disconnected graph）（「John」胆数、「Ashot」和「Beth」也是同樣的，因為它們是和別的節(jié)點都是分離的）互墓。在一個連接的圖里沒有到達不了的節(jié)點必尼，這里必須在每一對節(jié)點之間有一條路。

與 Facebook 的例子相反的是，如果 Alice 在 Twitter 上關(guān)注了 Bob判莉，Bob 并不需要關(guān)注 Alice豆挽。所以「關(guān)注」關(guān)系必須是有向的連接，其表示節(jié)點（用戶）有一條有向邊（關(guān)注）連接到其它的節(jié)點（用戶）券盅。

現(xiàn)在帮哈，我們了解了什么是有限無向圖，讓我們再一次思考 Euler 圖：

所以為什么我們最開始就討論了哥尼斯堡七橋問題和 Euler 圖呢渗饮？在接觸答案之前接觸一下問題背后的因素（節(jié)點但汞、邊、有向互站、無向）也能避免枯燥的理論方法私蕾。我們現(xiàn)在應(yīng)該更關(guān)注于用電腦表示圖，因為這是我們最大的興趣胡桃。用電腦程序表示圖將使我們設(shè)計出一個算法來跟蹤圖路徑（graph path）踩叭，這樣就能發(fā)現(xiàn)它是不是 Euler 路徑了。

圖表征：前言

這是一個很沉悶的任務(wù)翠胰，要有耐心容贝。記得數(shù)組和鏈表之間的戰(zhàn)爭嗎？用如果你需要快速訪問元素就用數(shù)組之景，如果你需要快速插入/刪除元素就用鏈表等斤富。我很難相信你會在像「怎樣表示列表」這樣的問題上糾結(jié)。當然锻狗，在圖論中真正的表達是非常無聊的满力，因為首先你應(yīng)該決定你將怎樣確切地表達圖。

現(xiàn)在我們以一個樹來開始轻纪。你肯定已經(jīng)至少一次見到了二叉樹（下面的不是二叉搜索樹）嚎研。

因為它是由節(jié)點和邊構(gòu)成的橡羞，所以它就是圖愕贡。你也要想到一般最常見的二叉樹是怎樣表示的（至少在教科書上）创南。

struct BinTreeNode{T value; // don't bother with template<>?TreeNode* left;TreeNode* right;};class BinTree{public:?// insert, remove, find, bla blaprivate:BinTreeNode* root_;};

這個對于已經(jīng)非常熟悉樹的人來說太詳細了，但是我必須確保我們在同一階段崇众。（注意我們還是在用偽代碼）掂僵。

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");

如果你不是新手，仔細的讀上面的偽代碼然后閱讀以下圖解：

當一個二叉樹是簡單的節(jié)點「集合」顷歌，每一個父節(jié)點有左子節(jié)點和右子節(jié)點的節(jié)點看峻。二叉樹在應(yīng)用簡單規(guī)則的時候是非常有意義的，例如允許快速的關(guān)鍵字查找衙吩。二叉搜索樹（BST）按序儲存他們的關(guān)鍵字。我們可以根據(jù)任何規(guī)則實現(xiàn)二叉樹（即使它會根據(jù)不同的規(guī)則而有不同的名字溪窒，比如坤塞，min—heap 或者 max——heap）冯勉，最常見的 BST 規(guī)則是它符合二項搜索性質(zhì)（也是名字的由來），即「任意節(jié)點的鍵值必須比它左邊子樹的鍵值要大摹芙，比右邊子樹上的鍵值要小灼狰。「更大」是 BST 重要的本質(zhì)浮禾，當你把它改成「比更大或一樣」時交胚，你的 BST 可以在插入新節(jié)點時解決復(fù)制鍵值得問題，除此之外它將只保留唯一鍵值的節(jié)點盈电。你可以在網(wǎng)上找到很好的二項樹的文章蝴簇，我們不會提供一個二元搜索樹的全面實現(xiàn)，但我們將展示一個簡單的二元搜索樹匆帚。

Airbnb

樹是非常有用的數(shù)據(jù)結(jié)構(gòu)熬词，你也許還沒有實現(xiàn)過樹型結(jié)構(gòu)，但你也許無意間用過它們吸重。像你注意到的互拾，二叉搜索樹（Binary Search Tree）中有「搜索」，簡單來說嚎幸，所有需要快速查找的事颜矿，應(yīng)該被放到二叉搜索樹中〖稻В「應(yīng)該」不意味著一定骑疆，在編程中最重要的事情是用合適的工具去解決問題。這里有很多案例可以看到簡單鏈表（O(N) 復(fù)雜度）搜索相比 BST（O(logN) 復(fù)雜度）搜索更受歡迎车遂。一般來說我們可以用一個庫來實現(xiàn)一個 BST封断，但是在這個教程中我們可以重新發(fā)明我們自己的輪子（BST 是基本在所有多用途編程語言庫都有實現(xiàn)）。接近了「一個真實世界例子」舶担，這里是我們試著去處理的問題：

Airbnb 房源搜索一瞥：

怎樣用濾波器基于詞條盡可能快的搜索房源坡疼，這是一項很難的任務(wù)。如果我們考慮到 Airbnb 儲存了幾百萬條表格的情況下衣陶，這個任務(wù)更難了柄瑰。

所以當用戶搜索房源時，他們也許就會「接觸」到四百萬條數(shù)據(jù)庫中的記錄剪况。的確教沾，在網(wǎng)站主頁上能夠展現(xiàn)的「top listings」有限，而用戶對瀏覽百萬條列表也并不感興趣译断。我沒有任何 Airbnb 的分析記錄, 但我們可以用編程語言中叫做「假設(shè)」的強大工具授翻，所以我們假設(shè)單個用戶查看最多 1 千個房源就會發(fā)現(xiàn)中意的房源。并且最重要的因子是即時用戶的數(shù)量，因為它會影響數(shù)據(jù)結(jié)構(gòu)堪唐、數(shù)據(jù)庫和項目構(gòu)架的選擇巡语。就像這看起來的那么明顯，如果這里總共有 100 個用戶淮菠，我們就不用去操心男公。相反，如果即時用戶數(shù)量超過了百萬級合陵，我們必須去思考每一個決定到底對不對枢赔。每個決策都被正確的使用，這是為什么巨頭們雇傭最好的人才拥知，為提供卓越的服務(wù)而努力的原因（Google踏拜、Facebook、Airbnb举庶、Netflix执隧、Amazon、Twitter 和許多其他公司都在處理大量的數(shù)據(jù)户侥；招聘正確的工程師來做正確的選擇镀琉，為數(shù)百萬實時用戶每秒處理百萬級字節(jié)的數(shù)據(jù)。這就是為什么我們碼農(nóng)糾結(jié)于可能遇見的數(shù)據(jù)結(jié)構(gòu)蕊唐，算法和問題處理屋摔，因為需要的是工程師有能力快速、有效地解決這樣大的問題）替梨。

所以在 Airbnb 的案例里钓试，用戶瀏覽了他們的房源主頁，Airbnb 試著去過濾房源來找出最適合的副瀑。我們怎樣處理這個問題呢弓熏？（注意這個問題是后端的，所以我們不需要管前端或者網(wǎng)絡(luò)流量或者 https over http 或者 Amazon EC2 over home cluster 等糠睡。首先挽鞠，因為我們已經(jīng)熟悉了程序員倉庫中最強大的工具（在說假設(shè)而不是抽象），我們假設(shè)處理的是完全適配 RAM 的數(shù)據(jù)狈孔。然后你也可以假設(shè)我們的 RAM 是足夠大的信认。足夠大去支持，但這是多大呢均抽？這是另一個非常好的問題嫁赏。需要多大的內(nèi)存來存儲真正的數(shù)據(jù)呢？如果我們處理的是四百萬單元的數(shù)據(jù)（還是假設(shè)）油挥，如果我們大概知道每一個單元的大小潦蝇，之后我們可以簡單地驅(qū)動需要的內(nèi)存款熬，就是 4M*sizeof(one_unit)』さ考慮下「房源」及其性質(zhì)（properties）华烟，事實上，至少考慮一下處理這一問題必要的性質(zhì)（一個「房源」是我們的單元）持灰。我們需要用 C++結(jié)構(gòu)偽代碼來表示一些問題，你可以簡單地將他們轉(zhuǎn)化為一個 MongoDB 略圖目標或者任何你想要的形式, 我們只討論性質(zhì)的名字和類別负饲。（試著去想象這是在空間經(jīng)濟里用字位段或者位集合）

// 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;};

假設(shè)堤魁。上面的結(jié)構(gòu)不是完美的（很顯然），而且這里有很多假設(shè)或者不完整的地方返十，去再讀一下免責聲明妥泉。我只是看了下 Airbnb 的過濾器和應(yīng)該存在的符合搜索查詢的設(shè)計性產(chǎn)權(quán)表。這只是個例子《纯樱現(xiàn)在我們應(yīng)該能計算每一個 AirbnbHome 對象會在內(nèi)存中占用多少空間盲链。name 是一個 wstring 來支持多語言的名字/頭銜的，這個意味著每一個字符占了 2 字節(jié)（我們不想擔心字符大小如果我們需要用其他的語言迟杂，但在 C++中刽沾，char 是 1 字節(jié)然后 wchar 是 2 字節(jié)）。

快速的看一下 Airbnb 的表可以讓我們估計房源的名字可以占到最多 100 個字符（雖然最多的是 50 個左右排拷，而不是 100 個）侧漓，我們會認為 100 個字符是最多的量，這占了差不多 200 字節(jié)的內(nèi)存监氢。uint 是 4 字節(jié)布蔗，uchar 是 1 字節(jié),ushort 是 2 字節(jié)（還是假設(shè)）。假設(shè)圖片是在儲存服務(wù)旁邊浪腐，像 Amazon S3（目前據(jù)我所知纵揍，這個假設(shè)對于 Airbnb 來說是最可能實現(xiàn)的，當然這也是假設(shè)）而且我們有這些照片的 URL议街，而且考慮這里沒有 URL 的標準尺寸的限制泽谨，但這事實上有一個眾所周知的上線-2083 字符，我們將要用這個當成任何 URL 的最大尺寸傍睹。所以考慮到這個隔盛，平均每個房源有 5 張照片，這可以占到 10Kb 內(nèi)存拾稳。

讓我們重新想一下吮炕，一般儲存用同樣的基礎(chǔ) URL 服務(wù)，像 http(s)://s3.amazonaws.com/<bucket>/<object>访得，這樣就是說龙亲，這里有一個基本的模式來建 URL 并且我們只需要儲存真實照片的 ID陕凹，讓我們說用了一些獨特的 ID 生成器，可以為圖片對象返回 20 字節(jié)長度的獨特的字符 ID鳄炉，看起來像 https://s3.amazonaws.com/some-know-bucket/杜耙。這提供了我們好多空間效率，所以為了 5 張照片儲存字符 ID拂盯，我們只需要 100 字節(jié)內(nèi)存佑女。

同樣的「手段」可以用 host_id 來做，就是說谈竿，房主的用戶 ID团驱，占了 20 字節(jié)的內(nèi)存（實際上我們可以就讓用戶用數(shù)字 ID，但考慮到一些 DB 系統(tǒng)像 MongoDB 有非常詳細的 ID 生成器空凸，我們假設(shè) 20 字節(jié)的字符 ID 是「中位」長度嚎花，已經(jīng)可以用很小的改動就能適用于大部分 DB 系統(tǒng)了。Mongo 的 ID 長度是 24 字節(jié)）呀洲。最后紊选，我們將用一個最多 4 字節(jié) 32 位大小對象的位集合和一個比 32 位大的 64 位小的位集合一起作為一個 8 字節(jié)的獨享。注意這是個假設(shè)道逗。我們在這個例子里為了所有的表達了枚舉的性質(zhì)用了位集合兵罢，但位集合可以取不止一個值，換種說法這是一種多種選擇的多選框憔辫。

舉例趣些，每一個 Airbnb 房源都有一些便利工具列表，比如：「熨斗」贰您、「洗衣機」坏平、「電視」、「wifi」锦亦、「掛衣架」舶替、「煙霧探測器」甚至「適用于筆記本電腦的書桌」等。這里也許有超過 20 種便利工具杠园，我們用 20 這個數(shù)字是因為 Airbnb 網(wǎng)站上可以用 20 個選項過濾顾瞪。如果一個房源有所有的上述便利措施（在截圖中看），我們在對應(yīng)的位集合的位置上標注 1 就好抛蚁。

位集合（Bitset）允許儲存 20 個不同數(shù)據(jù)而只用 20 個字節(jié)陈醒。

舉例，檢查一個房源有沒有「洗衣機」：

bool HasWasher(AirbnbHome* h){return h->amenities[2];}

或者更專業(yè)一點：

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::vector& amenities){?bool has = (h != nullptr);?for (const auto a : amenities) {?has &= h->amenities[a];?}return has;}

你可以修正代碼或修復(fù)編譯錯誤瞧甩，我們只想強調(diào)該問題背后用向量表征特征的觀念钉跷。同樣的觀念可以用在「入住守則」、「房間類型」和其它特征上肚逸。

最后爷辙，對于國家編碼和城市名彬坏。像上面代碼注釋中提到的一樣（看標注），我們不會儲存經(jīng)緯度來避免地理-空間問題膝晾，我們儲存國家代碼和城市名字來縮小用地名搜索的范圍（為了簡介省略街名栓始，原諒我）。國家代碼可以被用兩個字符血当，3 個字符或者 3 個數(shù)字來表示幻赚，我們會用 ushort 儲存數(shù)字表達。不幸的是歹颓，城市比國家多了太多坯屿，所以我們不能使用「城市編碼」，我們只會儲存真實的城市名巍扛，保留平均 0 為 50 字節(jié)的城市名字和特別的名字。我們最好用一個附加的布爾變量來表示這是不是一個特別長的名字乏德，所以我們將會加上附加的 32 字節(jié)來保證最終的結(jié)構(gòu)大小撤奸。我們也假設(shè)在 64 位系統(tǒng)上工作，即使我們?yōu)?int 何 short 選擇了非常緊湊的值喊括。

// Note the commentsstruct AirbnbHome{wstring name; // 200 bytes?uint price; // 4 bytes?uchar rating; // 1 byte?uint rating_count; // 4 bytesvector photos; // 100 bytes?string host_id; // 20 bytes?uchar adults_number; // 1 byte?uchar children_number; // 1 byte?uchar infants_number; // 1 byte?bitset<3> home_type; // 4 bytes?uchar beds_number; // 1 byte?uchar bedrooms_number; // 1 byte?uchar bathrooms_number; // 1 byte?bitset<21> accessibility; // 4 bytes?bool superhost; // 1 byte?bitset<20> amenities; // 4 bytes?bitset<6> facilities; // 4 bytes?bitset<34> property_types; // 8 bytes?bitset<32> host_languages; // 4 bytes, correct me if I'm wrong?bitset<3> house_rules; // 4 bytes?ushort country_code; // 2 bytes?string city; // 50 bytes};

所以胧瓜，420 字節(jié)加上 32 個多出的字節(jié)，若我們四舍五入到 500 字節(jié)郑什。所以每一個對象「home」最多占 500 字節(jié)府喳，并且對于所有房源列表，500 字節(jié)*4 百萬=1.86Gb ~2Gb蘑拯。我們在搭建結(jié)構(gòu)時做了很多假設(shè)钝满，讓儲存在內(nèi)存中更便宜。無論我們對這數(shù)據(jù)做什么申窘，我們需要至少 2Gb 內(nèi)存弯蚜。如果你無聊，忍著剃法，我們剛開始碎捺。

現(xiàn)在是任務(wù)最難的地方了，為這個問題選擇合適的數(shù)據(jù)結(jié)構(gòu)（來盡可能有效的過濾表）不是最難的任務(wù)贷洲。最難的是（對我而言）按照一系列濾波器搜索列表收厨。如果只有一個搜索鍵（key）（即只有一個濾波器），我們可以很輕易地解決這個問題优构。假設(shè)用戶只關(guān)心價格诵叁，我們需要的只是在給定的范圍以價格下降的順序找到 Airbnbhome 對象（合適的家）。如果我們要用二元搜索樹來解決這個問題俩块，則可按下圖形式執(zhí)行黎休。

如果需要遍歷所有的 4 百萬個對象浓领，這搜索樹會長得很大很大。另外势腮，需要占用的內(nèi)存也會越來越多联贩。這只是因為我們用了二元搜索數(shù)來存儲對象，每一個樹節(jié)點給它的左右子樹兩個額外的指針捎拯，加起來是每個子指針有 8 個額外的比特（假設(shè)是 64 位系統(tǒng)）泪幌。對于 400 百萬節(jié)點它加起來就是 62Mb，對于 2Gb 對象的數(shù)據(jù)來說是很小的署照，但還是不能輕易地「忽略」祸泪。

目前為止，上面展示的樹表明了任何物品都可以很輕易地在 O（logN）復(fù)雜度內(nèi)被找到建芙。如果你對這些概念不熟悉没隘，我們會在接下來解釋清楚，或者跳過復(fù)雜度討論的副章節(jié)禁荸。

算法復(fù)雜度：我們在這里快速地簡要介紹右蒲，在之后的文章「Algorithmic Complexity and Software Performance: the missing manual」我會進行詳細的解釋。在大部分情況里赶熟，找到一個算法的「大 O」復(fù)雜度是簡單的瑰妄。首先要注意到，我們總是考慮最差的情況映砖，即：一個算法要最多算多少次才能產(chǎn)生一個合適的結(jié)果（用來解決問題）间坐。

假設(shè)一個有 100 個元素的未排序數(shù)列，要做多少次的比較才能讓它找到任意的元素邑退，這里也要考慮到需要的元素可能缺失的情況竹宋？它最多需要與匹配的數(shù)字比較 100 次才能發(fā)現(xiàn)，盡管有時候第一個在數(shù)列中的元素就是要找的數(shù)字（意味著單次比較就找到答案了）瓜饥，但我們只考慮最差的可能情況（元素可能丟失了或者在最后的位置）逝撬。

計算算法復(fù)雜度的重點是找到運算次數(shù)與輸入規(guī)模之間的依賴關(guān)系，舉例來說乓土，上面的數(shù)列有 100 個元素宪潮，運算的次數(shù)也是 100，如果數(shù)列的數(shù)量（輸入）增長到 1423趣苏，運算次數(shù)也會增長到 1423（最差的情況）狡相。所以，輸入和運算次數(shù)之間的關(guān)系在這里是非常清晰的食磕，它也被叫做線性關(guān)系尽棕，運算次數(shù)和數(shù)列的增長一樣快。增長是復(fù)雜度的關(guān)鍵彬伦，我們說在一個未排序的數(shù)列中搜索需要 O（N）次運算滔悉，來強調(diào)尋找它需要最多用 N 次運算伊诵，（甚至最多到 N 的常數(shù)倍數(shù)運算，比如 3N 次）回官。另一方面曹宴，訪問數(shù)列上的任意元素只需要常數(shù)時間，比如 O（1）歉提。這是因為數(shù)列的結(jié)構(gòu)是一個連續(xù)結(jié)構(gòu)笛坦，并且包含相同類型的元素，所以訪問特定的元素只需要計算它與數(shù)列第一個元素的相對位置苔巨。

有一點非常明確版扩，二元搜索樹按排序順序保存其節(jié)點。那么在二元搜索樹中搜索元素的算法復(fù)雜度是多少呢侄泽？我們應(yīng)該在最壞的情況下計算查找元素所需的操作次數(shù)礁芦。

見上圖，當我們開始在根部搜索時悼尾，第一次匹配可能會導致三種情況：

（1）目標節(jié)點被發(fā)現(xiàn)宴偿；

（2）如果要找的值小于節(jié)點的值，則匹配將繼續(xù)到節(jié)點的左子樹诀豁；

（3）如果要找的值大于節(jié)點的值，則匹配將繼續(xù)到節(jié)點的右子樹窥妇。

在每一步中我們都把節(jié)點的數(shù)量減半舷胜。在二元搜索樹中查找元素所需的操作數(shù)等于樹的高度。樹的高度是最長路徑上節(jié)點的數(shù)量活翩。在這一案例中烹骨，高度是 4。所以高度等于 logN+1（底數(shù)為 2）材泄，搜索復(fù)雜度是 O（logN+1）=O（logN）沮焕。這意味著在 4 百萬個節(jié)點里搜索元素需要 log1000000=~22 次比較（最差的情況）。

回到樹搜索的問題拉宗，二元搜索樹中的元素搜索時間為 O（logN）峦树。為什么不使用哈希表？哈希表有常數(shù)的訪問時間旦事，這使得在幾乎任何地方使用哈希表都是合理的魁巩。

在該問題中，我們必須考慮一個重要的需求姐浮，即執(zhí)行范圍搜索如孝，如搜索價格區(qū)間在$80 到 $162 之間的房源赞季。在二元搜索樹的情況下，獲取區(qū)間中所有節(jié)點很簡單术吝，只需對樹執(zhí)行順序遍歷，保存計數(shù)即可熏挎。而哈希表的計算稍微昂貴，在這種情況下使用堅持二元搜索樹更好一些。盡管還存在另一個因素窗悯，使我們需要重新考慮哈希表：密度。價格不會「一直」上漲甩恼，大部分房源處于固定的價格區(qū)間內(nèi)蟀瞧。截圖中的柱狀圖顯示了價格的真實分布，數(shù)百萬房源處于同一區(qū)間（$18—$212）条摸，它們具備同樣的平均價格悦污。簡單的數(shù)組可能起到很好的效果。假設(shè)數(shù)組的索引是價格钉蒲，則我們能夠在（幾乎）常數(shù)時間內(nèi)獲取任意價格區(qū)間切端。如下圖所示：

就像一個哈希表，我們通過房源的價格來匹配每一套房子顷啼。所有具有相同價格的房源都歸入單獨的二元搜索樹踏枣。如果我們存儲房源的 ID 而不是上面定義的完整對象（AirbnbHome 結(jié)構(gòu)），也可以節(jié)省一些空間钙蒙。最可能的情況是將所有房源的完整對象保存在哈希表茵瀑，并將房源 ID 映射到房源的完整對象中，以及保存另一個哈希表（或更好的躬厌，一個數(shù)組）马昨，該哈希表將價格與房源 ID 進行映射。因此扛施，當用戶請求價格范圍時鸿捧，我們從價格表中獲取房源 ID，將結(jié)果裁剪成固定大懈碓（即分頁匙奴，通常在一頁上顯示 10-30 個項目），然后使用每個房源 ID 獲取完整的房源對象妄荔。請記得泼菌，要注意平衡。平衡對二元搜索樹至關(guān)重要懦冰，因為它是在 O（logN）內(nèi)完成樹操作的唯一保證灶轰。當你按排序順序插入元素時，二元搜索樹不平衡的問題就會很明顯刷钢，最終笋颤，樹將變成連接列表，這顯然會導致線性時間復(fù)雜度。現(xiàn)在假設(shè)我們所有的搜索樹都是完美平衡的伴澄。再看看上面的圖赋除。每個數(shù)組元素代表一棵大樹。如果我們改變這個樹非凌，變成圖呢举农？

這是一個「更接近真實」的圖。這個圖展示了最隱蔽的數(shù)據(jù)結(jié)構(gòu)和圖敞嗡，帶領(lǐng)我們到了（下文）颁糟。

圖表征：進階

圖論的缺點是缺乏單獨定義，這就是為什么你無法在庫中找到 std::graph喉悴。我們已經(jīng)嘗試過表示「特別的」圖 BST棱貌。重點在于，樹是圖箕肃，但圖未必是樹婚脱。最后一張示例圖表明在一個抽象圖下面有很多樹，「價格 vs 房源」和一些節(jié)點的類型不同勺像，價格只有價格值的圖節(jié)點障贸，表示滿足特定價格的房源 ID（房源節(jié)點）的樹。這很像混合數(shù)據(jù)結(jié)構(gòu)吟宦，不同于我們在教科書示例中見到的簡單圖形篮洁。圖表示的重點：不存在固定、「權(quán)威」的圖表示結(jié)構(gòu)（這與 BST 不同殃姓，后者用左／右子指針代表基于節(jié)點的特定表示嘀粱，盡管你可以用一個數(shù)組表示 BST）。你可以用最便捷的方式表示一個圖辰狡，重點在于你把它「看作」是圖÷⒎郑「看圖」的意思是使用適用于圖的算法宛篇。

N-ary 樹更像是模擬一個圖。

首先薄湿，將 N-ary 樹節(jié)點表示為：

struct NTreeNode{T value;?vector children;};

該結(jié)構(gòu)僅表示樹的一個節(jié)點叫倍，完整的樹如下所示：

// almost pseudocodeclass NTree{public:void Insert(const T&);?void Remove(const T&);?// lines of omitted codeprivate:?NTreeNode* root_;};

該類別是圍繞單個樹節(jié)點 root_ 的抽象。我們可以用它構(gòu)建任意大小的樹豺瘤。這是樹的起點吆倦。如果要添加新的樹節(jié)點，我們就要為其分配內(nèi)存坐求，將該節(jié)點添加至樹的根節(jié)點處蚕泽。

圖與 N-ary 樹很像，只有細微的不同。我們來看一下须妻。

這是圖嗎仔蝌？我認為，是的荒吏。但這幅圖與前面的 N-ary 相同敛惊，只不過稍微旋轉(zhuǎn)了一下。只要你看到一棵樹绰更，無論它是蘋果樹瞧挤、檸檬樹，還是二叉搜索樹儡湾，你都可以確定它也是一張圖特恬。因此，通過設(shè)計圖節(jié)點（圖節(jié)點）結(jié)構(gòu)盒粮，我們能夠提出同樣的結(jié)構(gòu)：

struct GraphNode{T value;?vector adjacent_nodes;};

這樣可以創(chuàng)建圖嗎鸵鸥？還不夠〉ぶ澹看下面兩幅圖妒穴，找不同：

二者都是圖

左側(cè)的圖沒有可以「進入」的點（與其說是樹，它更像森林）摊崭，相反讼油，右側(cè)的圖沒有不可達的節(jié)點，聽起來很熟悉呢簸。

如果圖中任意兩點都是連通的矮台，那么該圖被稱作連通圖。

雖然圖中不明顯根时，但是我們假設(shè)價格不能互相連接瘦赫，那么在「價格 vs 房源」圖中并不是每對節(jié)點之間都有路徑相連，這說明我們無法使用單個 GraphNode 結(jié)構(gòu)構(gòu)建圖的例子蛤迎，但是在很多案例中我們必須這樣處理非連通圖确虱。看下面這個類別：

class ConnectedGraph{public:// APIprivate:?GraphNode* root_;};

類似圍繞單個節(jié)點（根節(jié)點）構(gòu)建的 N-ary 樹替裆，連通圖也可以圍繞根節(jié)點構(gòu)建校辩。樹有「根」，即它們有起始點辆童。連通圖可以用帶有根節(jié)點的樹來表示（當然還有其他屬性）宜咒，不過要注意，實際的表示可能會隨著算法或具體問題發(fā)生變化把鉴。但是故黑，考慮基于節(jié)點的圖本質(zhì)，非連通圖可以按照下面的方式來表示：

class DisconnectedGraphOrJustAGraph{public:// APIprivate:std::vector all_roots_;};

樹狀圖可以清晰自然地表示 DFS/BFS 這樣的圖遍歷。但是倍阐，高效路徑追蹤等需要不同的表示方法概疆。還記得歐拉圖嗎？為了追蹤圖的「eulerness」（真實性）峰搪，我們應(yīng)該追蹤圖中的歐拉路徑岔冀。這意味著遍歷每個邊一次就要訪問所有節(jié)點；如果追蹤結(jié)束后我們?nèi)杂形幢闅v的邊概耻，則該圖沒有歐拉路徑使套，因此它不是歐拉圖。更快的方法是：檢查節(jié)點的度（假設(shè)每條邊都保存了度）鞠柄，如定義所述侦高，如果圖的節(jié)點度是奇數(shù)，則它不是歐拉圖厌杜。該檢查的復(fù)雜度是 O(|V|)奉呛，其中 |V| 是圖節(jié)點的數(shù)量。我們可以在插入新的邊緣的同時追蹤節(jié)點的奇數(shù)／偶數(shù)度夯尽，同時插入新的邊以增加奇數(shù)／偶數(shù)度檢查的復(fù)雜度到 O(1)瞧壮。下面介紹圖表示和返回路徑的 Trace() 函數(shù)。

// 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)?: from(f)?, to(t)?, used(false)?, next(nullptr){}?std::string ToString() {?return (from + " - " + to + " [used:" + (used ? "true" : "false") + "]");?}?std::string from;?std::string to;?bool used;?Edge* next;?};ConnectedVELOGraph() {}?~ConnectedVELOGraph() {?vertices_.clear();?for (std::size_t ix = 0; ix < edges_.size(); ++ix) {?delete edges_[ix];?}?}public: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);?}public:?void Print() {?for (auto elem : edges_) {std::cout << elem->ToString() << std::endl;?}?}?std::vector Trace(const std::string& v) {?std::vector path;?Edge* e = vertices_[v];?while (e != nullptr) {?if (e->used) {?e = e->next;?} else {?e->used = true;?path.push_back(e->from + ":-:" + e->to);?e = vertices_[e->to];?}?}return path;?}private:?void InsertVertexEdge_(const std::string& label, Edge* e) {?if (vertices_.count(label) == 0) {?vertices_[label] = e;?} else {vertices_[label]->next = e;?}?}private:?std::unordered_map vertices_;?std::vector edges_;};

注意 bug匙握，bug 到處都是咆槽。該代碼包含大量假設(shè)，比如標簽圈纺，我們可以通過節(jié)點理解字符串標簽秦忿，確保你可以將其更新成任意事物。接下來蛾娶，是命名灯谣。如注釋中所述，VELOGraph 僅適用于 Vertex Edge Label Only Graph蛔琅。重點在于酬屉，該圖表示包括一個將節(jié)點標簽映射至節(jié)點關(guān)聯(lián)邊的表、一個包含與邊相連的兩個節(jié)點的邊列表揍愁，和一個僅用于 Trace() 函數(shù)的 flag。查看 Trace() 函數(shù)實現(xiàn)杀饵，它使用邊的 flag 來標記已經(jīng)遍歷過的邊（在任意 Trace() 調(diào)用之后應(yīng)該重置 flag）莽囤。

示例：Twitter

另一種表示叫做相鄰矩陣，它在有向圖中有用切距，就像我們在 Twitter 關(guān)注圖中所使用的那樣朽缎。

有向圖

推特案例中有 8 個節(jié)點，所以我們需要使用|V|x|V|的二維矩陣表征這個圖（其中 |V|分別代表行數(shù)和列數(shù)）。如果從 v 到 u 有一條有向邊话肖，那么我們稱矩陣的元素 [v][u] 為真北秽，否則為假。

如你所見最筒，這是一個十分稀疏的矩陣贺氓，其中的值代表是否有單向連接路徑。如果我們需要了解 Patrick 是否關(guān)注了 Bob 的推特床蜘，那么我們只需要查看矩陣中 ["Patrick"]["Sponge Bob"] 的值是不是等于 1辙培。而要查看 Ann 推特的關(guān)注者，我需要獲得「Ann」的整個列邢锯；同樣查看 Sponge Bob 正在關(guān)注的人只需要查看「Sponge Bob」的行就行扬蕊。此外，鄰接矩陣（Adjacency matrix）可以用來描述無向圖丹擎，它不會在 v 到 u 的邊選擇值「0 或 1」來表示是否有連接尾抑，它會同時設(shè)置兩個方向的值都為 1，即 adj_matrix[v][u] = 1 和 adj_matrix[u][v] = 1蒂培。因此再愈，無向圖的鄰接矩陣為對稱矩陣。

注意毁渗，在通常情況下我們在鄰接矩陣中并不會只儲存 0 和 1践磅，我們可以儲存一些更具信息的值，例如邊權(quán)重等灸异。最好的案例可能是帶有距離信息的地圖府适。

上圖表示了 Patrick 和 Sponge Bob 等人之間的距離（也稱為加權(quán)圖）。如果節(jié)點間沒有沒有直接路徑肺樟，那么我們就把它設(shè)為無窮大檐春，它既不意味著根本沒有路徑，也不意味著一定有路徑么伯。它可以在應(yīng)用算法搜索兩個節(jié)點間路徑時定義疟暖。當然，我們還有更好的方法來儲存節(jié)點和邊之間的關(guān)系田柔，如關(guān)聯(lián)矩陣俐巴。

盡管鄰接矩陣對推特關(guān)注關(guān)系有很好的表征，但將 3 億用戶（每月活躍用戶）儲存在矩陣中需要 300*300*1（百萬字節(jié)/布爾值）的儲存空間硬爆。也就是約有 82000Tb（Terabyte）或需要 1024 * 82000 Gb 的儲存空間欣舵。BitBoard 可以幫助我們減少一些空間需求，大約可以降低到 10000Tb缀磕，但還是太大缘圈。如上所述劣光，鄰接矩陣稀疏要求我們提供比實際需求更多的空間，這也就是為什么邊的列表映射到節(jié)點可能會很有用糟把。重點是绢涡，鄰接矩陣允許保持關(guān)注和不關(guān)注的信息，而我們需要的僅僅是知道如下內(nèi)容：

鄰接矩陣與鄰接列表

右圖表示鄰接列表（adjacency list）遣疯，每個列表描述了圖中的一組鄰近節(jié)點雄可。在圖表中，我們突出了哈希表的用法另锋，因為任何節(jié)點的訪問復(fù)雜度都是 O（1）滞项。而且對于鄰近節(jié)點列表，我們并沒有提到任何具體的數(shù)據(jù)結(jié)構(gòu)夭坪，也不會從列表轉(zhuǎn)化為向量文判。重點是，如果要確定 Patrick 是否關(guān)注 Liz室梅，我們應(yīng)該遍歷哈希表中每一個元素（常數(shù)時間）戏仓，而鄰近矩陣需要查看每一個與 Liz 相關(guān)的元素（線性時間）。線性時間在這一點上并不是那么糟亡鼠，因為我們經(jīng)需要循環(huán)與 Patrick 相關(guān)的固定數(shù)目的節(jié)點赏殃。

如果我們用空間復(fù)雜度表示推特，這需要 3 億個哈希表記錄间涵，每個記錄指向一個向量（選擇向量以避免鏈表的左/右指針所產(chǎn)生的內(nèi)存開銷）仁热。此外，雖然沒有統(tǒng)計數(shù)據(jù)勾哩，但平均推特關(guān)注的人數(shù)是 707 個抗蠢。所以如果我們考慮每個哈希表記錄指向一個有 707 個用戶 ID 的數(shù)組，且每個 ID 有 8 個字節(jié)思劳，那么現(xiàn)在我們可以計算出儲存空間約為 12TB迅矛。

現(xiàn)在少很多了，但我們?nèi)匀徊淮_定 12TB 是否是一個合理的數(shù)字潜叛。如果在 32Gb RAM 的專用服務(wù)器上一個月需要 30 美元秽褒，那么 12TB 加上一些控制服務(wù)器和備用服務(wù)器等（約需要額外兩倍數(shù)量）核算下來需要 1500 臺服務(wù)器，每月的成本達到了 45K 美元威兜。這對于我們來說當然是難以接受的價格销斟，但對于推特來說就非常便宜了。但推特需要提高響應(yīng)的速度椒舵，即用戶發(fā)的推文需要第一時間發(fā)送給關(guān)注的人蚂踊。但理想的時間是多少？我們并不能作出任何假設(shè)和抽象逮栅，因此我們可以探討一下現(xiàn)實世界產(chǎn)品系統(tǒng)的響應(yīng)悴势。以下是我們在推文時經(jīng)常遇到情況。

同樣我們并不知道一條推文需要多少時間才能發(fā)送到所有的關(guān)注者措伐，但公開的數(shù)據(jù)表明每天約有 500 億條推文特纤。所以經(jīng)驗看來一般推文的時間在 5 秒內(nèi)，同時我們還要注意哪些擁有超百萬粉絲的名人侥加，推特可能會分配更多的資源來推送名人「超級有用」的內(nèi)容捧存。

為了解決推文的分發(fā)問題，我們并不需要以下的圖担败，我們需要關(guān)注者的列表昔穴。前面的哈希表和一些列表允許我們高效地搜索特定關(guān)注者關(guān)注的所有用戶，但它并不允許高效地搜索關(guān)注特定用戶所有關(guān)注者提前，因此我們必須掃描所有的哈希表鍵值吗货。這也就是為什么我們應(yīng)該構(gòu)建另一個圖，它與以下我們展示的圖對稱相反狈网。這個新的圖由包含 3 億個節(jié)點的哈希表組成宙搬，每個節(jié)點指向相鄰節(jié)點的獵鳥（結(jié)構(gòu)相同），但是這次相鄰節(jié)點的列表將表示關(guān)注者拓哺。

因此基于該示例勇垛，無論何時 Liz 發(fā)推特，Spone Bob 和 Ann 都必須在他們的時間線上找到特定的推文士鸥。一項普遍使用的解決該問題的技術(shù)是為每個用戶的時間線保持獨立的結(jié)構(gòu)闲孤。假設(shè)推特有 3 億的用戶，我們可以假定至少存在 3 億個時間線（每人一個）烤礁。簡單的說讼积，無論何時發(fā)推，我們應(yīng)該找到他的關(guān)注者并且更新他們的時間軸鸽凶，時間線可以被表征成連結(jié)串列或平衡樹（以推文的日期作為節(jié)點關(guān)鍵字）币砂。

// 'author' represents the User object, at this point we are interested only in author.id//// 'tw' is a Tweet object, at this point we are interested only in 'tw.id'?void DeliverATweet(User* author, Tweet* tw){// we assume that 'tw' object is already stored in a database?// 1. Get the list of user's followers (author of the tweet)?vector user_followers = GetUserFollowers(author->id);?// 2. insert tweet into each timeline?for (auto follower : user_followers) {?InsertTweetIntoUserTimeline(follower->id, tw->id);?}}

這僅僅是基本思想，從真實的時間線表征抽象得到玻侥。當然如果使用多線程决摧，我們可以將實際的傳送過程變得更快。這對于大規(guī)模案例非常關(guān)鍵凑兰，因為對于百萬級別的關(guān)注者掌桩，接近列表終點的用戶在處理上通常慢于接近列表前面的用戶。以下的偽代碼將嘗試解釋該多線程傳送思想姑食。

// Warning: a bunch of pseudocode aheadvoid RangeInsertIntoTimelines(vector user_ids, long tweet_id){for (auto id : user_ids) {?InsertIntoUserTimeline(id, tweet_id);?}}void DeliverATweet(User* author, Tweet* tw){?// we assume that 'tw' object is already stored in a database?// 1. Get the list of user's (tweet author's) followers's ids?vector user_followers = GetUserFollowers(author->id);?// 2. Insert tweet into each timeline in parallel?const int CHUNK_SIZE = 4000; // saw this somewhere?for (each CHUNK_SIZE elements in user_followers) {?Thread t = ThreadPool.GetAvailableThread(); // somehowt.Run(RangeInsertIntoTimelines, current_chunk, tw->id);?}}

因此無論關(guān)注者在什么時候刷新推特波岛，他們都能收到新的推文。當然音半，我們僅僅討論了 Airbnb 或推特面臨問題的冰山一角则拷，還有很多問題需要各位讀者共同探討贡蓖。

推特的推文分發(fā)問題關(guān)鍵在于對圖的利用，即使我們不使用任何的圖算法煌茬，僅用圖表示斥铺。而真正的圖算法是相當復(fù)雜的。在使用圖表示之前坛善，我們討論了 Airbnb 房源和高效過濾的問題晾蜘，主要困難在于當過濾器關(guān)鍵字超過一個的時候，就無法高效地過濾家園眠屎。那么使用圖算法能帶來什么好處嗎剔交？值得一試。我們可以將每個過濾器表示成一個獨立的節(jié)點改衩，每個過濾器可以代表特定的屬性（價格岖常、城市名、國家燎字、生活設(shè)施等）腥椒。

Airbnb 過濾器節(jié)選

我們還可以通過添加高層的節(jié)點，例如「生活設(shè)施」節(jié)點來連接所有生活設(shè)施類的節(jié)點（WiFi候衍、電視等）笼蛛，使該集合更容易理解。

擁有高級類型的 Airbnb 過濾器

現(xiàn)在蛉鹿，我們可以將 Airbnb 房源（home）表示成節(jié)點滨砍，然后將這些節(jié)點和對應(yīng)的屬性節(jié)點連接起來。

這個插圖的微妙變化使它更像一種特殊類型的圖形妖异，稱為偶圖（bipartite graph）惋戏。

節(jié)點的數(shù)量比看起來的更多

偶圖的節(jié)點可以分為兩個不相交和獨立的集合，這樣每個邊就將一個集合的節(jié)點連接到另一個集合的節(jié)點他膳。在我們的例子中响逢，其中一個表征過濾器（我們用 F 表示），另一個表征房源集合（H）棕孙。例如舔亭，如果有價值 62 美元的 10 萬個房源，則標記為「$ 62」的價格節(jié)點將具有 10 萬條邊入射到每個房源的節(jié)點蟀俊。

如果我們測量空間復(fù)雜度的最壞情況钦铺，即每個家庭具有滿足所有過濾器的所有屬性，則要存儲的邊總量將為 7 萬×400 萬肢预。如果我們將每個邊表示為一個 ID 對：{filter_id; home_id}矛洞，如果我們重新考慮 ID床未，并使用 4 個字節(jié)（int）數(shù)字 ID 為過濾器 ID剂跟，8 個字節(jié)（long）ID 為房源使用的 ID趴梢，那么每個邊緣至少需要 12 個字節(jié)薪捍。因此，存儲 7 萬* 400 萬個 12 字節(jié)值需要大約 3TB 的內(nèi)存抽兆。我們在計算中犯了一個小錯誤壕探，由于在 Airbnb 中有 65,000 個活躍城市，因此過濾器的數(shù)量約為 7 萬個（統(tǒng)計數(shù)據(jù)）郊丛。

好消息是，同一個家庭不能位于不同的城市瞧筛。也就是說厉熟，我們實際與城市邊配對的數(shù)量是 400 萬（每個家庭位于一個城市），因此我們將計算 70k-65k = 5000 個過濾器较幌，這意味著我們需要 5000 * 400 萬* 12 個字節(jié)的內(nèi)存揍瑟，小于 0.3Tb。聽起來不錯乍炉。但是什么給了我們這個偶圖绢片？最常見的網(wǎng)站/移動請求將由多個過濾器組成，例如：

house_type: "entire_place",adults_number: 2,price_range_start: 56,price_range_end: 80,beds_number: 2,amenities: ["tv", "wifi", "laptop friendly workspace"],facilities: ["gym"]

因此我們只需要找到上述所有「過濾器」的節(jié)點岛琼，并處理與其鄰近所有「房源」的節(jié)點底循。

圖算法

或許，任何用圖執(zhí)行的計算過程都可以分類為「圖算法」槐瑞，你可以實現(xiàn)一個輸出圖的所由節(jié)點的函數(shù)熙涤，然后將其命名為「<你的名字>的節(jié)點輸出算法」。但真正可怕的是教科書中列出的圖算法：

ColoringHopcroft–KarpHungarianPrüfer codingTarjan's off-line least common ancestorsTopological sort

我們嘗試使用偶圖匹配算法困檩，例如 Hopcroft–Karp 算法到 Airbnb 房源過濾問題：

給定一個 Airbnb 房源（H）的偶圖和過濾器（F）祠挫，其中 H 的每個節(jié)點可以多于 F 的一個相鄰節(jié)點（共享一個公共邊）。尋找 H 的由節(jié)點構(gòu)成的子集悼沿，該子集和 F 的子集的節(jié)點相鄰等舔。

問題的定義很難理解，并且目前我們還不確定 Hopcroft-Karp 算法可以解決該問題糟趾，但我們可以在求解的過程中學到很多圖算法的關(guān)鍵思想慌植。這個過程不會很短，需要你有耐心拉讯。Hopcroft-Karp 算法以二分圖為輸入涤浇，并生成最大基數(shù)匹配的輸出，該輸出是一個包含盡可能多的邊的集合魔慷，其中沒有任何兩條邊共享同一個端點只锭。熟悉該算法的讀者已經(jīng)注意到，這并不能解決我們的問題院尔，因為匹配過程的條件是沒有任何兩條邊共享同一個節(jié)點蜻展。我們來看一個示例展示喉誊，其中只有 4 個過濾器和 8 個房源（為簡單起見）。這些房源用字母 A 到 H 標記纵顾，過濾器是隨機選擇的伍茄。從 A 到 H 的所有房源都是 50 美元每晚的價格和一張床，但很少有供應(yīng) WiFi 和/或電視的施逾。因此以下的示例過程將嘗試找到滿足四個條件的房源（擁有 4 個過濾器）敷矫。

對該問題的求解需要找到和特定的房源連接的所有邊，該房源節(jié)點和相同的過濾器子集關(guān)聯(lián)汉额。而 Hopcroft-Karp 算法將移除公共端點的邊曹仗，并生成和兩個子集都關(guān)聯(lián)的邊。

查看上圖蠕搜，我們需要尋找的是房源 D 和 G怎茫，它們滿足了所有四個過濾器值。我們真正需要的是找到共享端點的所有匹配邊妓灌。我們可以為該方法設(shè)計一個算法轨蛤，但其處理時間可以說和用戶需求并不相關(guān)（用戶需求=快速）。也許創(chuàng)建一個平衡的多分類關(guān)鍵字的二值搜索樹會更快虫埂，差不過類似于數(shù)據(jù)庫索引文件祥山，其將主關(guān)鍵字和外鍵映射到滿足條件的記錄集合。我們將在另一篇文章中獨立討論平衡二值搜索樹和數(shù)據(jù)庫索引掉伏，到時會再次返回到 Airbnb 房源問題上枪蘑。

Hopcroft-Karp 算法（以及很多其它算法）都基于 DFS（深度優(yōu)先搜索）和 BFS（廣度優(yōu)先搜索）的圖遍歷算法。說實話岖免，這里介紹 Hopcroft-Karp 算法的真正原因是逐漸轉(zhuǎn)換到圖遍歷算法的討論岳颇，相比從二值樹開始討論會更好。

二值樹遍歷非常漂亮颅湘，這大多是因為它們的遞歸本質(zhì)话侧。有三種基本的遍歷方式稱為中序（in-order）、后序（post-order）和前序（pre-order）闯参。如果你曾經(jīng)遍歷過連結(jié)串列瞻鹏，這些概念是很好懂的。在連結(jié)串列中鹿寨，你只需要輸出當前節(jié)點的值（在下方的代碼中稱為 item）新博，并繼續(xù)到達下一個節(jié)點。

// struct ListNode {// ListNode* next;// T item;// };?void TraverseRecursive(ListNode* node) // starting node, most commonly the list 'head'{if (!node) return; // stop?std::cout << node->item;TraverseRecursive(node->next); // recursive call}void TraverseIterative(ListNode* node){?while (node) {?std::cout << node->item;node = node->next;?}}

這和二值樹幾乎相同脚草，輸出節(jié)點的值赫悄，然后到達下一個節(jié)點，但在這里，「下一個」指的是兩個節(jié)點埂淮，左節(jié)點和右節(jié)點姑隅。因此你需要分別到達左節(jié)點和右節(jié)點。不過你有三個不同的選擇：

輸出節(jié)點值倔撞，然后到達左節(jié)點讲仰，再到達右節(jié)點。到達左節(jié)點痪蝇，然后輸出節(jié)點值鄙陡，再到達右節(jié)點。到達左節(jié)點躏啰，然后到達右節(jié)點柔吼，再輸出節(jié)點值。

// struct TreeNode {// T item;// TreeNode* left;// TreeNode* right;// }// you cann pass a callback function to do whatever you want to do with the node's value// in this particular example we are just printing its value.// node is the "starting point", basically the first call is done with the "root" nodevoid PreOrderTraverse(TreeNode* node){if (!node) return; // stop?std::cout << node->item;?PreOrderTraverse(node->left); // do the same for the left sub-tree?PreOrderTraverse(node->right); // do the same for the right sub-tree}void InOrderTraverse(TreeNode* node){?if (!node) return; // stopInOrderTraverse(node->left);?std::cout << node->item;InOrderTraverse(node->right);}void PostOrderTraverse(TreeNode* node){?if (!node) return; // stop?PostOrderTraverse(node->left);PostOrderTraverse(node->right);?std::cout << node->item;}

前序遍歷的細節(jié)追蹤

很明顯遞歸函數(shù)的形式很優(yōu)雅丙唧，雖然其計算成本很高。每次我們遞歸地調(diào)用一個函數(shù)觅玻，也就意味著我們調(diào)用了一個完全的新函數(shù)（如上圖所示）想际。其中「新」的意思是函數(shù)變量和局域變量需要分配其它的堆棧內(nèi)存空間。這正是為什么遞歸調(diào)用的成本如此高（額外的堆椣澹空間分配和多函數(shù)調(diào)用）和危險（堆棧溢出）胡本，很明顯地使用迭代實現(xiàn)會更好。在關(guān)鍵任務(wù)（航空畸悬、NASA 探測車等）的系統(tǒng)編程中侧甫，遞歸調(diào)用是完全禁止的。

實例：Netflix

假設(shè)我們要將所有 Netflix 電影存儲在二進制搜索樹中蹋宦，并將電影標題作為排序鍵披粟。所以無論何時用戶輸入類似「Inter」的內(nèi)容，我們都會返回一個以「Inter」開頭的電影列表冷冗，舉例守屉，[「Interstellar」,「Interceptor」,「Interrogation of Walter White」]。如果我們將返回標題中包含「Inter」的所有電影（不僅僅是以「Inter」開頭的電影）那就太好了蒿辙，并且該列表將根據(jù)電影的評分或與該特定用戶相關(guān)的內(nèi)容進行排序（喜歡驚悚片比戲劇更多）拇泛。這個例子的重點在于對 BST 進行有效的范圍查詢，但像往常一樣思灌，我們不會深入探討其余部分俺叭。基本上泰偿，我們需要通過搜索關(guān)鍵字進行快速查找熄守，然后獲得按關(guān)鍵字排序的結(jié)果列表，這很可能應(yīng)該是電影評級和/或基于用戶個性化數(shù)據(jù)的內(nèi)部排名。我們會盡可能地堅持 KISK 原則（Keep It Simple柠横，Karl）窃款。

「KISK」或「讓我們保持它的簡單」或「為了簡單起見」，這是教程編寫者從真實問題中抽象出來的超級借口牍氛，并通過在偽代碼中引入「abc」簡單示例及其解決方案來做出大量假設(shè)晨继，并且這些答案在很老的筆記本電腦上也能工作。

這個問題可以很容易地應(yīng)用到亞馬遜的產(chǎn)品搜索上搬俊，因為我們通常通過輸入描述我們興趣的文本（如「圖算法」）來搜索亞馬遜的東西紊扬，并根據(jù)產(chǎn)品的評分獲得結(jié)果（我沒有在亞馬遜的個性化結(jié)果中體驗過搜索結(jié)果，但我很確定亞馬遜也是這樣做的）唉擂。所以餐屎，為了公平將這個子標題改為...

Netflix 和亞馬遜。Netflix 提供電影服務(wù)玩祟，亞馬遜提供產(chǎn)品腹缩，我們會將它們命名為「物品」，所以每當你閱讀「物品」時空扎，都會想到 Netflix 中的電影或亞馬遜的任何 [合格] 產(chǎn)品藏鹊。這些物品最常用的是解析其標題和描述（我們只處理標題），所以如果一個操作員（通常是一個人通過管理儀表板將項目的數(shù)據(jù)插入 Netflix / Amazon 數(shù)據(jù)庫）插入新項目到數(shù)據(jù)庫中转锈，它的標題正在被一些「ItemTitleProcessor」處理以產(chǎn)生關(guān)鍵字盘寡。

我知道這并不是最好的圖例（而且有一個書寫錯誤）

每一個物品都有專屬 ID，這個 ID 也鏈接到了標題之中的關(guān)鍵字撮慨。這也是搜索引擎在爬全世界的網(wǎng)站時做的竿痰。他們分析每個文檔的內(nèi)容，對其進行標記（將其分解為更小的實體和單詞）并添加到表中砌溺，該表將每個標記（詞）映射到標記已被「看到」的文檔標識（網(wǎng)站）影涉。因此，無論何時搜索「hello」规伐，搜索引擎都會獲取映射到關(guān)鍵字「hello」的所有文檔（實際情況非常復(fù)雜常潮，因為最重要的是搜索相關(guān)性，這就是為什么谷歌搜索非常棒）楷力。所以 Netflix /亞馬遜的類似表格可能看起來像這樣（再次喊式，在閱讀物品時想一想電影或產(chǎn)品）。

倒排索引

哈希表萧朝，再提一次岔留。是的，我們將為此倒排索引（索引結(jié)構(gòu)存儲來自內(nèi)容的映射）保留哈希表检柬。哈希表會將關(guān)鍵字映射到物品的 BST献联。為什么選擇 BST竖配？因為我們希望保持它們的排序并同時提供連續(xù)排序的部分（響應(yīng)前端請求），例如一次請求（分頁）中的 100 個物品里逆。這并不能說明 BST 的強大功能进胯，但假設(shè)我們還需要在搜索結(jié)果中進行快速查找，例如原押，你需要關(guān)鍵字為「機器」的所有 3 星電影胁镐。

請注意，可以在不同的樹中復(fù)制物品诸衔，因為通扯⑵可以使用多個關(guān)鍵字找到物品。我們將使用如下面定義的物品進行操作：

// Cached representation of an Item// Full Item object (with title, description, comments etc.)?// could be fetched from the databasestruct Item{// ID_TYPE is the type of Item's unique id, might be an integer, or a stringID_TYPE id;?int rating;};

每次將新物品插入數(shù)據(jù)庫時笨农，其標題都將被處理并添加到大型索引表中就缆，該表將關(guān)鍵字映射到物品≮艘啵可能有許多物品共享相同的關(guān)鍵字竭宰，因此我們將這些物品保存在按照評分排序的 BST 中。當用戶搜索某個關(guān)鍵字時份招，他們會得到按其評分排序的物品列表切揭。我們?nèi)绾螐呐判虻臉渲蝎@取列表？通過按順序遍歷脾还。

// this is a pseudocode, that's why I didn't bother with "const&"'s and "std::"'s// though it could have look better, forgive me C++ fellowsvector GetItemsByKeywordInSortedOrder(string keyword){// assuming IndexTable is a big hashtable mapping keywords to Item BSTsBST items = IndexTable[keyword];?// suppose BST has a function InOrderProduceVector(), which creates a vector and?// inserts into it items fetched via in-order traversing the tree?vector sorted_result = items.InOrderProduceVector();?return sorted_result;}

這里是一種 InOrderProduceVector() 實現(xiàn)：

template class BST{public:// other code ...vector InOrderProduceVector()?{?vector result;result.reserve(1000); // magic number, reserving a space to avoid reallocation on inserts?InOrderProduceVectorHelper_(root_, result); // passing vector by reference?return result;?}protected:?// takes a reference to vector?void InOrderProduceVectorHelper_(BSTNode* node, vector& destination)?{?if (!node) return;InOrderProduceVectorHelper_(node->left, destination);destination.push_back(node->item);?InOrderProduceVectorHelper_(node->right, destination);?}private:?BSTNode* root_;};

但是呢，我們首先需要最高評價的物品入愧，來替換掉按順序遍歷生成最低評級的物品鄙漏。這是因為它的性質(zhì)，是從低到高的順序遍歷物品棺蛛，「自下而上」怔蚌。為了得到我們想要的東西，即列表按降序而不是升序排列旁赊，我們應(yīng)該仔細查看順序遍歷實現(xiàn)桦踊。我們所做的是通過左節(jié)點，然后打印當前節(jié)點的值和通過右邊的節(jié)點终畅。當我們第一次通過左節(jié)點時籍胯，這就是為什么我們首先獲得了「最左」節(jié)點（最左節(jié)點），這是具有最小值的節(jié)點离福。因此杖狼，簡單地將實現(xiàn)更改為首先通過正確的節(jié)點將導致我們按照列表的降序排列。我們會像其他人一樣將其命名妖爷，這是一種逆序的遍歷蝶涩。讓我們更新上面的代碼（引入單個列表、警告、錯誤）：

// Reminder: this is pseudocode, no bother with "const&", "std::" or others// forgive me C++ fellowstemplate class BST{public:// other code ...?vector ReverseInOrderProduceVector(int offset, int limit)?{?vector result;?result.reserve(limit);?// passing result vector by reference?// and passing offset and limitReverseInOrderProduceVectorHelper_(root_, result, offset, limit);?return result;?}protected:?// takes a reference to vector?// skips 'offset' nodes and inserts up to 'limit' nodes?void ReverseInOrderProduceVectorHelper_(BSTNode* node, vector& destination, int offset, int limit)?{?if (!node) return;?if (limit == 0) return;?--offset; // skipping current elementReverseInOrderProduceVectorHelper_(node->right, destination, offset, limit);?if (offset <= 0) { // if skipped enough, insertdestination.push_back(node->value);?--limit; // keep the count of insertions?}ReverseInOrderProduceVectorHelper_(node->left, destination, offset, limit);}private:?BSTNode* root_;};// ... other possibly useful code// this is a pseudocode, that's why I didn't bother with "const&"'s and "std::"'s// though it could have look better, forgive me C++ fellowsvector GetItemsByKeywordInSortedOrder(string keyword, offset, limit) // pagination using offset and limit{?// assuming IndexTable is a big hashtable mapping keywords to Item BSTs?BST items = IndexTable[keyword];// suppose BST has a function InOrderProduceVector(), which creates a vector and?// inserts into it items fetched via reverse in-order traversing the tree?// to get items in descending order (starting from the highest rated item)vector sorted_result = items.ReverseInOrderProduceVector(offset, limit);?return sorted_result;}

通過排序關(guān)鍵詞查找電影或產(chǎn)品

這就對了绿聘，我們可以非乘陨希快速地提供物品搜索結(jié)果。如上所示熄攘，反轉(zhuǎn)索引在搜索引擎中最常用兽愤，例如谷歌搜索。雖然谷歌搜索引擎非常復(fù)雜鲜屏，它確實利用了某些簡單的思想烹看，來將搜索查詢匹配到文檔上，并盡可能快速地提供結(jié)果洛史。

我們使用了樹遍歷來以分類排序提供結(jié)果惯殊。在這里，前序/順序/后序遍歷可能太多了也殖，但有時候我們也需要應(yīng)用其它類型的遍歷土思。讓我們來解決這個著名的編程面試問題：「如何按等級輸出一個二值樹等級？」

DFS vs. BFS

如果你對這個問題不熟悉忆嗜，想想你在遍歷樹的時候可用于存儲節(jié)點的數(shù)據(jù)結(jié)構(gòu)己儒。如果對比分層遍歷樹和上文介紹的其他方式（前序/順序/后序遍歷），就會發(fā)現(xiàn)兩種主要的圖遍歷方法：深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）捆毫。

深度優(yōu)先搜索尋找最遠的節(jié)點闪湾，廣度優(yōu)先搜索先尋找最近的節(jié)點。

深度優(yōu)先搜索——更多動作绩卤，更少思考途样。廣度優(yōu)先搜索——在進一步行動之前先仔細觀察四周。

DFS 很像前序/順序/后序遍歷濒憋，而 BFS 用于分層輸出樹節(jié)點何暇。我們需要一個隊列（數(shù)據(jù)結(jié)構(gòu)）來存儲圖的「層級」，同時輸出（訪問）其「父級」凛驮。在之前的插圖中裆站，節(jié)點是隊列中淺藍色的點。每一層的節(jié)點被從隊列中取走黔夭，同時在訪問每個被取走的節(jié)點時宏胯，我們還應(yīng)該將其子節(jié)點插入隊列（為下一層做準備）。下列代碼很簡單本姥，可以幫助大家了解 BFS胳嘲。代碼假設(shè)圖是連通的，盡管我們可以修改代碼扣草，使其應(yīng)用于非連通圖了牛。

// Assuming graph is connected?// and a graph node is defined by this structure// struct GraphNode {// T item;// vector children;// }// WARNING: untested codevoid BreadthFirstSearch(GraphNode* node) // start node{if (!node) return;?queue q;?q.push(node);?while (!q.empty()) {?GraphNode* cur = q.front(); // doesn't pop?q.pop();?for (auto child : cur->children) {?q.push(child);?}?// do what you want with current nodecout << cur->item;?}}

在基于節(jié)點的連通圖表示上可以輕松地了解基本思想颜屠。記住圖遍歷的實現(xiàn)因圖表示而異。BFS 和 DFS 在解決圖搜索問題中是重要的工具（但是存在大量圖搜索算法）鹰祸。盡管 DFS 具備優(yōu)雅的遞歸實現(xiàn)甫窟，但進行迭代實現(xiàn)更合理。我們使用隊列進行 BFS 的迭代實現(xiàn)蛙婴，而 DFS 則需要堆棧粗井。圖領(lǐng)域中一個最流行的問題，同時也可能是你閱讀本文的原因之一是尋找圖節(jié)點之間的最短路徑街图。這需要我們進行最后一個實驗浇衬。

示例：Uber

Uber 有 5000 萬用戶、700 萬司機餐济，對于 Uber 來說耘擂，最重要的事情之一就是高效匹配司機和乘客。該問題首先是定位的問題絮姆。后端要處理數(shù)百萬份用戶請求醉冤，將每份請求發(fā)送至一或多（通常是多）位附近的司機。盡管將用戶請求發(fā)送至所有附近司機更加簡單篙悯，有時也更加智能蚁阳，但是預(yù)處理通常會有所幫助。

除了處理請求鸽照、基于用戶坐標確定定位螺捐、尋找最近坐標的司機以外，我們還需要尋找最適合這趟行程的司機矮燎。為了避免地理空間請求處理（對比司機當前坐標和用戶坐標定血，來獲取附近車輛），我們假設(shè)已經(jīng)分割了用戶和多輛附近車輛的地圖漏峰，如下圖所示：

黃色路線是車輛到用戶處的可能路徑糠悼。問題在于計算車輛到達用戶的最小距離届榄，即尋找最短路徑浅乔。盡管這更多地涉及谷歌地圖而不是 Uber，我們?nèi)匀粐L試解決這一特定和簡化案例铝条，其原因主要在于通常存在多輛車靖苇，Uber 可能需要計算離用戶最近的車。就這張插圖而言班缰，這意味著計算全部三輛車的最短路徑并確定哪輛車最適合該行程贤壁。為了使問題簡潔，我們將討論只有一輛車的情況埠忘。下圖顯示了一些到達用戶的可能路徑脾拆。

車輛到達用戶的可能路徑

我們將該地圖分割表示為一個圖：

這是一個無定向的加權(quán)圖（更具體地說是馒索，邊加權(quán)）。為了找到從 B（車）到 A（用戶）的最短途徑名船，我們應(yīng)該找到他們之間的一條邊權(quán)重最小的路绰上。你可以自由的設(shè)計你自己版本的解決方案，我們還是使用 Dijkstra 的版本渠驼。下面的步驟是從維基百科上找到的 Dijkstra 的算法的步驟蜈块。

讓我們把起始的節(jié)點叫做初始節(jié)點。節(jié)點距離 Y 表示初始節(jié)點到 Y 的距離迷扇。Dijkstra 的算法將分配一些初始距離值百揭，并嘗試一步步地改善它們。

1. 標記所有未訪問節(jié)點蜓席。創(chuàng)建所有未訪問節(jié)點的集合「unvisited set」器一。

2. 為每個節(jié)點分配一個實驗距離值：初始節(jié)點的距離值設(shè)置為 0，其他節(jié)點設(shè)置為無窮大瓮床。將初始節(jié)點設(shè)置為當前節(jié)點盹舞。

3. 對于當前節(jié)點，考慮其所有未訪問近鄰隘庄，通過當前節(jié)點計算它們的實驗距離踢步。對比新計算的實驗距離和當前分配的值，分配較小的值丑掺。例如获印，如果當前節(jié)點 A 的距離是 6，連接 A 與近鄰 B 的邊長度為 2街州，則經(jīng)過 A 到 B 的距離是 6 + 2 = 8兼丰。如果 B 之前標記的距離大于 8，則將其更改為 8唆缴。反之鳍征，保留當前值。

4. 當我們考慮完當前節(jié)點的所有近鄰之后面徽，將當前節(jié)點標記為已訪問艳丛，并從 unvisited set 中移除。已訪問節(jié)點無需再檢查趟紊。

5. 如果目標節(jié)點已經(jīng)標記為已訪問（當規(guī)劃兩個特定節(jié)點之間路線的時候）氮双，或 unvisited set 中節(jié)點之間的最小實驗距離是無窮大（當規(guī)劃完整遍歷時，初始節(jié)點和其余未訪問節(jié)點之間沒有連接時）霎匈，則停止戴差，算法結(jié)束。

6. 反之铛嘱，選擇標記有最小實驗距離的未訪問節(jié)點暖释，將其設(shè)置為新的「當前節(jié)點」袭厂，并返回第 3 步。

在我們的示例中球匕，我們首先將節(jié)點 B（車輛）設(shè)置為初始節(jié)點嵌器。前兩步：

我們的 unvisited set 包含了所有的節(jié)點，同時也要注意圖左邊里顯示的表格谐丢。所有的節(jié)點都包括了到 B 和到之前節(jié)點的最短距離爽航。例如，從 B 到 F 的最短距離是 20乾忱，之前節(jié)點是 B讥珍。

我們把 B 標注為訪問過的然后移動到它的近鄰 F。

現(xiàn)在窄瘟，我們把 F 標注已訪問過的衷佃，然后在最小實驗距離下選下一個沒被訪問過的節(jié)點，就是 G蹄葱。

就像算法里說的氏义，如果目標節(jié)點已經(jīng)被標注為訪問過的（當規(guī)劃兩個特定的節(jié)點間的路線時）那么我們可以停止。所以我們下一步用下面的值去停止算法图云。

所以我們已經(jīng)有了從 B 到 A 并且經(jīng)過 F 與 G 的兩條最短距離惯悠。

這真的是 Uber 里最簡單的問題的例子，和冰山類比相比較竣况，我們在冰山的山尖上克婶。然而，這對于我們探索圖論應(yīng)用的真實場景是個好的開始丹泉。我沒有完成我一開始計劃的文章情萤，但在不久的將來這個文章最有可能繼續(xù)下去（也包括數(shù)據(jù)庫內(nèi)部索引）。

關(guān)于圖論有很多內(nèi)容需要去學習摹恨，這篇文章只是冰山一角筋岛，非常感謝各位讀者有耐心能閱讀完 ~