圖論是計(jì)算機(jī)科學(xué)中最重要、最有趣的領(lǐng)域之一，同時(shí)也是最容易被誤解的。本長文從圖論最基礎(chǔ)的七橋問題開始，進(jìn)而結(jié)合推特與 Facebook 實(shí)例解釋無向圖與有向圖。此外，本文還是用大量的實(shí)例解釋表征圖、搜索樹、哈希表等關(guān)鍵概念。最后本文描述了基于深度的搜索和基于廣度的搜索等十分流行的圖算法。
理解和使用圖幫助我們成為更好的程序員。用圖思考幫助我們成為最好的，至少我們應(yīng)該那么思考。圖是很多節(jié)點(diǎn) V 和邊 E 的集合，即可以表示為有序?qū)?G=(V, E)。
盡管嘗試研究過圖論，也實(shí)現(xiàn)了一些算法，但是我還是非常困惑，因?yàn)樗鼘?shí)在太無聊了。
事實(shí)上，理解一件事物的最佳方式是理解其應(yīng)用。我們將展示圖論的多個(gè)應(yīng)用，最重要的是，有很多插圖。
七橋問題
讓我們首先從《圖論的起源》中的「柯尼斯堡（K?nigsberg）的七座橋」開始。在加里寧格勒（Kaliningrad）有七座橋，連接著由普雷戈里亞（Pregolya）河分割而成的兩個(gè)島嶼和兩大陸地。
在 18 世紀(jì)，這里被稱為柯尼斯堡，隸屬普魯士，這一區(qū)域有很多橋。當(dāng)時(shí)，有一個(gè)與柯尼斯堡的橋相關(guān)的腦筋急轉(zhuǎn)彎：如何只穿過橋一次而穿過整個(gè)城市。下圖為柯尼斯堡七座橋的簡化圖。
你可以嘗試一下，在穿過每座橋僅一次的情況下穿過這個(gè)城市。每座橋，意味著所有橋都被穿過；只穿過一次，意味著每座橋不能被穿越兩次及以上。如果你對這一問題有所了解，就知道這不可能。
Leonhard Euler
有時(shí)候，放棄這一問題是合理的。這就是 Leonhard Euler 的解決方法，他沒有試圖解決這一問題，而是證明其不可解決。讓我們試著去理解 Euler 的內(nèi)在想法，做到像 Euler 一樣思考。首先我們從下圖開始。
圖中有四塊彼此分隔的區(qū)域，兩個(gè)島嶼和兩塊陸地，以及七座橋。探討每一區(qū)域的橋數(shù)是否有一定模式很有趣。
每塊區(qū)域的橋數(shù)
如圖所示，每塊區(qū)域的橋數(shù)皆為奇數(shù)。如果你只能穿過橋一次，區(qū)域有兩座橋，那么你就可以進(jìn)入并離開該區(qū)域。
有兩座橋的區(qū)域的示例
通過圖示很容易發(fā)現(xiàn)，如果你通過一座橋進(jìn)入一個(gè)區(qū)域，那么你也要通過第二座橋離開它。但是當(dāng)?shù)谌鶚虺霈F(xiàn)，則無法只穿過橋一次而離開。所以對于一塊區(qū)域，當(dāng)橋數(shù)為偶時(shí)，則可以每座橋只穿過一次而離開；當(dāng)橋數(shù)為奇時(shí)，則不能。請牢記。
讓我們再添加一座新橋，如下圖所示，看看其是否能解決問題。
注意添加的新橋
現(xiàn)在我們有兩個(gè)偶數(shù)和兩個(gè)奇數(shù)。讓我們在添加新橋的圖上畫一條新路線。
我們已經(jīng)看到了橋的奇偶數(shù)是重要的。這里有個(gè)問題：橋的數(shù)量解決問題了嗎？難道這個(gè)數(shù)不應(yīng)該一直是偶數(shù)嗎？后來發(fā)現(xiàn)不是的。這就是 Euler 做的，他發(fā)現(xiàn)了一個(gè)顯示橋數(shù)量很重要的辦法。更有意思的事，有奇數(shù)個(gè)連接點(diǎn)的「陸地」也很重要。這時(shí)候 Euler 開始把陸地和橋轉(zhuǎn)化成我們看得懂的圖。下面是一幅表示了哥尼斯堡七橋（K?nigsberg bridges）的圖（注意：我們「臨時(shí)」加的橋不在這里）：
抽象化七橋問題
問題的泛化和提取是需要注意的。當(dāng)你解決一個(gè)特定問題時(shí)，最重要的是為類似的問題概括答案。在這個(gè)實(shí)際問題里，Euler 的任務(wù)是泛化過橋問題從而在將來可以解決類似的問題。比如：對于世界上所有的橋?？梢暬部梢詭椭覀儚牧硪粋€(gè)角度看問題，如下面的圖也全是七橋問題的抽象：
所以，可視化圖是解決該問題的好選擇，因此我們需要去找出哥尼斯堡七橋問題是怎樣被這張圖解決的。注意從圈里面向外出來的線。因此我們命名圈為節(jié)點(diǎn)（或節(jié)點(diǎn)），連接他們的線為邊。你也許看到了字母表達(dá)法，V 是節(jié)點(diǎn)（vertex），E 是邊（edge）。
下一個(gè)重要的事是所謂節(jié)點(diǎn)自由度（Degree），即連接到節(jié)點(diǎn)的邊數(shù)量。在我們上面的例子里，連接陸地和橋的邊的數(shù)量可以被表達(dá)成節(jié)點(diǎn)的自由度。
在 Euler 的努力下，他證明了在圖上（城市里）每次只走過一條邊（橋）并且走過每一條邊是嚴(yán)格取決于節(jié)點(diǎn)自由度。由這樣的邊組成的路徑被叫做 Euler 路徑（Euler path），Euler 路徑的長度就是邊的數(shù)量。
有限無向圖 G(V,E) 的 Euler 路徑是指 G 的每一個(gè)邊都只出現(xiàn)一次的路徑。如果 G 有一條 Euler 路徑，它就被稱之 Euler 圖。[注釋 1]
定理：有且僅有兩個(gè)確定的節(jié)點(diǎn)存在奇數(shù)自由度，其它的節(jié)點(diǎn)都有偶數(shù)自由度，那么該有限無向圖為 Euler 圖?！?】
左圖：有兩個(gè)節(jié)點(diǎn)有奇數(shù)自由度的圖像。右圖：所有節(jié)點(diǎn)都有奇數(shù)自由度。
首先，讓我們分清楚上面定理和理論中的新名詞。有限圖（Finite graph）是指有限數(shù)量的邊和節(jié)點(diǎn)的圖。
圖可以為有向的或無向的，這也是圖非常有趣的性質(zhì)。你肯定看到過將 Facebook 和 Twitter 的作為有向圖和無向圖的例子。Facebook 朋友關(guān)系也許可以很簡單地表示為一個(gè)無向圖，因?yàn)槿绻?Alice 是 Bob 的朋友的話，Bob 也必須是 Alice 的朋友。
而且也要注意「Patrick」節(jié)點(diǎn)，因?yàn)樗鼪]有連接一條邊（edges）。雖然它還是圖的一部分，但在這個(gè)案例中我們可以說該圖沒有連接上，這是個(gè)失聯(lián)圖（disconnected graph）（「John」、「Ashot」和「Beth」也是同樣的，因?yàn)樗鼈兪呛蛣e的節(jié)點(diǎn)都是分離的）。在一個(gè)連接的圖里沒有到達(dá)不了的節(jié)點(diǎn)，這里必須在每一對節(jié)點(diǎn)之間有一條路。
與 Facebook 的例子相反的是，如果 Alice 在 Twitter 上關(guān)注了 Bob，Bob 并不需要關(guān)注 Alice。所以「關(guān)注」關(guān)系必須是有向的連接，其表示節(jié)點(diǎn)（用戶）有一條有向邊（關(guān)注）連接到其它的節(jié)點(diǎn)（用戶）。
現(xiàn)在，我們了解了什么是有限無向圖，讓我們再一次思考 Euler 圖：
所以為什么我們最開始就討論了哥尼斯堡七橋問題和 Euler 圖呢？在接觸答案之前接觸一下問題背后的因素（節(jié)點(diǎn)、邊、有向、無向）也能避免枯燥的理論方法。我們現(xiàn)在應(yīng)該更關(guān)注于用電腦表示圖，因?yàn)檫@是我們最大的興趣。用電腦程序表示圖將使我們設(shè)計(jì)出一個(gè)算法來跟蹤圖路徑（graph path），這樣就能發(fā)現(xiàn)它是不是 Euler 路徑了。
圖表征：前言
這是一個(gè)很沉悶的任務(wù)，要有耐心。記得數(shù)組和鏈表之間的戰(zhàn)爭嗎？用如果你需要快速訪問元素就用數(shù)組，如果你需要快速插入/刪除元素就用鏈表等。我很難相信你會(huì)在像「怎樣表示列表」這樣的問題上糾結(jié)。當(dāng)然，在圖論中真正的表達(dá)是非常無聊的，因?yàn)槭紫饶銘?yīng)該決定你將怎樣確切地表達(dá)圖。
現(xiàn)在我們以一個(gè)樹來開始。你肯定已經(jīng)至少一次見到了二叉樹（下面的不是二叉搜索樹）。
因?yàn)樗怯晒?jié)點(diǎn)和邊構(gòu)成的，所以它就是圖。你也要想到一般最常見的二叉樹是怎樣表示的（至少在教科書上）。
struct BinTreeNode
{
T value; // don't bother with template
TreeNode* left;
TreeNode* right;
};
class BinTree
{
public:
// insert, remove, find, bla bla
private:
BinTreeNode* root_;
};
這個(gè)對于已經(jīng)非常熟悉樹的人來說太詳細(xì)了，但是我必須確保我們在同一階段。（注意我們還是在用偽代碼）。
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');
如果你不是新手，仔細(xì)的讀上面的偽代碼然后閱讀以下圖解：
當(dāng)一個(gè)二叉樹是簡單的節(jié)點(diǎn)「集合」，每一個(gè)父節(jié)點(diǎn)有左子節(jié)點(diǎn)和右子節(jié)點(diǎn)的節(jié)點(diǎn)。二叉樹在應(yīng)用簡單規(guī)則的時(shí)候是非常有意義的，例如允許快速的關(guān)鍵字查找。二叉搜索樹（BST）按序儲(chǔ)存他們的關(guān)鍵字。我們可以根據(jù)任何規(guī)則實(shí)現(xiàn)二叉樹（即使它會(huì)根據(jù)不同的規(guī)則而有不同的名字，比如，min—heap 或者 max——heap），最常見的 BST 規(guī)則是它符合二項(xiàng)搜索性質(zhì)（也是名字的由來），即「任意節(jié)點(diǎn)的鍵值必須比它左邊子樹的鍵值要大，比右邊子樹上的鍵值要小。「更大」是 BST 重要的本質(zhì)，當(dāng)你把它改成「比更大或一樣」時(shí)，你的 BST 可以在插入新節(jié)點(diǎn)時(shí)解決復(fù)制鍵值得問題，除此之外它將只保留唯一鍵值的節(jié)點(diǎn)。你可以在網(wǎng)上找到很好的二項(xiàng)樹的文章，我們不會(huì)提供一個(gè)二元搜索樹的全面實(shí)現(xiàn)，但我們將展示一個(gè)簡單的二元搜索樹。
Airbnb
樹是非常有用的數(shù)據(jù)結(jié)構(gòu)，你也許還沒有實(shí)現(xiàn)過樹型結(jié)構(gòu)，但你也許無意間用過它們。像你注意到的，二叉搜索樹（Binary Search Tree）中有「搜索」，簡單來說，所有需要快速查找的事，應(yīng)該被放到二叉搜索樹中?！笐?yīng)該」不意味著一定，在編程中最重要的事情是用合適的工具去解決問題。這里有很多案例可以看到簡單鏈表（O(N) 復(fù)雜度）搜索相比 BST（O(logN) 復(fù)雜度）搜索更受歡迎。一般來說我們可以用一個(gè)庫來實(shí)現(xiàn)一個(gè) BST，但是在這個(gè)教程中我們可以重新發(fā)明我們自己的輪子（BST 是基本在所有多用途編程語言庫都有實(shí)現(xiàn)）。接近了「一個(gè)真實(shí)世界例子」，這里是我們試著去處理的問題：
Airbnb 房源搜索一瞥：
怎樣用濾波器基于詞條盡可能快的搜索房源，這是一項(xiàng)很難的任務(wù)。如果我們考慮到 Airbnb 儲(chǔ)存了幾百萬條表格的情況下，這個(gè)任務(wù)更難了。
所以當(dāng)用戶搜索房源時(shí)，他們也許就會(huì)「接觸」到四百萬條數(shù)據(jù)庫中的記錄。的確，在網(wǎng)站主頁上能夠展現(xiàn)的「top listings」有限，而用戶對瀏覽百萬條列表也并不感興趣。我沒有任何 Airbnb 的分析記錄, 但我們可以用編程語言中叫做「假設(shè)」的強(qiáng)大工具，所以我們假設(shè)單個(gè)用戶查看最多 1 千個(gè)房源就會(huì)發(fā)現(xiàn)中意的房源。并且最重要的因子是即時(shí)用戶的數(shù)量，因?yàn)樗鼤?huì)影響數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫和項(xiàng)目構(gòu)架的選擇。就像這看起來的那么明顯，如果這里總共有 100 個(gè)用戶，我們就不用去操心。相反，如果即時(shí)用戶數(shù)量超過了百萬級，我們必須去思考每一個(gè)決定到底對不對。每個(gè)決策都被正確的使用，這是為什么巨頭們雇傭最好的人才，為提供卓越的服務(wù)而努力的原因（Google、Facebook、Airbnb、Netflix、Amazon、Twitter 和許多其他公司都在處理大量的數(shù)據(jù)；招聘正確的工程師來做正確的選擇，為數(shù)百萬實(shí)時(shí)用戶每秒處理百萬級字節(jié)的數(shù)據(jù)。這就是為什么我們碼農(nóng)糾結(jié)于可能遇見的數(shù)據(jù)結(jié)構(gòu)，算法和問題處理，因?yàn)樾枰氖枪こ處熡心芰焖佟⒂行У亟鉀Q這樣大的問題）。
所以在 Airbnb 的案例里，用戶瀏覽了他們的房源主頁，Airbnb 試著去過濾房源來找出最適合的。我們怎樣處理這個(gè)問題呢？（注意這個(gè)問題是后端的，所以我們不需要管前端或者網(wǎng)絡(luò)流量或者 https over http 或者 Amazon EC2 over home cluster 等。首先，因?yàn)槲覀円呀?jīng)熟悉了程序員倉庫中最強(qiáng)大的工具（在說假設(shè)而不是抽象），我們假設(shè)處理的是完全適配 RAM 的數(shù)據(jù)。然后你也可以假設(shè)我們的 RAM 是足夠大的。足夠大去支持，但這是多大呢？這是另一個(gè)非常好的問題。需要多大的內(nèi)存來存儲(chǔ)真正的數(shù)據(jù)呢？如果我們處理的是四百萬單元的數(shù)據(jù)（還是假設(shè)），如果我們大概知道每一個(gè)單元的大小，之后我們可以簡單地驅(qū)動(dòng)需要的內(nèi)存，就是 4M*sizeof(one_unit)?？紤]下「房源」及其性質(zhì)（properties），事實(shí)上，至少考慮一下處理這一問題必要的性質(zhì)（一個(gè)「房源」是我們的單元）。我們需要用 C++結(jié)構(gòu)偽代碼來表示一些問題，你可以簡單地將他們轉(zhuǎn)化為一個(gè) MongoDB 略圖目標(biāo)或者任何你想要的形式, 我們只討論性質(zhì)的名字和類別。（試著去想象這是在空間經(jīng)濟(jì)里用字位段或者位集合）
// 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 home_type;
uchar beds_number;
uchar bedrooms_number;
uchar bathrooms_number;
bitset accessibility;
bool superhost;
bitset amenities;
bitset facilities;
bitset property_types;
bitset host_languages;
bitset house_rules;
ushort country_code;
string city;
};
假設(shè)。上面的結(jié)構(gòu)不是完美的（很顯然），而且這里有很多假設(shè)或者不完整的地方，去再讀一下免責(zé)聲明。我只是看了下 Airbnb 的過濾器和應(yīng)該存在的符合搜索查詢的設(shè)計(jì)性產(chǎn)權(quán)表。這只是個(gè)例子?，F(xiàn)在我們應(yīng)該能計(jì)算每一個(gè) AirbnbHome 對象會(huì)在內(nèi)存中占用多少空間。name 是一個(gè) wstring 來支持多語言的名字/頭銜的，這個(gè)意味著每一個(gè)字符占了 2 字節(jié)（我們不想擔(dān)心字符大小如果我們需要用其他的語言，但在 C++中，char 是 1 字節(jié)然后 wchar 是 2 字節(jié)）。
快速的看一下 Airbnb 的表可以讓我們估計(jì)房源的名字可以占到最多 100 個(gè)字符（雖然最多的是 50 個(gè)左右，而不是 100 個(gè)），我們會(huì)認(rèn)為 100 個(gè)字符是最多的量，這占了差不多 200 字節(jié)的內(nèi)存。uint 是 4 字節(jié)，uchar 是 1 字節(jié),ushort 是 2 字節(jié)（還是假設(shè)）。假設(shè)圖片是在儲(chǔ)存服務(wù)旁邊，像 Amazon S3（目前據(jù)我所知，這個(gè)假設(shè)對于 Airbnb 來說是最可能實(shí)現(xiàn)的，當(dāng)然這也是假設(shè)）而且我們有這些照片的 URL，而且考慮這里沒有 URL 的標(biāo)準(zhǔn)尺寸的限制，但這事實(shí)上有一個(gè)眾所周知的上線-2083 字符，我們將要用這個(gè)當(dāng)成任何 URL 的最大尺寸。所以考慮到這個(gè)，平均每個(gè)房源有 5 張照片，這可以占到 10Kb 內(nèi)存。
讓我們重新想一下，一般儲(chǔ)存用同樣的基礎(chǔ) URL 服務(wù)，像 http(s)://s3.amazonaws.com//，這樣就是說，這里有一個(gè)基本的模式來建 URL 并且我們只需要儲(chǔ)存真實(shí)照片的 ID，讓我們說用了一些獨(dú)特的 ID 生成器，可以為圖片對象返回 20 字節(jié)長度的獨(dú)特的字符 ID，看起來像 https://s3.amazonaws.com/some-know-bucket/。這提供了我們好多空間效率，所以為了 5 張照片儲(chǔ)存字符 ID，我們只需要 100 字節(jié)內(nèi)存。
同樣的「手段」可以用 host_id 來做，就是說，房主的用戶 ID，占了 20 字節(jié)的內(nèi)存（實(shí)際上我們可以就讓用戶用數(shù)字 ID，但考慮到一些 DB 系統(tǒng)像 MongoDB 有非常詳細(xì)的 ID 生成器，我們假設(shè) 20 字節(jié)的字符 ID 是「中位」長度，已經(jīng)可以用很小的改動(dòng)就能適用于大部分 DB 系統(tǒng)了。Mongo 的 ID 長度是 24 字節(jié)）。最后，我們將用一個(gè)最多 4 字節(jié) 32 位大小對象的位集合和一個(gè)比 32 位大的 64 位小的位集合一起作為一個(gè) 8 字節(jié)的獨(dú)享。注意這是個(gè)假設(shè)。我們在這個(gè)例子里為了所有的表達(dá)了枚舉的性質(zhì)用了位集合，但位集合可以取不止一個(gè)值，換種說法這是一種多種選擇的多選框。
舉例，每一個(gè) Airbnb 房源都有一些便利工具列表，比如：「熨斗」、「洗衣機(jī)」、「電視」、「wifi」、「掛衣架」、「煙霧探測器」甚至「適用于筆記本電腦的書桌」等。這里也許有超過 20 種便利工具，我們用 20 這個(gè)數(shù)字是因?yàn)?Airbnb 網(wǎng)站上可以用 20 個(gè)選項(xiàng)過濾。如果一個(gè)房源有所有的上述便利措施（在截圖中看），我們在對應(yīng)的位集合的位置上標(biāo)注 1 就好。
位集合（Bitset）允許儲(chǔ)存 20 個(gè)不同數(shù)據(jù)而只用 20 個(gè)字節(jié)。
舉例，檢查一個(gè)房源有沒有「洗衣機(jī)」：
bool HasWasher(AirbnbHome* h)
{
return h->amenities[2];
}
或者更專業(yè)一點(diǎn)：
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ù)編譯錯(cuò)誤，我們只想強(qiáng)調(diào)該問題背后用向量表征特征的觀念。同樣的觀念可以用在「入住守則」、「房間類型」和其它特征上。
最后，對于國家編碼和城市名。像上面代碼注釋中提到的一樣（看標(biāo)注），我們不會(huì)儲(chǔ)存經(jīng)緯度來避免地理-空間問題，我們儲(chǔ)存國家代碼和城市名字來縮小用地名搜索的范圍（為了簡介省略街名，原諒我）。國家代碼可以被用兩個(gè)字符，3 個(gè)字符或者 3 個(gè)數(shù)字來表示，我們會(huì)用 ushort 儲(chǔ)存數(shù)字表達(dá)。不幸的是，城市比國家多了太多，所以我們不能使用「城市編碼」，我們只會(huì)儲(chǔ)存真實(shí)的城市名，保留平均 0 為 50 字節(jié)的城市名字和特別的名字。我們最好用一個(gè)附加的布爾變量來表示這是不是一個(gè)特別長的名字，所以我們將會(huì)加上附加的 32 字節(jié)來保證最終的結(jié)構(gòu)大小。我們也假設(shè)在 64 位系統(tǒng)上工作，即使我們?yōu)?int 何 short 選擇了非常緊湊的值。
// Note the comments
struct AirbnbHome
{
wstring name; // 200 bytes
uint price; // 4 bytes
uchar rating; // 1 byte
uint rating_count; // 4 bytes
vector photos; // 100 bytes
string host_id; // 20 bytes
uchar adults_number; // 1 byte
uchar children_number; // 1 byte
uchar infants_number; // 1 byte
bitset home_type; // 4 bytes
uchar beds_number; // 1 byte
uchar bedrooms_number; // 1 byte
uchar bathrooms_number; // 1 byte
bitset accessibility; // 4 bytes
bool superhost; // 1 byte
bitset amenities; // 4 bytes
bitset facilities; // 4 bytes
bitset property_types; // 8 bytes
bitset host_languages; // 4 bytes, correct me if I'm wrong
bitset house_rules; // 4 bytes
ushort country_code; // 2 bytes
string city; // 50 bytes
};
所以，420 字節(jié)加上 32 個(gè)多出的字節(jié)，若我們四舍五入到 500 字節(jié)。所以每一個(gè)對象「home」最多占 500 字節(jié)，并且對于所有房源列表，500 字節(jié)*4 百萬=1.86Gb ~2Gb。我們在搭建結(jié)構(gòu)時(shí)做了很多假設(shè)，讓儲(chǔ)存在內(nèi)存中更便宜。無論我們對這數(shù)據(jù)做什么，我們需要至少 2Gb 內(nèi)存。如果你無聊，忍著，我們剛開始。
現(xiàn)在是任務(wù)最難的地方了，為這個(gè)問題選擇合適的數(shù)據(jù)結(jié)構(gòu)（來盡可能有效的過濾表）不是最難的任務(wù)。最難的是（對我而言）按照一系列濾波器搜索列表。如果只有一個(gè)搜索鍵（key）（即只有一個(gè)濾波器），我們可以很輕易地解決這個(gè)問題。假設(shè)用戶只關(guān)心價(jià)格，我們需要的只是在給定的范圍以價(jià)格下降的順序找到 Airbnbhome 對象（合適的家）。如果我們要用二元搜索樹來解決這個(gè)問題，則可按下圖形式執(zhí)行。
如果需要遍歷所有的 4 百萬個(gè)對象，這搜索樹會(huì)長得很大很大。另外，需要占用的內(nèi)存也會(huì)越來越多。這只是因?yàn)槲覀冇昧硕阉鲾?shù)來存儲(chǔ)對象，每一個(gè)樹節(jié)點(diǎn)給它的左右子樹兩個(gè)額外的指針，加起來是每個(gè)子指針有 8 個(gè)額外的比特（假設(shè)是 64 位系統(tǒng)）。對于 400 百萬節(jié)點(diǎn)它加起來就是 62Mb，對于 2Gb 對象的數(shù)據(jù)來說是很小的，但還是不能輕易地「忽略」。
目前為止，上面展示的樹表明了任何物品都可以很輕易地在 O（logN）復(fù)雜度內(nèi)被找到。如果你對這些概念不熟悉，我們會(huì)在接下來解釋清楚，或者跳過復(fù)雜度討論的副章節(jié)。
算法復(fù)雜度：我們在這里快速地簡要介紹，在之后的文章「Algorithmic Complexity and Software Performance: the missing manual」我會(huì)進(jìn)行詳細(xì)的解釋。在大部分情況里，找到一個(gè)算法的「大 O」復(fù)雜度是簡單的。首先要注意到，我們總是考慮最差的情況，即：一個(gè)算法要最多算多少次才能產(chǎn)生一個(gè)合適的結(jié)果（用來解決問題）。
假設(shè)一個(gè)有 100 個(gè)元素的未排序數(shù)列，要做多少次的比較才能讓它找到任意的元素，這里也要考慮到需要的元素可能缺失的情況？它最多需要與匹配的數(shù)字比較 100 次才能發(fā)現(xiàn)，盡管有時(shí)候第一個(gè)在數(shù)列中的元素就是要找的數(shù)字（意味著單次比較就找到答案了），但我們只考慮最差的可能情況（元素可能丟失了或者在最后的位置）。
計(jì)算算法復(fù)雜度的重點(diǎn)是找到運(yùn)算次數(shù)與輸入規(guī)模之間的依賴關(guān)系，舉例來說，上面的數(shù)列有 100 個(gè)元素，運(yùn)算的次數(shù)也是 100，如果數(shù)列的數(shù)量（輸入）增長到 1423，運(yùn)算次數(shù)也會(huì)增長到 1423（最差的情況）。所以，輸入和運(yùn)算次數(shù)之間的關(guān)系在這里是非常清晰的，它也被叫做線性關(guān)系，運(yùn)算次數(shù)和數(shù)列的增長一樣快。增長是復(fù)雜度的關(guān)鍵，我們說在一個(gè)未排序的數(shù)列中搜索需要 O（N）次運(yùn)算，來強(qiáng)調(diào)尋找它需要最多用 N 次運(yùn)算，（甚至最多到 N 的常數(shù)倍數(shù)運(yùn)算，比如 3N 次）。另一方面，訪問數(shù)列上的任意元素只需要常數(shù)時(shí)間，比如 O（1）。這是因?yàn)閿?shù)列的結(jié)構(gòu)是一個(gè)連續(xù)結(jié)構(gòu)，并且包含相同類型的元素，所以訪問特定的元素只需要計(jì)算它與數(shù)列第一個(gè)元素的相對位置。
有一點(diǎn)非常明確，二元搜索樹按排序順序保存其節(jié)點(diǎn)。那么在二元搜索樹中搜索元素的算法復(fù)雜度是多少呢？我們應(yīng)該在最壞的情況下計(jì)算查找元素所需的操作次數(shù)。
見上圖，當(dāng)我們開始在根部搜索時(shí)，第一次匹配可能會(huì)導(dǎo)致三種情況：
（1）目標(biāo)節(jié)點(diǎn)被發(fā)現(xiàn)；
（2）如果要找的值小于節(jié)點(diǎn)的值，則匹配將繼續(xù)到節(jié)點(diǎn)的左子樹；
（3）如果要找的值大于節(jié)點(diǎn)的值，則匹配將繼續(xù)到節(jié)點(diǎn)的右子樹。
在每一步中我們都把節(jié)點(diǎn)的數(shù)量減半。在二元搜索樹中查找元素所需的操作數(shù)等于樹的高度。樹的高度是最長路徑上節(jié)點(diǎn)的數(shù)量。在這一案例中，高度是 4。所以高度等于 logN+1（底數(shù)為 2），搜索復(fù)雜度是 O（logN+1）=O（logN）。這意味著在 4 百萬個(gè)節(jié)點(diǎn)里搜索元素需要 log1000000=~22 次比較（最差的情況）。
回到樹搜索的問題，二元搜索樹中的元素搜索時(shí)間為 O（logN）。為什么不使用哈希表？哈希表有常數(shù)的訪問時(shí)間，這使得在幾乎任何地方使用哈希表都是合理的。
在該問題中，我們必須考慮一個(gè)重要的需求，即執(zhí)行范圍搜索，如搜索價(jià)格區(qū)間在$80 到 $162 之間的房源。在二元搜索樹的情況下，獲取區(qū)間中所有節(jié)點(diǎn)很簡單，只需對樹執(zhí)行順序遍歷，保存計(jì)數(shù)即可。而哈希表的計(jì)算稍微昂貴，在這種情況下使用堅(jiān)持二元搜索樹更好一些。盡管還存在另一個(gè)因素，使我們需要重新考慮哈希表：密度。價(jià)格不會(huì)「一直」上漲，大部分房源處于固定的價(jià)格區(qū)間內(nèi)。截圖中的柱狀圖顯示了價(jià)格的真實(shí)分布，數(shù)百萬房源處于同一區(qū)間（$18—$212），它們具備同樣的平均價(jià)格。簡單的數(shù)組可能起到很好的效果。假設(shè)數(shù)組的索引是價(jià)格，則我們能夠在（幾乎）常數(shù)時(shí)間內(nèi)獲取任意價(jià)格區(qū)間。如下圖所示：
就像一個(gè)哈希表，我們通過房源的價(jià)格來匹配每一套房子。所有具有相同價(jià)格的房源都?xì)w入單獨(dú)的二元搜索樹。如果我們存儲(chǔ)房源的 ID 而不是上面定義的完整對象（AirbnbHome 結(jié)構(gòu)），也可以節(jié)省一些空間。最可能的情況是將所有房源的完整對象保存在哈希表，并將房源 ID 映射到房源的完整對象中，以及保存另一個(gè)哈希表（或更好的，一個(gè)數(shù)組），該哈希表將價(jià)格與房源 ID 進(jìn)行映射。因此，當(dāng)用戶請求價(jià)格范圍時(shí)，我們從價(jià)格表中獲取房源 ID，將結(jié)果裁剪成固定大小（即分頁，通常在一頁上顯示 10-30 個(gè)項(xiàng)目），然后使用每個(gè)房源 ID 獲取完整的房源對象。請記得，要注意平衡。平衡對二元搜索樹至關(guān)重要，因?yàn)樗窃?O（logN）內(nèi)完成樹操作的唯一保證。當(dāng)你按排序順序插入元素時(shí)，二元搜索樹不平衡的問題就會(huì)很明顯，最終，樹將變成連接列表，這顯然會(huì)導(dǎo)致線性時(shí)間復(fù)雜度。現(xiàn)在假設(shè)我們所有的搜索樹都是完美平衡的。再看看上面的圖。每個(gè)數(shù)組元素代表一棵大樹。如果我們改變這個(gè)樹，變成圖呢？
這是一個(gè)「更接近真實(shí)」的圖。這個(gè)圖展示了最隱蔽的數(shù)據(jù)結(jié)構(gòu)和圖，帶領(lǐng)我們到了（下文）。
圖表征：進(jìn)階
圖論的缺點(diǎn)是缺乏單獨(dú)定義，這就是為什么你無法在庫中找到 std::graph。我們已經(jīng)嘗試過表示「特別的」圖 BST。重點(diǎn)在于，樹是圖，但圖未必是樹。最后一張示例圖表明在一個(gè)抽象圖下面有很多樹，「價(jià)格 vs 房源」和一些節(jié)點(diǎn)的類型不同，價(jià)格只有價(jià)格值的圖節(jié)點(diǎn)，表示滿足特定價(jià)格的房源 ID（房源節(jié)點(diǎn)）的樹。這很像混合數(shù)據(jù)結(jié)構(gòu)，不同于我們在教科書示例中見到的簡單圖形。圖表示的重點(diǎn)：不存在固定、「權(quán)威」的圖表示結(jié)構(gòu)（這與 BST 不同，后者用左／右子指針代表基于節(jié)點(diǎn)的特定表示，盡管你可以用一個(gè)數(shù)組表示 BST）。你可以用最便捷的方式表示一個(gè)圖，重點(diǎn)在于你把它「看作」是圖?！缚磮D」的意思是使用適用于圖的算法。
N-ary 樹更像是模擬一個(gè)圖。
首先，將 N-ary 樹節(jié)點(diǎn)表示為：
struct NTreeNode
{
T value;
vector children;
};
該結(jié)構(gòu)僅表示樹的一個(gè)節(jié)點(diǎn)，完整的樹如下所示：
// almost pseudocode
class NTree
{
public:
void Insert(const T&);
void Remove(const T&);
// lines of omitted code
private:
NTreeNode* root_;
};
該類別是圍繞單個(gè)樹節(jié)點(diǎn) root_ 的抽象。我們可以用它構(gòu)建任意大小的樹。這是樹的起點(diǎn)。如果要添加新的樹節(jié)點(diǎn)，我們就要為其分配內(nèi)存，將該節(jié)點(diǎn)添加至樹的根節(jié)點(diǎn)處。
圖與 N-ary 樹很像，只有細(xì)微的不同。我們來看一下。
這是圖嗎？我認(rèn)為，是的。但這幅圖與前面的 N-ary 相同，只不過稍微旋轉(zhuǎn)了一下。只要你看到一棵樹，無論它是蘋果樹、檸檬樹，還是二叉搜索樹，你都可以確定它也是一張圖。因此，通過設(shè)計(jì)圖節(jié)點(diǎn)（圖節(jié)點(diǎn)）結(jié)構(gòu)，我們能夠提出同樣的結(jié)構(gòu)：
struct GraphNode
{
T value;
vector adjacent_nodes;
};
這樣可以創(chuàng)建圖嗎？還不夠?？聪旅鎯煞鶊D，找不同：
二者都是圖
左側(cè)的圖沒有可以「進(jìn)入」的點(diǎn)（與其說是樹，它更像森林），相反，右側(cè)的圖沒有不可達(dá)的節(jié)點(diǎn)，聽起來很熟悉。
如果圖中任意兩點(diǎn)都是連通的，那么該圖被稱作連通圖。
雖然圖中不明顯，但是我們假設(shè)價(jià)格不能互相連接，那么在「價(jià)格 vs 房源」圖中并不是每對節(jié)點(diǎn)之間都有路徑相連，這說明我們無法使用單個(gè) GraphNode 結(jié)構(gòu)構(gòu)建圖的例子，但是在很多案例中我們必須這樣處理非連通圖?？聪旅孢@個(gè)類別：
class ConnectedGraph
{
public:
// API
private:
GraphNode* root_;
};
類似圍繞單個(gè)節(jié)點(diǎn)（根節(jié)點(diǎn)）構(gòu)建的 N-ary 樹，連通圖也可以圍繞根節(jié)點(diǎn)構(gòu)建。樹有「根」，即它們有起始點(diǎn)。連通圖可以用帶有根節(jié)點(diǎn)的樹來表示（當(dāng)然還有其他屬性），不過要注意，實(shí)際的表示可能會(huì)隨著算法或具體問題發(fā)生變化。但是，考慮基于節(jié)點(diǎn)的圖本質(zhì)，非連通圖可以按照下面的方式來表示：
class DisconnectedGraphOrJustAGraph
{
public:
// API
private:
std::vector all_roots_;
};
樹狀圖可以清晰自然地表示 DFS/BFS 這樣的圖遍歷。但是，高效路徑追蹤等需要不同的表示方法。還記得歐拉圖嗎？為了追蹤圖的「eulerness」（真實(shí)性），我們應(yīng)該追蹤圖中的歐拉路徑。這意味著遍歷每個(gè)邊一次就要訪問所有節(jié)點(diǎn)；如果追蹤結(jié)束后我們?nèi)杂形幢闅v的邊，則該圖沒有歐拉路徑，因此它不是歐拉圖。更快的方法是：檢查節(jié)點(diǎn)的度（假設(shè)每條邊都保存了度），如定義所述，如果圖的節(jié)點(diǎn)度是奇數(shù)，則它不是歐拉圖。該檢查的復(fù)雜度是 O(|V|)，其中 |V| 是圖節(jié)點(diǎn)的數(shù)量。我們可以在插入新的邊緣的同時(shí)追蹤節(jié)點(diǎn)的奇數(shù)／偶數(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
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 ToString()
}
}
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è)，比如標(biāo)簽，我們可以通過節(jié)點(diǎn)理解字符串標(biāo)簽，確保你可以將其更新成任意事物。接下來，是命名。如注釋中所述，VELOGraph 僅適用于 Vertex Edge Label Only Graph。重點(diǎn)在于，該圖表示包括一個(gè)將節(jié)點(diǎn)標(biāo)簽映射至節(jié)點(diǎn)關(guān)聯(lián)邊的表、一個(gè)包含與邊相連的兩個(gè)節(jié)點(diǎn)的邊列表，和一個(gè)僅用于 Trace() 函數(shù)的 flag。查看 Trace() 函數(shù)實(shí)現(xiàn)，它使用邊的 flag 來標(biāo)記已經(jīng)遍歷過的邊（在任意 Trace() 調(diào)用之后應(yīng)該重置 flag）。
示例：Twitter
另一種表示叫做相鄰矩陣，它在有向圖中有用，就像我們在 Twitter 關(guān)注圖中所使用的那樣。
有向圖
推特案例中有 8 個(gè)節(jié)點(diǎn)，所以我們需要使用|V|x|V|的二維矩陣表征這個(gè)圖（其中 |V|分別代表行數(shù)和列數(shù)）。如果從 v 到 u 有一條有向邊，那么我們稱矩陣的元素 [v][u] 為真，否則為假。
如你所見，這是一個(gè)十分稀疏的矩陣，其中的值代表是否有單向連接路徑。如果我們需要了解 Patrick 是否關(guān)注了 Bob 的推特，那么我們只需要查看矩陣中 ['Patrick']['Sponge Bob'] 的值是不是等于 1。而要查看 Ann 推特的關(guān)注者，我需要獲得「Ann」的整個(gè)列；同樣查看 Sponge Bob 正在關(guān)注的人只需要查看「Sponge Bob」的行就行。此外，鄰接矩陣（Adjacency matrix）可以用來描述無向圖，它不會(huì)在 v 到 u 的邊選擇值「0 或 1」來表示是否有連接，它會(huì)同時(shí)設(shè)置兩個(gè)方向的值都為 1，即 adj_matrix[v][u] = 1 和 adj_matrix[u][v] = 1。因此，無向圖的鄰接矩陣為對稱矩陣。
注意，在通常情況下我們在鄰接矩陣中并不會(huì)只儲(chǔ)存 0 和 1，我們可以儲(chǔ)存一些更具信息的值，例如邊權(quán)重等。最好的案例可能是帶有距離信息的地圖。
上圖表示了 Patrick 和 Sponge Bob 等人之間的距離（也稱為加權(quán)圖）。如果節(jié)點(diǎn)間沒有沒有直接路徑，那么我們就把它設(shè)為無窮大，它既不意味著根本沒有路徑，也不意味著一定有路徑。它可以在應(yīng)用算法搜索兩個(gè)節(jié)點(diǎn)間路徑時(shí)定義。當(dāng)然，我們還有更好的方法來儲(chǔ)存節(jié)點(diǎn)和邊之間的關(guān)系，如關(guān)聯(lián)矩陣。
盡管鄰接矩陣對推特關(guān)注關(guān)系有很好的表征，但將 3 億用戶（每月活躍用戶）儲(chǔ)存在矩陣中需要 300*300*1（百萬字節(jié)/布爾值）的儲(chǔ)存空間。也就是約有 82000Tb（Terabyte）或需要 1024 * 82000 Gb 的儲(chǔ)存空間。BitBoard 可以幫助我們減少一些空間需求，大約可以降低到 10000Tb，但還是太大。如上所述，鄰接矩陣稀疏要求我們提供比實(shí)際需求更多的空間，這也就是為什么邊的列表映射到節(jié)點(diǎn)可能會(huì)很有用。重點(diǎn)是，鄰接矩陣允許保持關(guān)注和不關(guān)注的信息，而我們需要的僅僅是知道如下內(nèi)容：
鄰接矩陣與鄰接列表
右圖表示鄰接列表（adjacency list），每個(gè)列表描述了圖中的一組鄰近節(jié)點(diǎn)。在圖表中，我們突出了哈希表的用法，因?yàn)槿魏喂?jié)點(diǎn)的訪問復(fù)雜度都是 O（1）。而且對于鄰近節(jié)點(diǎn)列表，我們并沒有提到任何具體的數(shù)據(jù)結(jié)構(gòu)，也不會(huì)從列表轉(zhuǎn)化為向量。重點(diǎn)是，如果要確定 Patrick 是否關(guān)注 Liz，我們應(yīng)該遍歷哈希表中每一個(gè)元素（常數(shù)時(shí)間），而鄰近矩陣需要查看每一個(gè)與 Liz 相關(guān)的元素（線性時(shí)間）。線性時(shí)間在這一點(diǎn)上并不是那么糟，因?yàn)槲覀兘?jīng)需要循環(huán)與 Patrick 相關(guān)的固定數(shù)目的節(jié)點(diǎn)。
如果我們用空間復(fù)雜度表示推特，這需要 3 億個(gè)哈希表記錄，每個(gè)記錄指向一個(gè)向量（選擇向量以避免鏈表的左/右指針?biāo)a(chǎn)生的內(nèi)存開銷）。此外，雖然沒有統(tǒng)計(jì)數(shù)據(jù)，但平均推特關(guān)注的人數(shù)是 707 個(gè)。所以如果我們考慮每個(gè)哈希表記錄指向一個(gè)有 707 個(gè)用戶 ID 的數(shù)組，且每個(gè) ID 有 8 個(gè)字節(jié)，那么現(xiàn)在我們可以計(jì)算出儲(chǔ)存空間約為 12TB。
現(xiàn)在少很多了，但我們?nèi)匀徊淮_定 12TB 是否是一個(gè)合理的數(shù)字。如果在 32Gb RAM 的專用服務(wù)器上一個(gè)月需要 30 美元，那么 12TB 加上一些控制服務(wù)器和備用服務(wù)器等（約需要額外兩倍數(shù)量）核算下來需要 1500 臺(tái)服務(wù)器，每月的成本達(dá)到了 45K 美元。這對于我們來說當(dāng)然是難以接受的價(jià)格，但對于推特來說就非常便宜了。但推特需要提高響應(yīng)的速度，即用戶發(fā)的推文需要第一時(shí)間發(fā)送給關(guān)注的人。但理想的時(shí)間是多少？我們并不能作出任何假設(shè)和抽象，因此我們可以探討一下現(xiàn)實(shí)世界產(chǎn)品系統(tǒng)的響應(yīng)。以下是我們在推文時(shí)經(jīng)常遇到情況。
同樣我們并不知道一條推文需要多少時(shí)間才能發(fā)送到所有的關(guān)注者，但公開的數(shù)據(jù)表明每天約有 500 億條推文。所以經(jīng)驗(yàn)看來一般推文的時(shí)間在 5 秒內(nèi)，同時(shí)我們還要注意哪些擁有超百萬粉絲的名人，推特可能會(huì)分配更多的資源來推送名人「超級有用」的內(nèi)容。
為了解決推文的分發(fā)問題，我們并不需要以下的圖，我們需要關(guān)注者的列表。前面的哈希表和一些列表允許我們高效地搜索特定關(guān)注者關(guān)注的所有用戶，但它并不允許高效地搜索關(guān)注特定用戶所有關(guān)注者，因此我們必須掃描所有的哈希表鍵值。這也就是為什么我們應(yīng)該構(gòu)建另一個(gè)圖，它與以下我們展示的圖對稱相反。這個(gè)新的圖由包含 3 億個(gè)節(jié)點(diǎn)的哈希表組成，每個(gè)節(jié)點(diǎn)指向相鄰節(jié)點(diǎn)的獵鳥（結(jié)構(gòu)相同），但是這次相鄰節(jié)點(diǎn)的列表將表示關(guān)注者。
因此基于該示例，無論何時(shí) Liz 發(fā)推特，Spone Bob 和 Ann 都必須在他們的時(shí)間線上找到特定的推文。一項(xiàng)普遍使用的解決該問題的技術(shù)是為每個(gè)用戶的時(shí)間線保持獨(dú)立的結(jié)構(gòu)。假設(shè)推特有 3 億的用戶，我們可以假定至少存在 3 億個(gè)時(shí)間線（每人一個(gè)）。簡單的說，無論何時(shí)發(fā)推，我們應(yīng)該找到他的關(guān)注者并且更新他們的時(shí)間軸，時(shí)間線可以被表征成連結(jié)串列或平衡樹（以推文的日期作為節(jié)點(diǎn)關(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);
}
}
這僅僅是基本思想，從真實(shí)的時(shí)間線表征抽象得到。當(dāng)然如果使用多線程，我們可以將實(shí)際的傳送過程變得更快。這對于大規(guī)模案例非常關(guān)鍵，因?yàn)閷τ诎偃f級別的關(guān)注者，接近列表終點(diǎn)的用戶在處理上通常慢于接近列表前面的用戶。以下的偽代碼將嘗試解釋該多線程傳送思想。
// Warning: a bunch of pseudocode ahead
void 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(); // somehow
t.Run(RangeInsertIntoTimelines, current_chunk, tw->id);
}
}
因此無論關(guān)注者在什么時(shí)候刷新推特，他們都能收到新的推文。當(dāng)然，我們僅僅討論了 Airbnb 或推特面臨問題的冰山一角，還有很多問題需要各位讀者共同探討。
推特的推文分發(fā)問題關(guān)鍵在于對圖的利用，即使我們不使用任何的圖算法，僅用圖表示。而真正的圖算法是相當(dāng)復(fù)雜的。在使用圖表示之前，我們討論了 Airbnb 房源和高效過濾的問題，主要困難在于當(dāng)過濾器關(guān)鍵字超過一個(gè)的時(shí)候，就無法高效地過濾家園。那么使用圖算法能帶來什么好處嗎？值得一試。我們可以將每個(gè)過濾器表示成一個(gè)獨(dú)立的節(jié)點(diǎn)，每個(gè)過濾器可以代表特定的屬性（價(jià)格、城市名、國家、生活設(shè)施等）。
Airbnb 過濾器節(jié)選
我們還可以通過添加高層的節(jié)點(diǎn)，例如「生活設(shè)施」節(jié)點(diǎn)來連接所有生活設(shè)施類的節(jié)點(diǎn)（WiFi、電視等），使該集合更容易理解。
擁有高級類型的 Airbnb 過濾器
現(xiàn)在，我們可以將 Airbnb 房源（home）表示成節(jié)點(diǎn)，然后將這些節(jié)點(diǎn)和對應(yīng)的屬性節(jié)點(diǎn)連接起來。
這個(gè)插圖的微妙變化使它更像一種特殊類型的圖形，稱為偶圖（bipartite graph）。
節(jié)點(diǎn)的數(shù)量比看起來的更多
偶圖的節(jié)點(diǎn)可以分為兩個(gè)不相交和獨(dú)立的集合，這樣每個(gè)邊就將一個(gè)集合的節(jié)點(diǎn)連接到另一個(gè)集合的節(jié)點(diǎn)。在我們的例子中，其中一個(gè)表征過濾器（我們用 F 表示），另一個(gè)表征房源集合（H）。例如，如果有價(jià)值 62 美元的 10 萬個(gè)房源，則標(biāo)記為「$ 62」的價(jià)格節(jié)點(diǎn)將具有 10 萬條邊入射到每個(gè)房源的節(jié)點(diǎn)。
如果我們測量空間復(fù)雜度的最壞情況，即每個(gè)家庭具有滿足所有過濾器的所有屬性，則要存儲(chǔ)的邊總量將為 7 萬×400 萬。如果我們將每個(gè)邊表示為一個(gè) ID 對：，如果我們重新考慮 ID，并使用 4 個(gè)字節(jié)（int）數(shù)字 ID 為過濾器 ID，8 個(gè)字節(jié)（long）ID 為房源使用的 ID，那么每個(gè)邊緣至少需要 12 個(gè)字節(jié)。因此，存儲(chǔ) 7 萬* 400 萬個(gè) 12 字節(jié)值需要大約 3TB 的內(nèi)存。我們在計(jì)算中犯了一個(gè)小錯(cuò)誤，由于在 Airbnb 中有 65,000 個(gè)活躍城市，因此過濾器的數(shù)量約為 7 萬個(gè)（統(tǒng)計(jì)數(shù)據(jù)）。
好消息是，同一個(gè)家庭不能位于不同的城市。也就是說，我們實(shí)際與城市邊配對的數(shù)量是 400 萬（每個(gè)家庭位于一個(gè)城市），因此我們將計(jì)算 70k-65k = 5000 個(gè)過濾器，這意味著我們需要 5000 * 400 萬* 12 個(gè)字節(jié)的內(nèi)存，小于 0.3Tb。聽起來不錯(cuò)。但是什么給了我們這個(gè)偶圖？最常見的網(wǎng)站/移動(dòng)請求將由多個(gè)過濾器組成，例如：
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é)點(diǎn)，并處理與其鄰近所有「房源」的節(jié)點(diǎn)。
圖算法
或許，任何用圖執(zhí)行的計(jì)算過程都可以分類為「圖算法」，你可以實(shí)現(xiàn)一個(gè)輸出圖的所由節(jié)點(diǎn)的函數(shù)，然后將其命名為「的節(jié)點(diǎn)輸出算法」。但真正可怕的是教科書中列出的圖算法：
Coloring
Hopcroft–Karp
Hungarian
Prüfer coding
Tarjan's off-line least common ancestors
Topological sort
我們嘗試使用偶圖匹配算法，例如 Hopcroft–Karp 算法到 Airbnb 房源過濾問題：
給定一個(gè) Airbnb 房源（H）的偶圖和過濾器（F），其中 H 的每個(gè)節(jié)點(diǎn)可以多于 F 的一個(gè)相鄰節(jié)點(diǎn)（共享一個(gè)公共邊）。尋找 H 的由節(jié)點(diǎn)構(gòu)成的子集，該子集和 F 的子集的節(jié)點(diǎn)相鄰。
問題的定義很難理解，并且目前我們還不確定 Hopcroft-Karp 算法可以解決該問題，但我們可以在求解的過程中學(xué)到很多圖算法的關(guān)鍵思想。這個(gè)過程不會(huì)很短，需要你有耐心。Hopcroft-Karp 算法以二分圖為輸入，并生成最大基數(shù)匹配的輸出，該輸出是一個(gè)包含盡可能多的邊的集合，其中沒有任何兩條邊共享同一個(gè)端點(diǎn)。熟悉該算法的讀者已經(jīng)注意到，這并不能解決我們的問題，因?yàn)槠ヅ溥^程的條件是沒有任何兩條邊共享同一個(gè)節(jié)點(diǎn)。我們來看一個(gè)示例展示，其中只有 4 個(gè)過濾器和 8 個(gè)房源（為簡單起見）。這些房源用字母 A 到 H 標(biāo)記，過濾器是隨機(jī)選擇的。從 A 到 H 的所有房源都是 50 美元每晚的價(jià)格和一張床，但很少有供應(yīng) WiFi 和/或電視的。因此以下的示例過程將嘗試找到滿足四個(gè)條件的房源（擁有 4 個(gè)過濾器）。
對該問題的求解需要找到和特定的房源連接的所有邊，該房源節(jié)點(diǎn)和相同的過濾器子集關(guān)聯(lián)。而 Hopcroft-Karp 算法將移除公共端點(diǎn)的邊，并生成和兩個(gè)子集都關(guān)聯(lián)的邊。
查看上圖，我們需要尋找的是房源 D 和 G，它們滿足了所有四個(gè)過濾器值。我們真正需要的是找到共享端點(diǎn)的所有匹配邊。我們可以為該方法設(shè)計(jì)一個(gè)算法，但其處理時(shí)間可以說和用戶需求并不相關(guān)（用戶需求=快速）。也許創(chuàng)建一個(gè)平衡的多分類關(guān)鍵字的二值搜索樹會(huì)更快，差不過類似于數(shù)據(jù)庫索引文件，其將主關(guān)鍵字和外鍵映射到滿足條件的記錄集合。我們將在另一篇文章中獨(dú)立討論平衡二值搜索樹和數(shù)據(jù)庫索引，到時(shí)會(huì)再次返回到 Airbnb 房源問題上。
Hopcroft-Karp 算法（以及很多其它算法）都基于 DFS（深度優(yōu)先搜索）和 BFS（廣度優(yōu)先搜索）的圖遍歷算法。說實(shí)話，這里介紹 Hopcroft-Karp 算法的真正原因是逐漸轉(zhuǎn)換到圖遍歷算法的討論，相比從二值樹開始討論會(huì)更好。
二值樹遍歷非常漂亮，這大多是因?yàn)樗鼈兊倪f歸本質(zhì)。有三種基本的遍歷方式稱為中序（in-order）、后序（post-order）和前序（pre-order）。如果你曾經(jīng)遍歷過連結(jié)串列，這些概念是很好懂的。在連結(jié)串列中，你只需要輸出當(dāng)前節(jié)點(diǎn)的值（在下方的代碼中稱為 item），并繼續(xù)到達(dá)下一個(gè)節(jié)點(diǎn)。
// struct ListNode {
// ListNode* next;
// T item;
// };
void TraverseRecursive(ListNode* node) // starting node, most commonly the list 'head'
{
if (!node) return; // stop
std::cout item;
TraverseRecursive(node->next); // recursive call
}
void TraverseIterative(ListNode* node)
{
while (node) {
std::cout item;
node = node->next;
}
}
這和二值樹幾乎相同，輸出節(jié)點(diǎn)的值，然后到達(dá)下一個(gè)節(jié)點(diǎn)，但在這里，「下一個(gè)」指的是兩個(gè)節(jié)點(diǎn)，左節(jié)點(diǎn)和右節(jié)點(diǎn)。因此你需要分別到達(dá)左節(jié)點(diǎn)和右節(jié)點(diǎn)。不過你有三個(gè)不同的選擇：
輸出節(jié)點(diǎn)值，然后到達(dá)左節(jié)點(diǎn)，再到達(dá)右節(jié)點(diǎn)。
到達(dá)左節(jié)點(diǎn)，然后輸出節(jié)點(diǎn)值，再到達(dá)右節(jié)點(diǎn)。
到達(dá)左節(jié)點(diǎn)，然后到達(dá)右節(jié)點(diǎn)，再輸出節(jié)點(diǎn)值。
// 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' node
void PreOrderTraverse(TreeNode* node)
{
if (!node) return; // stop
std::cout 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; // stop
InOrderTraverse(node->left);
std::cout item;
InOrderTraverse(node->right);
}
void PostOrderTraverse(TreeNode* node)
{
if (!node) return; // stop
PostOrderTraverse(node->left);
PostOrderTraverse(node->right);
std::cout item;
}
前序遍歷的細(xì)節(jié)追蹤
很明顯遞歸函數(shù)的形式很優(yōu)雅，雖然其計(jì)算成本很高。每次我們遞歸地調(diào)用一個(gè)函數(shù)，也就意味著我們調(diào)用了一個(gè)完全的新函數(shù)（如上圖所示）。其中「新」的意思是函數(shù)變量和局域變量需要分配其它的堆棧內(nèi)存空間。這正是為什么遞歸調(diào)用的成本如此高（額外的堆棧空間分配和多函數(shù)調(diào)用）和危險(xiǎn)（堆棧溢出），很明顯地使用迭代實(shí)現(xiàn)會(huì)更好。在關(guān)鍵任務(wù)（航空、NASA 探測車等）的系統(tǒng)編程中，遞歸調(diào)用是完全禁止的。
實(shí)例：Netflix
假設(shè)我們要將所有 Netflix 電影存儲(chǔ)在二進(jìn)制搜索樹中，并將電影標(biāo)題作為排序鍵。所以無論何時(shí)用戶輸入類似「Inter」的內(nèi)容，我們都會(huì)返回一個(gè)以「Inter」開頭的電影列表，舉例，[「Interstellar」,「Interceptor」,「Interrogation of Walter White」]。如果我們將返回標(biāo)題中包含「Inter」的所有電影（不僅僅是以「Inter」開頭的電影）那就太好了，并且該列表將根據(jù)電影的評分或與該特定用戶相關(guān)的內(nèi)容進(jìn)行排序（喜歡驚悚片比戲劇更多）。這個(gè)例子的重點(diǎn)在于對 BST 進(jìn)行有效的范圍查詢，但像往常一樣，我們不會(huì)深入探討其余部分?；旧?，我們需要通過搜索關(guān)鍵字進(jìn)行快速查找，然后獲得按關(guān)鍵字排序的結(jié)果列表，這很可能應(yīng)該是電影評級和/或基于用戶個(gè)性化數(shù)據(jù)的內(nèi)部排名。我們會(huì)盡可能地堅(jiān)持 KISK 原則（Keep It Simple，Karl）。
「KISK」或「讓我們保持它的簡單」或「為了簡單起見」，這是教程編寫者從真實(shí)問題中抽象出來的超級借口，并通過在偽代碼中引入「abc」簡單示例及其解決方案來做出大量假設(shè)，并且這些答案在很老的筆記本電腦上也能工作。
這個(gè)問題可以很容易地應(yīng)用到亞馬遜的產(chǎn)品搜索上，因?yàn)槲覀兺ǔＭㄟ^輸入描述我們興趣的文本（如「圖算法」）來搜索亞馬遜的東西，并根據(jù)產(chǎn)品的評分獲得結(jié)果（我沒有在亞馬遜的個(gè)性化結(jié)果中體驗(yàn)過搜索結(jié)果，但我很確定亞馬遜也是這樣做的）。所以，為了公平將這個(gè)子標(biāo)題改為...
Netflix 和亞馬遜。Netflix 提供電影服務(wù)，亞馬遜提供產(chǎn)品，我們會(huì)將它們命名為「物品」，所以每當(dāng)你閱讀「物品」時(shí)，都會(huì)想到 Netflix 中的電影或亞馬遜的任何 [合格] 產(chǎn)品。這些物品最常用的是解析其標(biāo)題和描述（我們只處理標(biāo)題），所以如果一個(gè)操作員（通常是一個(gè)人通過管理儀表板將項(xiàng)目的數(shù)據(jù)插入 Netflix / Amazon 數(shù)據(jù)庫）插入新項(xiàng)目到數(shù)據(jù)庫中，它的標(biāo)題正在被一些「ItemTitleProcessor」處理以產(chǎn)生關(guān)鍵字。
我知道這并不是最好的圖例（而且有一個(gè)書寫錯(cuò)誤）
每一個(gè)物品都有專屬 ID，這個(gè) ID 也鏈接到了標(biāo)題之中的關(guān)鍵字。這也是搜索引擎在爬全世界的網(wǎng)站時(shí)做的。他們分析每個(gè)文檔的內(nèi)容，對其進(jìn)行標(biāo)記（將其分解為更小的實(shí)體和單詞）并添加到表中，該表將每個(gè)標(biāo)記（詞）映射到標(biāo)記已被「看到」的文檔標(biāo)識（網(wǎng)站）。因此，無論何時(shí)搜索「hello」，搜索引擎都會(huì)獲取映射到關(guān)鍵字「hello」的所有文檔（實(shí)際情況非常復(fù)雜，因?yàn)樽钪匾氖撬阉飨嚓P(guān)性，這就是為什么谷歌搜索非常棒）。所以 Netflix /亞馬遜的類似表格可能看起來像這樣（再次，在閱讀物品時(shí)想一想電影或產(chǎn)品）。
倒排索引
哈希表，再提一次。是的，我們將為此倒排索引（索引結(jié)構(gòu)存儲(chǔ)來自內(nèi)容的映射）保留哈希表。哈希表會(huì)將關(guān)鍵字映射到物品的 BST。為什么選擇 BST？因?yàn)槲覀兿Ｍ３炙鼈兊呐判虿⑼瑫r(shí)提供連續(xù)排序的部分（響應(yīng)前端請求），例如一次請求（分頁）中的 100 個(gè)物品。這并不能說明 BST 的強(qiáng)大功能，但假設(shè)我們還需要在搜索結(jié)果中進(jìn)行快速查找，例如，你需要關(guān)鍵字為「機(jī)器」的所有 3 星電影。
請注意，可以在不同的樹中復(fù)制物品，因?yàn)橥ǔ？梢允褂枚鄠€(gè)關(guān)鍵字找到物品。我們將使用如下面定義的物品進(jìn)行操作：
// Cached representation of an Item
// Full Item object (with title, description, comments etc.)
// could be fetched from the database
struct Item
{
// ID_TYPE is the type of Item's unique id, might be an integer, or a string
ID_TYPE id;
int rating;
};
每次將新物品插入數(shù)據(jù)庫時(shí)，其標(biāo)題都將被處理并添加到大型索引表中，該表將關(guān)鍵字映射到物品。可能有許多物品共享相同的關(guān)鍵字，因此我們將這些物品保存在按照評分排序的 BST 中。當(dāng)用戶搜索某個(gè)關(guān)鍵字時(shí)，他們會(huì)得到按其評分排序的物品列表。我們?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++ fellows
vector GetItemsByKeywordInSortedOrder(string keyword)
{
// 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 in-order traversing the tree
vector sorted_result = items.InOrderProduceVector();
return sorted_result;
}
這里是一種 InOrderProduceVector() 實(shí)現(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_;
};
但是呢，我們首先需要最高評價(jià)的物品，來替換掉按順序遍歷生成最低評級的物品。這是因?yàn)樗男再|(zhì)，是從低到高的順序遍歷物品，「自下而上」。為了得到我們想要的東西，即列表按降序而不是升序排列，我們應(yīng)該仔細(xì)查看順序遍歷實(shí)現(xiàn)。我們所做的是通過左節(jié)點(diǎn)，然后打印當(dāng)前節(jié)點(diǎn)的值和通過右邊的節(jié)點(diǎn)。當(dāng)我們第一次通過左節(jié)點(diǎn)時(shí)，這就是為什么我們首先獲得了「最左」節(jié)點(diǎn)（最左節(jié)點(diǎn)），這是具有最小值的節(jié)點(diǎn)。因此，簡單地將實(shí)現(xiàn)更改為首先通過正確的節(jié)點(diǎn)將導(dǎo)致我們按照列表的降序排列。我們會(huì)像其他人一樣將其命名，這是一種逆序的遍歷。讓我們更新上面的代碼（引入單個(gè)列表、警告、錯(cuò)誤）：
// Reminder: this is pseudocode, no bother with 'const&', 'std::' or others
// forgive me C++ fellows
template
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 limit
ReverseInOrderProduceVectorHelper_(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 element
ReverseInOrderProduceVectorHelper_(node->right, destination, offset, limit);
if (offset
destination.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++ fellows
vector 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)品
這就對了，我們可以非?？焖俚靥峁┪锲匪阉鹘Y(jié)果。如上所示，反轉(zhuǎn)索引在搜索引擎中最常用，例如谷歌搜索。雖然谷歌搜索引擎非常復(fù)雜，它確實(shí)利用了某些簡單的思想，來將搜索查詢匹配到文檔上，并盡可能快速地提供結(jié)果。
我們使用了樹遍歷來以分類排序提供結(jié)果。在這里，前序/順序/后序遍歷可能太多了，但有時(shí)候我們也需要應(yīng)用其它類型的遍歷。讓我們來解決這個(gè)著名的編程面試問題：「如何按等級輸出一個(gè)二值樹等級？」
DFS vs. BFS
如果你對這個(gè)問題不熟悉，想想你在遍歷樹的時(shí)候可用于存儲(chǔ)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)。如果對比分層遍歷樹和上文介紹的其他方式（前序/順序/后序遍歷），就會(huì)發(fā)現(xiàn)兩種主要的圖遍歷方法：深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）。
深度優(yōu)先搜索尋找最遠(yuǎn)的節(jié)點(diǎn)，廣度優(yōu)先搜索先尋找最近的節(jié)點(diǎn)。
深度優(yōu)先搜索——更多動(dòng)作，更少思考。
廣度優(yōu)先搜索——在進(jìn)一步行動(dòng)之前先仔細(xì)觀察四周。
DFS 很像前序/順序/后序遍歷，而 BFS 用于分層輸出樹節(jié)點(diǎn)。我們需要一個(gè)隊(duì)列（數(shù)據(jù)結(jié)構(gòu)）來存儲(chǔ)圖的「層級」，同時(shí)輸出（訪問）其「父級」。在之前的插圖中，節(jié)點(diǎn)是隊(duì)列中淺藍(lán)色的點(diǎn)。每一層的節(jié)點(diǎn)被從隊(duì)列中取走，同時(shí)在訪問每個(gè)被取走的節(jié)點(diǎn)時(shí)，我們還應(yīng)該將其子節(jié)點(diǎn)插入隊(duì)列（為下一層做準(zhǔn)備）。下列代碼很簡單，可以幫助大家了解 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 code
void 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 node
cout item;
}
}
在基于節(jié)點(diǎn)的連通圖表示上可以輕松地了解基本思想。記住圖遍歷的實(shí)現(xiàn)因圖表示而異。BFS 和 DFS 在解決圖搜索問題中是重要的工具（但是存在大量圖搜索算法）。盡管 DFS 具備優(yōu)雅的遞歸實(shí)現(xiàn)，但進(jìn)行迭代實(shí)現(xiàn)更合理。我們使用隊(duì)列進(jìn)行 BFS 的迭代實(shí)現(xiàn)，而 DFS 則需要堆棧。圖領(lǐng)域中一個(gè)最流行的問題，同時(shí)也可能是你閱讀本文的原因之一是尋找圖節(jié)點(diǎn)之間的最短路徑。這需要我們進(jìn)行最后一個(gè)實(shí)驗(yàn)。
示例：Uber
Uber 有 5000 萬用戶、700 萬司機(jī)，對于 Uber 來說，最重要的事情之一就是高效匹配司機(jī)和乘客。該問題首先是定位的問題。后端要處理數(shù)百萬份用戶請求，將每份請求發(fā)送至一或多（通常是多）位附近的司機(jī)。盡管將用戶請求發(fā)送至所有附近司機(jī)更加簡單，有時(shí)也更加智能，但是預(yù)處理通常會(huì)有所幫助。
除了處理請求、基于用戶坐標(biāo)確定定位、尋找最近坐標(biāo)的司機(jī)以外，我們還需要尋找最適合這趟行程的司機(jī)。為了避免地理空間請求處理（對比司機(jī)當(dāng)前坐標(biāo)和用戶坐標(biāo)，來獲取附近車輛），我們假設(shè)已經(jīng)分割了用戶和多輛附近車輛的地圖，如下圖所示：
黃色路線是車輛到用戶處的可能路徑。問題在于計(jì)算車輛到達(dá)用戶的最小距離，即尋找最短路徑。盡管這更多地涉及谷歌地圖而不是 Uber，我們?nèi)匀粐L試解決這一特定和簡化案例，其原因主要在于通常存在多輛車，Uber 可能需要計(jì)算離用戶最近的車。就這張插圖而言，這意味著計(jì)算全部三輛車的最短路徑并確定哪輛車最適合該行程。為了使問題簡潔，我們將討論只有一輛車的情況。下圖顯示了一些到達(dá)用戶的可能路徑。
車輛到達(dá)用戶的可能路徑
我們將該地圖分割表示為一個(gè)圖：
這是一個(gè)無定向的加權(quán)圖（更具體地說是，邊加權(quán)）。為了找到從 B（車）到 A（用戶）的最短途徑，我們應(yīng)該找到他們之間的一條邊權(quán)重最小的路。你可以自由的設(shè)計(jì)你自己版本的解決方案，我們還是使用 Dijkstra 的版本。下面的步驟是從維基百科上找到的 Dijkstra 的算法的步驟。
讓我們把起始的節(jié)點(diǎn)叫做初始節(jié)點(diǎn)。節(jié)點(diǎn)距離 Y 表示初始節(jié)點(diǎn)到 Y 的距離。Dijkstra 的算法將分配一些初始距離值，并嘗試一步步地改善它們。
1. 標(biāo)記所有未訪問節(jié)點(diǎn)。創(chuàng)建所有未訪問節(jié)點(diǎn)的集合「unvisited set」。
2. 為每個(gè)節(jié)點(diǎn)分配一個(gè)實(shí)驗(yàn)距離值：初始節(jié)點(diǎn)的距離值設(shè)置為 0，其他節(jié)點(diǎn)設(shè)置為無窮大。將初始節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)。
3. 對于當(dāng)前節(jié)點(diǎn)，考慮其所有未訪問近鄰，通過當(dāng)前節(jié)點(diǎn)計(jì)算它們的實(shí)驗(yàn)距離。對比新計(jì)算的實(shí)驗(yàn)距離和當(dāng)前分配的值，分配較小的值。例如，如果當(dāng)前節(jié)點(diǎn) A 的距離是 6，連接 A 與近鄰 B 的邊長度為 2，則經(jīng)過 A 到 B 的距離是 6 + 2 = 8。如果 B 之前標(biāo)記的距離大于 8，則將其更改為 8。反之，保留當(dāng)前值。
4. 當(dāng)我們考慮完當(dāng)前節(jié)點(diǎn)的所有近鄰之后，將當(dāng)前節(jié)點(diǎn)標(biāo)記為已訪問，并從 unvisited set 中移除。已訪問節(jié)點(diǎn)無需再檢查。
5. 如果目標(biāo)節(jié)點(diǎn)已經(jīng)標(biāo)記為已訪問（當(dāng)規(guī)劃兩個(gè)特定節(jié)點(diǎn)之間路線的時(shí)候），或 unvisited set 中節(jié)點(diǎn)之間的最小實(shí)驗(yàn)距離是無窮大（當(dāng)規(guī)劃完整遍歷時(shí)，初始節(jié)點(diǎn)和其余未訪問節(jié)點(diǎn)之間沒有連接時(shí)），則停止，算法結(jié)束。
6. 反之，選擇標(biāo)記有最小實(shí)驗(yàn)距離的未訪問節(jié)點(diǎn)，將其設(shè)置為新的「當(dāng)前節(jié)點(diǎn)」，并返回第 3 步。
在我們的示例中，我們首先將節(jié)點(diǎn) B（車輛）設(shè)置為初始節(jié)點(diǎn)。前兩步：
我們的 unvisited set 包含了所有的節(jié)點(diǎn)，同時(shí)也要注意圖左邊里顯示的表格。所有的節(jié)點(diǎn)都包括了到 B 和到之前節(jié)點(diǎn)的最短距離。例如，從 B 到 F 的最短距離是 20，之前節(jié)點(diǎn)是 B。
我們把 B 標(biāo)注為訪問過的然后移動(dòng)到它的近鄰 F。
現(xiàn)在，我們把 F 標(biāo)注已訪問過的，然后在最小實(shí)驗(yàn)距離下選下一個(gè)沒被訪問過的節(jié)點(diǎn)，就是 G。
就像算法里說的，如果目標(biāo)節(jié)點(diǎn)已經(jīng)被標(biāo)注為訪問過的（當(dāng)規(guī)劃兩個(gè)特定的節(jié)點(diǎn)間的路線時(shí)）那么我們可以停止。所以我們下一步用下面的值去停止算法。
所以我們已經(jīng)有了從 B 到 A 并且經(jīng)過 F 與 G 的兩條最短距離。
這真的是 Uber 里最簡單的問題的例子，和冰山類比相比較，我們在冰山的山尖上。然而，這對于我們探索圖論應(yīng)用的真實(shí)場景是個(gè)好的開始。我沒有完成我一開始計(jì)劃的文章，但在不久的將來這個(gè)文章最有可能繼續(xù)下去（也包括數(shù)據(jù)庫內(nèi)部索引）。
關(guān)于圖論有很多內(nèi)容需要去學(xué)習(xí)，這篇文章只是冰山一角，非常感謝各位讀者有耐心能閱讀完 ~
原文地址：https://medium.freecodecamp.org/i-dont-understand-graph-theory-1c96572a1401
