大數(shù)據(jù)文摘作品
編譯：張禮俊、王一丁、xixi、修竹、Apricock、驚蟄、Chloe、龍牧雪
長文預警！本文作者Vardan Grigoryan是一名后端程序員，但他認為圖論（應用數(shù)學的一個分支）的思維應該成為程序員必備。
本文從七橋問題引入，將會講到圖論在Airbnb房屋查詢、推特推送更新時間、Netflix和亞馬遜影片/商品個性化推薦、Uber尋找最短路線中的應用，附有大量手把手代碼和手繪插圖，值得收藏。
圖論的傻瓜式教程
圖論是計算機科學中最重要、最有趣，同時也是最容易被誤解的領域之一。理解并使用圖論有助于我們成為更好的程序員。圖論思維應該成為我們的思維方式之一。
先看一下枯燥的定義……圖是一組節(jié)點V和邊E的集合，包括有序?qū) =（V，E）……??
在試圖研究理論并實現(xiàn)一些算法的同時，我發(fā)現(xiàn)自己經(jīng)常因為這些理論和算法太過艱深而被卡住......
事實上，理解某些東西的最好方法就是應用它。我們將展示圖論的各種應用，及其詳細的解釋。
對于經(jīng)驗豐富的程序員來說，下面的描述可能看起來過于詳細，但相信我，作為一個過來人，詳細的解釋總是優(yōu)于簡潔的定義的。
所以，如果你一直在尋找一個“圖論的傻瓜式教程”，你看這篇文章就夠了。
免責聲明
免責聲明1：我不是計算機科學/算法/數(shù)據(jù)結(jié)構(gòu)（特別是圖論方面）的專家。 我沒有參與本文談及的公司的任何項目。本文問題的解決辦法并非完美，也有改進的空間。 如果你發(fā)現(xiàn)任何問題或不合理的地方，歡迎你發(fā)表評論。 如果你在上述某家公司工作或參與相應的軟件項目，請?zhí)峁嶋H解決方案。請大家耐心閱讀，這是一篇很長的文章。
免責聲明2：這篇文章在信息表述的風格上與其它文章有所不同，看起來可能圖片也與其所在部分的主題不是十分契合，不過耐心的話，相信最終會發(fā)現(xiàn)自己對圖片有完整的理解。
免責聲明3：本文主要是將初級程序員作為受眾而編寫的。在考慮目標受眾的同時，但更專業(yè)的人員也將通過閱讀本文有所發(fā)現(xiàn)。
哥尼斯堡的七橋問題
讓我們從經(jīng)常在圖論書中看到的“圖論的起源”開始——哥尼斯堡七橋問題。
故事發(fā)生在東普魯士的首都哥尼斯堡（今俄羅斯加里寧格勒），普萊格爾河（Pregolya）橫貫其中。十八世紀在這條河上建有七座橋，將河中間的兩個島和河岸聯(lián)結(jié)起來。
現(xiàn)在這個地區(qū)變成這樣啦
問題是如何才能不重復，不遺漏地一次走完七座橋，最后回到出發(fā)點。他們當時沒有互聯(lián)網(wǎng)，所以就得找些問題來思考消磨時間。以下是18世紀哥尼斯堡七座橋梁的示意圖。
你可以嘗試一下，用每座橋只通過一次的方式來走遍整個城市?！懊孔鶚颉币馕吨粦撚袥]有通過的橋?！爸挥幸淮巍币馕吨坏枚啻瓮ㄟ^每座橋。如果你對這個問題很熟悉，你會知道無論怎么努力嘗試這都是不可能的；再努力最終你還是會放棄。
Leonhard Euler（萊昂哈德·歐拉）
有時，暫時放棄是合理的。歐拉就是這樣應對這個問題的。雖然放棄了正面解決問題，但是他選擇了去證明“每座橋恰好走過并只走過一遍是不可能的”。讓我們假裝“像歐拉一樣思考”，先來看看“不可能”。
圖中有四塊區(qū)域——兩個島嶼和兩個河岸，還有七座橋梁。先來看看連接島嶼或河岸的橋梁數(shù)量中的模式（我們會使用“陸地”來泛指島嶼和河岸）。
每塊區(qū)域連接橋梁的數(shù)量
只有奇數(shù)個的橋梁連接到每塊陸地。這就麻煩了。
兩座橋與陸地的例子
在上面的插圖中很容易看到，如果你通過一座橋進入一片陸地，那你可以通過走第二座橋離開這片陸地。
每當出現(xiàn)第三座橋時，一旦穿過橋梁進入，那就沒法走上每座橋且只走一次離開了。如果你試圖將這種推理推廣到一塊陸地上，你可以證明，如果橋梁數(shù)量是偶數(shù)的話，總有辦法離開這塊陸地，但如果橋梁數(shù)量是奇數(shù)，就不能每橋走且只走一次的離開。試著記住這個結(jié)論。
如果添加一個新的橋梁呢？通過下面這張圖，我們可以觀察各個陸地所連接的橋的數(shù)量變化及其影響。
注意新出現(xiàn)的橋
現(xiàn)在我們有兩個偶數(shù)和兩個奇數(shù)。讓我們畫一條包括了新橋梁的路線。
Wow
橋梁的數(shù)量是偶數(shù)還是奇數(shù)至關重要。現(xiàn)在的問題是：我們知道了橋梁數(shù)量是否就能夠斷定問題可不可解？為了解決問題橋的數(shù)量必須是偶數(shù)嗎？歐拉找到了一種方法證明這個問題。而且，更有趣的是，具有奇數(shù)個橋梁連接的陸地數(shù)量也很重要。
歐拉開始將陸地和橋梁“轉(zhuǎn)換”成我們所知道的圖。以下是代表哥尼斯堡七橋的圖的樣子（請注意，我們“暫時”增加的橋并不在圖中）：
需要特別注意的一點是對問題的概括和抽象。無論何時你解決一個具體的問題，最重要的是歸納類似問題的解決方案。在這個例子中，歐拉的任務是歸納橋梁問題，以便能在未來推廣到類似問題上，比如說世界上所有的橋梁問題?？梢暬€有助于以不同視角來看問題。下面的每張圖都表示前面描述的橋梁問題：
所以說圖形化可以很好地描繪問題，但我們需要的是如何使用圖來解決哥尼斯堡問題。觀察從圓圈中出來的線的數(shù)量。從專業(yè)角度而言，我們將稱之為“節(jié)點”（V），以及連接它們的“邊”（E）。V代表節(jié)點（vertex），E代表邊（edge）。
下一個重要的概念就是所謂的節(jié)點自由度，即入射（連接）到節(jié)點的邊的數(shù)量。在上面的例子中，與陸地連結(jié)的橋的數(shù)目可以視為圖的節(jié)點自由度。
歐拉證明了，一次并僅有一次穿過每條邊（橋）來遍歷圖（陸地）嚴格依賴于節(jié)點（陸地）自由度。由這些邊組成的路徑叫做歐拉路徑。歐拉路徑的長度是邊的數(shù)量。
有限無向圖G（V，E）的歐拉路徑是一條使G的每條邊出現(xiàn)并且只出現(xiàn)一次的路徑。如果G有一條歐拉路徑，那么就可以稱之為歐拉圖。
定理：一個有限無向連通圖是一個歐拉圖，當且僅當只有兩個節(jié)點有奇數(shù)自由度或者所有節(jié)點都有偶數(shù)自由度。在后一種情況下，曲線圖的每條歐拉路徑都是一條閉環(huán)，前者則不是。
左圖正好有兩個節(jié)點具有奇數(shù)自由度，右圖則是所有節(jié)點都是奇數(shù)自由度
首先，讓我們澄清上述定義和定理中的新術(shù)語。
有限圖是具有有限數(shù)量的邊和節(jié)點的圖。
圖可以是有向圖也可以是無向圖，這是圖的有趣特性之一。舉個非常流行的關于有向圖和無向圖的例子，F(xiàn)acebook vs. Twitter。Facebook的友誼關系可以很容易地表示為無向圖，因為如果Alice是Bob的朋友，那么Bob也必須是Alice的朋友。 沒有方向，都是彼此的朋友。
還要注意標記為“Patrick”的節(jié)點，它有點特別，因為沒有任何連接的邊。但“Patrick”點仍然是圖的一部分，但在這種情況下，我們會說這個圖是不連通的，它是非連通圖（與“John”，“Ashot”和“Beth”相同，因為它們與圖的其他部分分開）。在連通圖中沒有不可達的節(jié)點，每對節(jié)點之間必須有一條路徑。
與Facebook的例子相對，如果Alice在Twitter上關注Bob，那不需要Bob回粉Alice。所以一個“關注”關系必須有一個方向來指示是誰關注誰，圖表示中就是哪個節(jié)點（用戶）有一個有向邊（關注）到另一個節(jié)點。
現(xiàn)在，知道什么是有限連通無向圖后，讓我們回到歐拉圖：
為什么我們首先討論了哥尼斯堡橋問題和歐拉圖呢？通過思考實際問題和上述解決方案，我們觸及了圖理論的基本概念（節(jié)點，邊，有向，無向），避免了只有枯燥的理論。然而我們還未完全解決歐拉圖和上述問題。我們現(xiàn)在應該轉(zhuǎn)向圖的計算機表示，因為這對我們程序員來說是最重要的。通過在計算機程序中表示圖，我們能設計一個標記圖路徑的算法，從而確定它是否是歐拉路徑。
圖表示法：介紹
這是一項非常乏味的任務，要有耐心。記得數(shù)組和鏈表之間的競爭嗎？如果你需要對元素進行快速訪問，請使用數(shù)組；如果你需要對元素進行快速插入/刪除等修改，請使用列表。
我不相信你會在“如何表示列表”的問題上有困惑。但是就圖的表示而言，實際上卻有很多麻煩，因為首先需要你決定的是用什么來表示一個圖。相信我，你不會喜歡這個過程的。鄰接表，鄰接矩陣，還是邊表？拋個硬幣來決定？
決定了用什么表示圖了嗎？我們將從一棵樹開始。你應該至少看過一次二叉樹（以下不是二叉搜索樹）。
僅僅因為它由頂點和邊組成，它就是一個圖。你也許還記得最常見的一棵二叉樹（至少在教科書中）的樣子。
對于已經(jīng)熟悉“樹”的人來說，這段文字可能看起來太過細致了，但我還是要詳細解釋以確保我們的理解一致（請注意，我們?nèi)栽谑褂脗未a）。
BinTreeNode
root->left = new BinTreeNode
root->right = new BinTreeNode
BinTreeNode
yellow_2->left = new BinTreeNode
yellow_2->right = new BinTreeNode
如果你不熟悉樹，請仔細閱讀上面的偽代碼，然后按照此插圖中的步驟操作：
雖然二叉樹是一個簡單的節(jié)點“集合”，每個節(jié)點都有左右子節(jié)點，但二叉搜索樹卻由于應用了一個允許快速鍵查找的簡單規(guī)則顯得更加有用。
二叉搜索樹（BST）對各節(jié)點排序。你可以自由地使用任何你想要的規(guī)則來實現(xiàn)你的二叉樹（盡管可能根據(jù)規(guī)則改變它的名字，例如最小堆或最大堆），BST一般滿足二分搜索屬性（這也是二叉搜索樹名字的來源），即“每個節(jié)點的值必須大于其左側(cè)子樹中的任何值，并且小于其右側(cè)子樹中的任何值”。
關于“大于”的闡述有個非常有趣的評論。這對于BST的性質(zhì)也至關重要。當將“大于”更改為“大于或等于”，插入新節(jié)點后，BST可以保留重復的值，否則只將保留一個具有相同值的節(jié)點。你可以在網(wǎng)上找到關于二叉搜索樹非常好的文章，我們不會提供二叉搜索樹的完整實現(xiàn)，但為了保持一致性，我們還是會舉例說明一個簡單的二叉搜索樹。
Airbnb房屋查詢實例：二叉搜索樹
樹是一種非常實用的數(shù)據(jù)結(jié)構(gòu)，你可能在項目開始的時候沒有打算應用樹這種結(jié)構(gòu)，但是不經(jīng)意間就用到了。讓我們來看一個構(gòu)想的但非常有價值的例子，關于為什么要首先使用二叉搜索樹。
二叉搜索樹中這個名字中包括了“搜索”，所以基本上所有需要快速查找的東西都應該放進二叉搜索樹中。應該不代表必須，在編程中最重要的事情就是要牢記用合適的工具解決問題。在許多案例中用復雜度為O(N)的簡單鏈表查找比復雜度為O(logN)的二叉搜索樹查找更好。
通常我們會使用一個庫實現(xiàn)BST，最常用的是C++里面的std::set或是std::map，然而在這個教程中，我們完全可以重新造輪子，重寫一個BST庫（BST幾乎可以通過任何通用的編程語言庫實現(xiàn)，你可以找到你喜歡的語言的相應文檔）。
下面是我們將要解決的問題：
Airbnb房屋搜索截圖
如何用一些過濾器盡可能快地根據(jù)一些查詢語句搜索住房是一個困難的問題；當我們考慮到Airbnb儲存了上百萬的房源信息后這個問題會變得更困難。
所以當用戶搜索住房時，他們有機會接觸到數(shù)據(jù)庫中大概四百萬個房源記錄。當然，網(wǎng)站主頁上只能顯示有限個排名靠前的住房列表，并且用戶幾乎不會好奇地去瀏覽住房列表里百萬量級的住房信息。我沒有任何關于Airbnb的分析，但是我們可以用一個在編程中叫做“假設”的強大工具，所以我們假設一個用戶最多瀏覽一千套房源。
這里最重要的因素是實時用戶數(shù)量，因為這會導致數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫選擇的不同和項目結(jié)構(gòu)的不同。可以很明顯的看出，如果只有100個用戶，我們一點不必擔心，但如果一個國家的實時用戶數(shù)量遠超過百萬量級的闕值，我們必須要十分明智地做每一個決定。
是的，“每一個”決定都需要明智的決策。這就是為什么公司在服務方面力求卓越而雇傭最好的員工。Google, Facebook, Airbnb, Netflix, Amazon, Twitter還有許多其他的公司，他們需要處理大量的數(shù)據(jù)，做出正確的選擇以通過每秒數(shù)以百萬的數(shù)據(jù)來服務數(shù)以百萬的實時用戶，這一切從招聘好的工程師開始。這就是為什么我們程序員在面試中要與數(shù)據(jù)結(jié)構(gòu)、算法和解決問題的邏輯作斗爭，因為他們所需要工程師需要具有以最快最有效的方式解決大規(guī)模問題的能力。
現(xiàn)在案例是，一個用戶訪問Airbnb主頁并且希望找到最合適的房源。我們?nèi)绾谓鉀Q這個問題？（注意這是一個后端問題，所以我們不需關心前端或者網(wǎng)絡阻塞或者多個http鏈接一個http或者Amazon EC2鏈接主集群等等）。
首先，我們已經(jīng)熟悉了一種強大的編程工具（是假設而不是抽象），讓我們從假設我們所處理的數(shù)據(jù)都能放在內(nèi)存中。你也可以假設我們的內(nèi)存已經(jīng)足夠大。多大的內(nèi)存是足夠的呢？這是另外一個好問題。儲存真實的數(shù)據(jù)需要多大的內(nèi)存，如果我們正在處理四百萬單位個數(shù)據(jù)（假設），而且我們或許知道每個單位的大小，那么我們就可以輕易的算出需要的內(nèi)存大小，例如，4M＊一個單位的大小。讓我們來考慮一個“home”對象和他的特征，
事實上，讓我們考慮至少一個在解決問題時需要處理的特征（一個“home”就是一個單位）。我們把它表示為C++語言結(jié)構(gòu)的偽代碼，你可以很輕松的將它轉(zhuǎn)換成MongoDB架構(gòu)或者其它你想要的形式，我們只是討論特征名字和類型（想象為節(jié)約空間所使用的二元位域或位集）。
// 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;
vectorstring> 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;
};
假設，上面的結(jié)構(gòu)顯然不是完美的，還有許多假設和未完成的部分（免責聲明里我也說了）。我只是觀察Airbnb的過濾器和設計屬性列表來滿足查找需求。這只是一個例子?，F(xiàn)在我們要計算每個AirbnbHome對象需要占用多少內(nèi)存。
名字只是一個支持多種語言標題的wstring，這意味著每個字符會占用2字節(jié)（如果我們用其它語言可能不需要考慮字符大小，但是在C++中，char占用1字節(jié)，wchar占用2字節(jié)）。
對于Airbnb住房列表的快速瀏覽讓我們假設住房的名字最多包含100個字符（大多數(shù)都在50個字符左右，而不是100），所以我們將假設最大值為100，這就意味著占用不超過200字節(jié)的內(nèi)存。uint是4字節(jié)，uchar為1字節(jié)，ushort為2字節(jié)（這些都是假設）。
假設圖片用第三方存儲服務儲存，比如Amazon S3（目前為止，我知道這個假設對于Airbnb來說很可能是真實的，但是這只是一個假設），另外我們有這些照片的鏈接，考慮到鏈接沒有標準的大小限制，但通常都不會超過2083個字符，所以我們用這個當作鏈接的最大大小。因為每個房源平均會有5張照片，所以圖片最多占用10KB內(nèi)存。
讓我們重新考慮，通常存儲服務提供的鏈接有一部分是固定的。
例如http(s)://s3.amazonaws.com/
那么每張圖片的鏈接就會是這樣： https://s3.amazonaws.com/some-know-bucket/
這讓我們節(jié)省了空間，儲存五張圖片的ID只需要100字節(jié)的內(nèi)存。同樣的小技巧也可以應用在房東的ID上面，例如房東的ID需要20字節(jié)的內(nèi)存（事實上我們對用戶只用了整數(shù)ID，但是考慮到一些數(shù)據(jù)庫系統(tǒng)有自己專用的ID生成器，如MongoDB，我們假設20字節(jié)長度的ID只是一個中位數(shù)，使它可以幾乎滿足所有數(shù)據(jù)庫系統(tǒng)的變化。Mongo產(chǎn)生的ID大小為24字節(jié)）。
最后，我們用4個字節(jié)表示長度為32的位集，對于長度大于32小于64的位集用8個字節(jié)表示。注意這里的假設，我們在這個例子中用位集表示任意一個數(shù)值特征，但是它也可以取多個值，用另一種方法來說，就是一種多項選擇的復選框。
例如，每個Airbnb房源都有一個關于可用設施的列表，比如熨斗、洗衣機、電視、wifi、衣架、煙霧報警、甚至筆記本辦公區(qū)域等?；蛟S房子里有超過20種設施，但我們依然把這個數(shù)目固定為20，因為這個數(shù)目是Airbnb過濾頁面中可選擇的設備數(shù)量。
如果我們用合理的順序排列設備的名字，位集可以幫助我們節(jié)省一些空間。比如說，如果一個房子里有上述提到的設備（在截圖中打勾的設備），我們可以在位集里對應的位置填充一個1。
位集能夠用20個比特存儲20個不同值
例如，檢查房間里是否有“洗衣機”：
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::vectorint>& amenities)
{
bool has = (h != nullptr);
for (const auto a : amenities) {
has &= h->amenities[a];
}
return has;
}
你可以盡可能地改善代碼（并且改正編寫的錯誤），我們只是想強調(diào)在這個問題背景下使用位集的思想。
同樣也適用于“房屋守則”、“住房類型”等。正如上面代碼的注釋中提到的，我們不會儲存經(jīng)緯度以避免地理位置上的查詢，我們會儲存國家代碼和城市名字來縮小地址的查找范圍（刪除掉街道只是為了簡化）。
國家代碼可以用2或3個字符或3個數(shù)字表示，我們會用數(shù)字化的表示并且用ushort表示每個國家代碼。
城市往往比國家多，所以我們不能用“城市代碼”（盡管我們可以生成一些作為內(nèi)部使用），我們直接使用真實的城市名稱，為每個名字平均預留50字節(jié)的內(nèi)存，對于特殊的城市名比如Taumatawhakatangihangakoauauotamateaturipukakapikimaungahoronukupokaiwhenuakitanatahu (85 個字母），我們最好用另外的布爾變量來表示這個是一個特殊的非常長的城市名字（不要試圖讀出這個名字）。
所以，記住字符串和向量的內(nèi)存消耗，我們將添加額外的32字節(jié)確保最后結(jié)構(gòu)的大小不會超出。我們還會假設我們在64位的系統(tǒng)上工作，盡管我們?yōu)閕nt和short選擇了最合適的值。
// Note the comments
struct AirbnbHome
{
wstring name; // 200 bytes
uint price; // 4 bytes
uchar rating; // 1 byte
uint rating_count; // 4 bytes
vectorstring> 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é)，總共452字節(jié)的容量，考慮到有時候你或許會受困于一些校準因素，所以讓我們把容量調(diào)到500字節(jié)。那么每條房屋信息占用500字節(jié)內(nèi)存，對于包含所有房屋信息的列表（有時候我們會混淆列表數(shù)量和真實房屋數(shù)量，如果我犯錯了請告訴我），占用內(nèi)存約500字節(jié)＊4百萬＝1.86GB，近似2GB，這個結(jié)果看起來很合理。
我們在創(chuàng)建結(jié)構(gòu)的時候做了許多假設，努力節(jié)約內(nèi)存來縮小成本，我估計會最后地結(jié)果會超過2GB，如果我在計算中出錯，請告訴我。接下來，無論我們要怎么處理這些數(shù)據(jù)，我們都需要至少2GB的內(nèi)存。請克服你無聊的感覺，我們才剛要開始。
現(xiàn)在是這項任務中最難的部分。針對這個問題選擇正確的數(shù)據(jù)結(jié)構(gòu)（最高效的列表過濾方法）不是最難的部分。（對我來說）最難的是用大量的過濾器查找這些列表。
如果只有一個查找關鍵詞（只有一個過濾器）那么問題會更容易解決。假設用戶只對價格感興趣，那么我們需要做的就只是選擇在這個價格范圍內(nèi)的Airbnb房源。下面是我們用二叉搜索樹完成這項任務的例子。
想象全部四百萬的房屋對象，這棵樹會變得十分巨大。當然，內(nèi)存也會增長很多，因為我們用BST儲存這些數(shù)據(jù)時，每個樹上的節(jié)點都有另外兩個指針指向它的左子節(jié)點和右子節(jié)點，這樣每個子節(jié)點指針都會占用另外8字節(jié)（假設是64位的系統(tǒng)）。
對于四百萬個節(jié)點來說，這些指針總共又會占用62MB，盡管這跟2GB原有的數(shù)據(jù)大小相比不算什么，但是我們也不能輕易忽視它們。
上個例子中樹的所有節(jié)點都可以用O(logN)復雜度的算法找到。如果你不熟悉算法復雜度，不能侃侃而談，我接下來會解釋清楚，或者你可以直接跳過復雜度這部分。
算法復雜度
大多數(shù)情況下，計算一個算法的大O復雜度是比較容易的。提醒一下，我們總是只關心最壞的情況，也就是算法獲得正確結(jié)果（解決問題）所需要的最大操作次數(shù)。
假設有一個包含100個元素的無序數(shù)組，需要比較多少次我們才能找到任意指定元素（同時也考慮指定元素缺失的情況）？
我們需要將每個元素值和我們要找的值相比較，即使這個要找的元素有可能在數(shù)組的第一位（只需要一次比較），但是我們只考慮最壞的情況（要么元素缺失，要么是在數(shù)組的最后一位），所以答案是100次。
“計算”算法復雜度其實就是在操作數(shù)和輸入大小之間找到一個依賴關系，上面那個例子中數(shù)組有100個元素，操作數(shù)也是100次，如果數(shù)組元素個數(shù)（輸入）增加到1423個，找到任意指定元素的操作數(shù)也增加到1423次（最壞的情況下）。
所以在這個例子中，輸入大小和操作數(shù)的關系是很明顯的線性關系：數(shù)組輸入增加多少，操作數(shù)就增加多少。
復雜度的關鍵所在就是找到這個隨輸入數(shù)增加操作數(shù)怎么變化的規(guī)律，我們說在無序數(shù)組中查找某一元素需要的時間為O(N)，旨在強調(diào)查找它的過程會占用N次操作（或者說占用N次操作*某個常數(shù)值，比如3N）。
另一方面，在數(shù)組中訪問某個元素只需要常數(shù)時間，即O(1)。這是因為數(shù)組結(jié)構(gòu)是一個連續(xù)數(shù)據(jù)結(jié)構(gòu)，持有相同類型的元素（別介意 JS數(shù)組），所以“跳轉(zhuǎn)”到特定元素只需要計算其到數(shù)組第一個元素間的相對位置。
我們非常清楚二叉搜索樹將其節(jié)點按序排列。那么在二叉搜索樹中查找一個元素的算法復雜度是多少呢？
此時我們應該計算找到指定元素（在最壞情況下）所需要的操作數(shù)?？床鍒D，從根部開始搜索，第一次比較行為將導致三種結(jié)果，（1）發(fā)現(xiàn)節(jié)點，（2）若指定元素值小于節(jié)點值，則繼續(xù)與節(jié)點左子樹比較，或（3）指定元素值大于節(jié)點值，則與右子樹比較。
在每一步中我們都可以把所需考慮的節(jié)點減少一半。在BST中查找元素所需要的操作數(shù)（也就是比較次數(shù)）與樹的高度一致。
樹高是最長路徑上的節(jié)點數(shù)。在這個例子中樹高為4。如圖所示，高度計算公式為：以2為底logN+1。所以搜索的復雜度為O(logN+1) = O(logN)。所以最壞情況下，在400萬個節(jié)點中搜索需要log4000000=~22次比較。
再說回樹。二叉搜索樹中元素訪問時間為O(logN)。為什么不用哈希表呢？哈希表具有常數(shù)訪問時間，因此幾乎任何地方都可以用哈希表。
在這個問題中我們必須要考慮一個很重要的條件，那就是我們必須能夠進行范圍搜索，例如搜索從房價80美元到162美元的區(qū)間內(nèi)的房子。
在BST中只需要對樹進行一次中序遍歷并保留一個計數(shù)器就可以很容易可以得到一個范圍內(nèi)的所有節(jié)點。而相同任務對于哈希表有點費時了，所以對于特定的例子來說選擇BST還是很合理的。
不過還有另外一個地方讓我們重新考慮使用哈希表。
那就是價格分布。價格不可能一直上漲，大部分房子處在相同的價格區(qū)間?？瓷厦孢@個截圖，直方圖向我們展示了價格的真實情況，數(shù)以百萬計的房價在同一個區(qū)間（18美元到212美元），他們平均價格是相同的。
簡單的數(shù)組也許能起到很好的作用。假設一個數(shù)組的索引是價格，房子列表按照價格排序，我們可以在常量時間內(nèi)獲得任意價格區(qū)間（額，幾乎是常數(shù)）。下面是它的樣子（抽象來講）：
就像哈希表，我們可以按照價格訪問每一組房屋。價格相同的所有房屋都歸在同一個單獨的BST下。而且如果我們存儲的是房屋的ID而不是上面定義的整個對象（AirbnbHome結(jié)構(gòu)），會節(jié)省下一些空間。最有可能的情況是，將所有房屋的完整對象保存在一個哈希表中，房屋ID映射房屋對象，同時建立另一個哈希表（或者一個數(shù)組），用房屋ID映射價格。
當用戶請求一個價格區(qū)間時，我們從價格表中獲取房屋ID，將結(jié)果分割成固定大?。ㄒ簿褪欠猪?，通常一個頁面上顯示10-30個條目），通過房屋ID獲取完整房屋信息。記住這些方法。
同時，要記住平衡。平衡對BST來講至關重要，因為這是在O(logN)內(nèi)完成操作的唯一保證。不平衡BST的問題很明顯，當你在排序中插入元素時，樹最終會變成一個鏈表，這顯然會導致具有線性時間性質(zhì)的操作次數(shù)。
不過從現(xiàn)在開始可以忘記這些，假設我們所有的樹都是完全平衡的。再看一眼上面的插圖，每個數(shù)組元素代表一顆樹。那如果我們把插圖改成這樣：
這更像一個“真實”的圖了。這個插圖描繪了了最會偽裝成其他數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)——圖。
圖表示法：進階
關于圖有一個壞消息，那就是對于圖表示法并沒有一個固定的定義。這就是為什么你在庫里找不到std::graph的原因。不過BST其實可以代表一個“特殊”的圖。關鍵是要記住，樹是圖，但圖并不僅僅是樹。
上個插圖表示在單個抽象條件下可以有許多樹，圖中包含“價格vs房屋”和具有“不同”類型的節(jié)點，價格是只具有價格數(shù)值的圖節(jié)點，并指向滿足指定價格的所有住房ID（住房節(jié)點）的樹。它很像一個混合的數(shù)據(jù)結(jié)構(gòu)，而不是我們在課本例子中常常見到的簡單的一個圖。
這就是圖表示法的關鍵，它并沒有固定的和“合法的”結(jié)構(gòu)用于圖表示（不像BST有指定的基于節(jié)點的表示法，有左/右子指針，盡管你也可以用一個數(shù)組來表示一個BST）。
只要你“認為”它是一個圖，你可以用你覺得最方便的方式（對特定問題最便捷）表達它?！罢J為是一個圖”所表達的就是應用特定于圖的算法。
其實N叉樹更像一個圖。
首先想到來表示N叉樹節(jié)點的偽代碼是這樣的：
struct NTreeNode
{
T value;
vector
};
這個結(jié)構(gòu)只表示這個樹的一個節(jié)點，整棵樹應該是這樣的：
// almost pseudocode
class NTree
{
public:
void Insert(const T&);
void Remove(const T&);
// lines of omitted code
private:
NTreeNode* root_;
};
這個類模擬一個名為root_樹節(jié)點。我們可以用它構(gòu)建任意大小的樹。這是樹的起始點。為了增加一個新的樹節(jié)點我們需要分配給它一個內(nèi)存并將該節(jié)點添加到樹的根節(jié)點上。
圖與N叉樹雖然很像，但稍微有點不同。試著畫出來一下。
這個是圖嗎？說不是也是。它跟之前的N叉樹是一樣的，只是旋轉(zhuǎn)了一下。根據(jù)經(jīng)驗來講，不管何時你看到一棵樹，也不管這是一顆蘋果樹，檸檬樹還是二叉搜索樹，你都可以確定他也是一個圖。所以為圖節(jié)點（圖頂點）設計一個結(jié)構(gòu)，我們可以得出相同的結(jié)構(gòu)：
struct GraphNode
{
T value;
vector
};
這足以構(gòu)成一個圖嗎？當然不能?？纯粗暗膬蓚€圖有什么不同。
都是圖
左邊插圖中的圖中的樹沒有一個“輸入”點（更像是一個森林而不是單獨的樹），相反的是右側(cè)插圖中的圖沒有不可到達的頂點。聽起來很熟悉哈。
定義：如果每對節(jié)點間都有一條路徑，那么我們認為這個圖是連通的。
很明顯，在“價格vs房屋”圖中并不是每對節(jié)點間都有路徑（如果從插圖中看不出來，就假設價格節(jié)點并沒有彼此相連吧）。盡管這只是一個例子來解釋我們不能構(gòu)造一個具有單個GraphNode struct的圖，但有些情況下我們必須處理像這樣的非連通圖?？纯催@個類：
class ConnectedGraph
{
public:
// API
private:
GraphNode* root_;
就像N叉樹是圍繞一個節(jié)點（根節(jié)點）構(gòu)建的，一個連通圖也是圍繞一個根節(jié)點構(gòu)造的。樹是“有根”的，也就是說存在一個起始點。連通圖可以表示成一個有根樹（和幾個屬性），這已經(jīng)很明顯了，但是要記住即使對于一個連通圖，實際表示會因算法不同而異，因問題不同而異。然而考慮到圖的基于節(jié)點的性質(zhì)，非連通圖可以表示為：
class DisconnectedGraphOrJustAGraph
{
public:
// API
private:
std::vector
};
對于像DFS/BFS這樣的圖遍歷，很自然就使用樹狀表示了。這種表示方法幫助很大。然而，像有效路徑跟蹤這樣的例子就需要不同的表示了。還記得歐拉圖嗎？
為了找到一個圖具有“歐拉性”，我們應該在其中找到一個歐拉路徑。這意味著通過遍歷每條邊一次去訪問所有的節(jié)點，并且如果遍歷結(jié)束還有未走過的邊，那就說明這個圖沒有歐拉路徑，因此也就不是歐拉圖。
還有一個更快些的方法，我們可以檢查所有節(jié)點的自由度（假設每個節(jié)點都存有它的自由度），然后根據(jù)定義，如果圖有個數(shù)不等于兩個的奇自由度節(jié)點，那這個圖就不是歐拉圖。
這個檢查行為的復雜度是O(|V|)，|V|是圖中節(jié)點的個數(shù)。當插入新的邊來增加奇/偶自由度時我們可以進行追蹤，這個行為復雜度為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::vectorstd::string> Trace(const std::string& v) {
std::vectorstd::string> 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_mapstd::string, Edge*> vertices_;
std::vector
};
注意這些無處不在的bug。上面的代碼包含大量的假設，比如打標簽，因此我們知道頂點有一個字符串類型的標簽。你可以隨意將它換成任何你想要的東西，不必太在意這個例子里的內(nèi)容。然后還有命名，代碼注釋中寫道，VELOGraph是Vertex Edge Label Only Graph的縮寫（我起的名字）。
重點是，這個圖表示法包含一個表，用來將節(jié)點標簽和節(jié)點連接的邊映射到該頂點，還包含一個邊的列表，該列表含有節(jié)點對（由特定邊連接）和僅由Trace()函數(shù)使用的標記(flag)。
回顧Trace()函數(shù)實現(xiàn)過程，邊的標記(flag)用來表示已經(jīng)遍歷過的邊（在任何Trace()被調(diào)用后都需要重置標記）。
推特時間線實例：多線程推送
鄰接矩陣是另一種非常有用的有向圖的表示方法，推特的關注情況圖即是一個有向圖。
有向圖
這個推特的示例圖中，共有8個節(jié)點。因此我們只需將這個圖表示為|V|×|V|的方陣（|V|行|V|列，|V|為節(jié)點數(shù)）。如果節(jié)點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，也可以儲存“更有用”的東西，比如邊的權(quán)重。表示地點之間距離的圖就是一個再恰當不過的例子。
上圖表示出了Patrick, Sponge Bob和其他人住址之間的距離（這也被稱作加權(quán)圖）。如果兩個頂點之間沒有直接路徑，矩陣對應元素就置無窮符號“∞”。
這一階段的無窮符號并不意味著二者之間一定不存在路徑，也不意味著一定存在。元素的值可能在用算法找出頂點之間路徑長度以后重新定義（若要更好地儲存頂點和與之相連的邊的信息，可利用關聯(lián)矩陣）。
雖然鄰接矩陣看起來很適合用于表示推特的關注情況圖，但存儲將近3億用戶（月活躍用戶數(shù)）的布爾值需要300 * 300 * 1 字節(jié)，這是大約82000Tb（百萬兆字節(jié)），也就是1024 * 82000Gb。
不知道你的磁盤有多少簇，但我的筆記本可沒有這么大的內(nèi)存。如果用位集呢？位棋盤有一點用，可以讓所需存儲空間縮減到10000Tb左右，但這還是太大了。前面提到過，鄰接矩陣過于稀疏，因此想要儲存全部有效信息，需要很多額外空間，因此表示與頂點相連的邊的鄰接表是更佳選擇。
所謂更佳，是因為鄰接矩陣既儲存了“已關注”信息，也儲存了“未關注”信息，而我們只需要知道關注情況，如下所示：
鄰接矩陣 vs 鄰接表
右側(cè)的插圖表示一個鄰接表。每個表體現(xiàn)了圖中一個頂點所有相鄰頂點的集合。要指出的是，一個圖可以用不同的鄰接表來表示（荒謬但事實如此）。插圖中標黃處使用了哈希表，這是一種相當明智的方法，因為哈希表查詢頂點的時間復雜度是O(1)。
我們沒有提到鄰接頂點列表應該用哪一種特定的數(shù)據(jù)結(jié)構(gòu)存儲，鏈表、向量等都行，任你選擇。關鍵在于，要想知道Patrick有沒有關注Liz，我們需要訪問哈希表（需要常數(shù)時間），遍歷這個鏈表中的所有元素，并與“Liz”元素進行比較（需要線性時間）。
這種情況下，線性時間并不太壞，因為我們只需循環(huán)與“Patrick”相鄰的頂點，而這些頂點的個數(shù)是一定的。那考慮到空間復雜度，這種表示方法是否還適用于推特的例子呢？我們需要至少3億個哈希表來記錄，每個都指向一個向量（我選擇向量來避免列表左/右指針的內(nèi)存消耗），每個向量里包含了...多少元素呢？
沒有相關數(shù)據(jù)，只找到了推特關注數(shù)的平均值，707。假設每個哈希表指向707個用戶id（每個占8字節(jié)），并假設哈希表每個表頭只含有關鍵字（仍然是用戶id），則每個哈希表占據(jù)3億 * 8字節(jié)，哈希表關鍵字占據(jù)707 * 8字節(jié)，總共就是3億 * 8 * 707 * 8字節(jié)，大約為12Tb。這個結(jié)果不算令人滿意，但和一萬多Tb相比已經(jīng)好很多了。
說實在的，我不知道這個結(jié)果是否合理，但考慮到我在32Gb的專用服務器上花費約為30美元，那么分片儲存12Tb需要至少385個這樣的服務和400多臺控制服務器（用于數(shù)據(jù)分發(fā)控制），因此每月需要大約1.2萬美元?？紤]到數(shù)據(jù)有副本，而且總會有些問題出現(xiàn)，我們將服務器的數(shù)量擴大到三倍，再增加一些控制服務器。
假設至少需要1500臺服務器，則每月需要大約4.5萬美元。我當然覺得這不可行，畢竟租用一臺服務器于我都有些吃力，但對于Twitter則似乎算不上事（與真正的Twitter服務器相比，確實不算事）。
這樣計算夠了嗎？并不是，我們只考慮了關注情況的數(shù)據(jù)。推特最重要的是什么？我是指，從技術(shù)上來說，最大的問題是什么？是能夠快速將某人的一條推文推送給其關注者。而且不僅是快速，更像是閃電一樣的光速。
假設Patrick發(fā)了一條關于食物想法的推文，他的所有關注者都應在一個合理的時間內(nèi)收到這條推文。多長時間合理呢？我們當然可以隨意假設，但我們感興趣的是真實的系統(tǒng)。下圖說明了有人發(fā)送推文的后續(xù)過程。
我們不知道一條推特需要多久才能推送給所有關注者，但公開的統(tǒng)計數(shù)據(jù)顯示，每天有5億條推文，因此上圖的過程每天要重復5億次。關于傳達速度我找不到有用的數(shù)據(jù)，但可以模糊地回憶出，大約5秒之內(nèi)，所有關注者都可以接收到推文。
而且還要考慮處理量很大的情況，比如有著上百萬關注量的名人。他們可能只是在海濱別墅里用推文分享了美妙的早餐，推特卻要辛辛苦苦把這“相當有用”的信息推送給以百萬計的關注者。
為了解決推文推送的問題，我們不需要關注情況的圖，而需要關注者的圖。關注情況圖（用一個哈希表和一些列表表示）可以很方便的找出被某一個用戶所關注的所有用戶，但卻不能找到某一個用戶的所有關注者，要想達到這個目標需要遍歷哈希表所有的關鍵字。
因此我們應當構(gòu)造另一個圖，這個圖在某種程度上對稱相反于前者。這個新的圖應該也由3億個頂點組成，每個頂點指向鄰接頂點的列表（數(shù)據(jù)結(jié)構(gòu)不變），不過這個列表代表關注者。
在上圖所示的情況下，每當Liz發(fā)送推文，Sponge Bob和Ann都會在他們的時間線上看到更新。實現(xiàn)這一點有一個常用技術(shù)，即為每位用戶的時間線保留一個單獨的結(jié)構(gòu)。在推特這個有3億用戶的例子里，我們大概假設需要至少3億個時間線（每位用戶一個）。
總的來說，當一個用戶發(fā)送推文，我們應當獲取該用戶的關注者列表，并更新這些關注者的時間線（將內(nèi)容相同的推文插入它們的時間線）。時間線可以用列表或是平衡樹表示（以推文發(fā)送時間的數(shù)據(jù)作為節(jié)點）。
// '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
// 2. insert tweet into each timeline
for (auto follower : user_followers) {
InsertTweetIntoUserTimeline(follower->id, tw->id);
}
}
這段代碼只是我們從時間線真實的形式中提取出的思想，用多線程的方法可以加快推送的速度。
這種方法對于處理量很大的情況至關重要，因為對于上百萬關注者來說，相較于處在關注者列表前端的用戶，處于尾端的用戶總是較晚看到新推文。下面一段偽代碼嘗試說明了多線程推送的想法：
// Warning: a bunch of pseudocode ahead
void RangeInsertIntoTimelines(vectorlong> 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
vectorlong> 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);
}
}
如此一來，無論關注者何時刷新時間線，總能接收到新推文。
公道地說，我們不過才觸及Airbnb或推特所面臨問題的冰山一角。天才工程師們要耗費大量時間，才能構(gòu)造出推特、谷歌、臉書、亞馬遜、airbnb等了不起的復雜系統(tǒng)。閱讀本文時別忘了這一點。
推特的例子的重點在于圖的使用，盡管沒有用到圖算法，而只涉及到圖的表示。我們的確用偽代碼寫了一個推送推文的函數(shù)，但這只是尋找解決方案過程的產(chǎn)物，我指的“圖算法”是這個列表中的算法。
令程序員心力交瘁的圖論和圖算法應用，某種意義上來說是有些許差異的。前面我們討論了不用圖表示時，高效篩選Airbnb房源的問題。此時，一處明顯的缺陷在于，若有兩個或以上的篩選關鍵詞，則無法高效篩選?？梢詧D算法可以解決這個問題嗎？這我不敢保證，不過可以試一試。
把每個篩選條件當作獨立的頂點會有什么結(jié)果呢？字面地理解“每個篩選條件”，10美元到1000美元以上的價格、所有城市的名稱、國家代碼、生活設施（電視、Wi-Fi等等）、成人房客數(shù)等等，每個信息都作為一個獨立的頂點。
將“類型”頂點加入圖能使這些頂點更“好用”，比如將所有代表生活設施篩選條件的頂點連接到“生活設施”頂點。
如果我們將Airbnb房源表示為頂點，并將它們連接到各自符合的篩選條件所對應的頂點上，會是什么情況呢（例如，若“房源1”有“廚房”這項設施，則將其連接至“廚房”）？
稍微處理一下這個示意圖，能使之更像一種特殊的圖：二分圖。
頂點數(shù)量比圖上顯示的更多
二分圖（亦稱偶圖）是一種特殊的圖，其頂點可分為兩個不相交且獨立的集合，從而每條邊的兩個頂點分別在兩個集合中。在我們的例子中，一個集合代表篩選條件（以F表示），另一個代表房源（H）。
例如，有10萬個房源標價為62美元，則有10萬條邊以“62美元”為一個頂點，每條邊的另一頂點為滿足該條件的房源。考慮空間復雜度最壞的情況，即每個房源滿足所有的篩選條件，邊總數(shù)應為7萬 * 400萬。
如果每條邊用｛篩選條件；房源｝來表示，并用4字節(jié)的整型變量表示篩選條件、8字節(jié)的長整型變量表示房源，則每條邊占據(jù)12字節(jié)。存儲7萬 * 400萬個12字節(jié)的值大約需要3Tb的內(nèi)存。
不過我們的計算中有一個小錯誤，由Airbnb的統(tǒng)計數(shù)據(jù)得知，7萬個左右的篩選條件中約有6.5萬個是房源所在城市。值得慶幸的是，一個房源不能位于兩個或以上的城市。
這意味著與城市相連的邊的總數(shù)實際應為400萬（每個房源只位于一座城市），因此只用計算70000－65000＝5000個篩選條件，故而只需5千 * 400萬 * 12字節(jié)的內(nèi)存，總計小于0.3Tb。
這個結(jié)果還不錯。不過是什么構(gòu)造出了這樣的二分圖呢？一般而言，網(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é)點的函數(shù)，就叫做“我的節(jié)點打印算法”。大多數(shù)人覺得很難的是那些寫在教科書上的算法?；羝湛寺宸蛱兀ㄆ账惴ǎ℉opcroft-Karp）就是個二分圖匹配算法的例子。下面我們就來試著用這個算法來過濾Airbnb房源吧。
給定一個Airbnb房屋（H）和過濾器（F）的二分圖，其中H的每個元素（頂點）都可以有多個相鄰的F元素（頂點）相連。 請查找一個和F子集內(nèi)頂點相鄰的H頂點子集。
這個問題的描述已經(jīng)很繞了，而我們現(xiàn)在甚至還不能確定Hopcroft-Karp算法是否能解決這個的問題。不過我向你保證，解決問題的這個過程會讓我們學到很多在圖算法背后的基本原理。不過，這個過程并不那么短，所以請大家耐心。
Hopcroft-Karp算法是種以一個二分圖作為輸入，并產(chǎn)生一個最大基數(shù)匹配（maximum cardinality matching）的算法。 最大基數(shù)匹配得出的結(jié)果是一組由盡可能多的邊組成的集合，而集合中所有的邊都不會共享節(jié)點。
熟悉這種算法的讀者可能已經(jīng)意識到，這并不能解決我們的Airbnb問題，因為匹配要求所有的邊都不會共享節(jié)點。
我們來看一個例子。為了簡單起見，我們假設一共只有4個過濾器和8個房源。房源由A到H的字母表示，過濾器是隨機選擇的。假設四個過濾器分別為：每晚50美元，有一張床，提供Wifi，提供電視。
已知家庭A價格為50美元，有1張床。從A到H的所有房屋每晚價格都為50美元，床位為1張，但其中很少有提供WiFi或者電視的。下面這張插圖詳細說明了系統(tǒng)應返回哪一個房源，滿足了顧客需求，即一間同時符合所有四種過濾器的住房。
這個問題的解決方案（見上圖中左下角連線）要求能通過這些共享頂點的邊找到那些可以通過所有四種過濾器的房屋(即D和G)，而Hopcroft-Karp算法去掉了具有共同節(jié)點的邊，最后得到的是入射到兩個子集頂點的邊（見上圖中右下角的紅線）。
就像上圖中所展示的，在所有的選擇中我們只需要同時滿足所有條件的D和G就可以。我們真正需要找的，是共享節(jié)點的所有的邊。
我們可以給這樣的方法設計一種算法，但處理時間對于要求立刻回復的用戶來說并不理想。相比之下，建立一個節(jié)點帶有多個排序鍵值(key)的平衡二叉搜索樹(balanced binary search tree)可能會更快。這有點像數(shù)據(jù)庫的索引文件，直接把主鍵(primary keys)或者外鍵(foreign keys)映射到一組所需要的數(shù)據(jù)記錄。
Hopcroft-Karp算法（以及其他許多算法）都是同時基于DFS（深度優(yōu)先搜索）和BFS（廣度優(yōu)先搜索）圖遍歷算法。
實際上，在這里介紹Hopcroft-Karp算法的實際原因是可以從二叉樹這樣性質(zhì)優(yōu)良的圖循序漸進地轉(zhuǎn)入更難的圖遍歷問題。
二叉樹遍歷非常優(yōu)美，主要是因為它們的遞歸性質(zhì)。 二叉樹有三種基本遍歷，分別是先序，后序和中序遍歷（你當然可以自己編寫遍歷算法）。
如果你曾經(jīng)遍歷過鏈表，那么遍歷很容易理解。 在鏈表中只需打印當前節(jié)點的值（下面代碼中的命名項）并在下一個節(jié)點繼續(xù)這個操作即可。
// 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é)點的值（或其他任何需要使用的值），然后繼續(xù)到下一個節(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' node
void 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; // stop
InOrderTraverse(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;
顯然，遞歸函數(shù)看起來非常優(yōu)雅，雖然它們的運行時間一般都很長。 每次遞歸調(diào)用函數(shù)時，這意味著我們需要調(diào)用一個完全新的的函數(shù)（參見上圖）。
“新”的意思是，我們應該給函數(shù)參數(shù)和局部變量分配另一個堆棧存儲空間。 這就是為什么遞歸調(diào)用在資源上顯得很昂貴（額外的堆?？臻g分配和多個函數(shù)調(diào)用）而且比較危險（需要注意堆棧溢出）。
因此相比之下更建議通過迭代法來實現(xiàn)同樣的功能。 在關鍵任務系統(tǒng)編程（比如飛行器或者NASA探測器）中，遞歸是完全禁止的（這個只是傳言，并沒有實際數(shù)據(jù)或者經(jīng)驗證明這一點）。
Netflix和亞馬遜個性化推薦實例：倒排索引
假設我們要將所有Netflix影片存儲在二叉搜索樹中，并將影片的標題作為排序鍵。
在這種情況下，無論何時用戶輸入開頭為“Inter”的內(nèi)容，程序都會返回一系列以“Inter”開頭的電影列表，例如[Interstellar星際穿越，Interceptor截擊戰(zhàn)，Interrogation of Walter White絕命毒師]。
如果這個程序可以找出標題中包含“Inter”的所有電影（包括并沒有以“Inter”開頭，但是標題中包含這個關鍵字的電影），并且該列表將按電影的評分或與該特定用戶相關的內(nèi)容進行排序就更好了（例如，某用戶更喜歡驚險片而不是戲?。?。
這個例子的重點在于對二叉搜索樹進行有效的范圍查詢。但和之前一樣，在這里我們不會繼研究冰山還沒露出的部分。
基本上，我們需要通過搜索關鍵字進行快速查找，然后獲得按關鍵字排序的結(jié)果列表。其實這很可能就是電影評分或基于用戶個性化數(shù)據(jù)的內(nèi)部排名。 當然，我們會盡可能堅持KISK原則（Keep It Simple，Karl）。
“KISK”或““l(fā)et’s keep it simple”或“for the sake of simplicity”，這簡直就是教程編寫者從真實問題中找一些抽象化的簡單的例子，并以偽代碼形式來講解的超級借口。這些事例的解決方案簡單到往往在祖父母一輩的電腦上都能運行。
這個問題也可以很容易應用到亞馬遜的商品搜索中，因為用戶通常通過在亞馬遜上輸入他們感興趣的內(nèi)容（如“圖算法”）來查找相關產(chǎn)品，并得到以商品評分排序的清單。
Netflix里有不少影片，亞馬遜里有很多商品，在這里我們把影片和商品叫做“物品”，所以每當你查找“物品”時，可以聯(lián)想Netflix中的電影或亞馬遜的任何合適的產(chǎn)品。
關于這些物品，最常見的就是用程序去解析標題和描述（在此我們只考慮標題）。所以如果一個操作員（比如一位通過管理板將物品數(shù)據(jù)插入Netflix / Amazon數(shù)據(jù)庫的員工）把新項目插入到數(shù)據(jù)庫里，物品的標題就被一些被叫做“ItemTitleProcessor”的程序處理，從而產(chǎn)生一系列關鍵字。
每個物品都有一個唯一的ID，這個ID和物品標題中的關鍵字有直接關聯(lián)。這是搜索引擎在爬全球各種各樣的網(wǎng)站時所做的事。他們分析每個文檔的內(nèi)容，對其進行標記（將其分解為更小的詞組和單詞）并添加到列表中。
這個表將每個標記（單詞）映射到已被標記成 ”包含這個標記” 的文檔或網(wǎng)站的ID上。
因此，無論何時搜索“hello”，搜索引擎都會獲取映射到關鍵字“hello”的所有文檔?，F(xiàn)實中這個過程非常復雜，因為最重要的是搜索的相關性，這就是為什么Google很好用。Netflix /亞馬遜也會用類似的表。同樣的，讀者們請在看到物品（item）時想想電影或網(wǎng)購的商品。
倒排索引
又來了，哈希表。是的，我們將為這個倒排索引（索引結(jié)構(gòu)存儲了一個和內(nèi)容相關的映射）保留一個哈希表。哈希表會將關鍵字映射到構(gòu)成二叉搜索樹的許多物品當中。
為什么選擇二叉搜索樹呢？ 這是因為我們希望可以保持物品的排序，并同時對按順序排好的部分進行處理（響應網(wǎng)頁前端的請求），例如請求分頁時的100個項目。
這并不能說明二叉搜索樹的強大功能，但假設我們還需要在搜索結(jié)果中進行快速查找，例如，你想要查找關鍵字為“機器”(machine)的所有三星電影。
這里需要注意的是，在不同的樹中同一個物品重復出現(xià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ù)庫時，它的標題都會被處理，并添加到總索引表里，該表會創(chuàng)建一個從關鍵字到對應物品的映射。
可能有很多物品共享相同的關鍵字，因此我們將這些項目保存在按照評分排序的二叉搜索樹中。當用戶搜索某個關鍵字時，他們會得到按評分排序的物品列表。我們?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
{
// assuming IndexTable is a big hashtable mapping keywords to Item BSTs
BST
// suppose BST has a function InOrderProduceVector(), which creates a vector and
// inserts into it items fetched via in-order traversing the tree
vector
return sorted_result;
}
下面這段代碼實現(xiàn)中序遍歷：
template typename BlaBla>
class BST
{
public:
// other code ...
vector
{
vector
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
{
if (!node) return;
InOrderProduceVectorHelper_(node->left, destination);
destination.push_back(node->item);
InOrderProduceVectorHelper_(node->right, destination);
}
private:
BSTNode* root_;
};
但是！首先我們首先需要評分最高的項目，而中序遍歷首先輸出的是評分最低的項目。這個結(jié)果和中序遍歷的性質(zhì)有關，畢竟從低到高的中序遍歷是自下而上的。
為了得到理想的結(jié)果，即列表按降序而不是升序排列，我們應該仔細研究一下中序遍歷的實現(xiàn)原理。 我們所做的是通過左節(jié)點，然后打印當前節(jié)點的值，最后是右節(jié)點。
正因為我們一直從左開始，所以最先的得到的是“最靠左”的節(jié)點，也就是最左節(jié)點，這是在整個二叉樹里具有最小值的節(jié)點。因此，簡單地將遍歷方法改成右節(jié)點優(yōu)先，就可以得到降序排列的列表。
和其他人一樣，我們可以給這種方法命名，比如“reverse in-order traversal”，反序遍歷?，F(xiàn)在我們來更新一下之前寫的代碼（這里引入單個列表，注意，前方bug出沒）：
// Reminder: this is pseudocode, no bother with 'const&', 'std::' or others
// forgive me C++ fellows
template typename BlaBla>
class BST
{
public:
// other code ...
vector
{
vector
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
{
if (!node) return;
if (limit == 0) return;
--offset; // skipping current element
ReverseInOrderProduceVectorHelper_(node->right, destination, offset, limit);
if (offset <=>0) { // if skipped enough, insert
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
{
// assuming IndexTable is a big hashtable mapping keywords to Item BSTs
BST
// 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
return sorted_result;
}
就是這樣，我們可以快速提供物品的搜索結(jié)果。 如上所述，倒排索引主要用于Google之類的搜索引擎。
盡管Google是個特別復雜的搜索引擎，但它確實使用了一些簡單的想法（雖然用非常現(xiàn)代化的方法實現(xiàn)），以將搜索查詢與物品文檔進行匹配，并盡可能快地提供搜索結(jié)果。
這里，我們用了樹的遍歷來按照某種排序來處理搜索結(jié)果。在這一點上，先序、中序和后序遍歷看起來可能綽綽有余，但有時還需要另一種類型的遍歷。大家可以試著解決這個眾所周知的編程面試題“如何逐層打印一個二叉樹？”:
深度優(yōu)先搜索DFS和廣度優(yōu)先搜索BFS
如果你對這個問題不熟悉，請想一下遍歷樹時用來存儲節(jié)點的數(shù)據(jù)結(jié)構(gòu)。如果我們拿逐層樹遍歷和先序遍歷、中序遍歷、后序遍歷比較，最后會得到兩種主要的圖遍歷方法，深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）。
深度優(yōu)先搜索尋找最遠的節(jié)點，廣度優(yōu)先搜索先探索最近的節(jié)點。
深度優(yōu)先搜索：做的多，想的少。
廣度優(yōu)先搜索：先四處觀望再進行下一步動作。
DFS很像先序遍歷、中序遍歷、后序遍歷，而BFS可以逐層遍歷節(jié)點。為實現(xiàn)BFS，需要一個隊列（數(shù)據(jù)結(jié)構(gòu)）來保存圖的“層次”，同時打?。ㄔL問）其“父母層”。
上圖中，放入隊列的節(jié)點為淺藍色?；旧现饘舆M行，每層節(jié)點都從隊列中獲取，訪問每個獲取的節(jié)點時，將其子節(jié)點插入到隊列中（用于下一層）。下面的代碼非常簡單，很好地說明了BFS的思路。假設圖是連通圖，可以修改以適用于非連通圖。
// Assuming graph is connected
// and a graph node is defined by this structure
// struct GraphNode {
// T item;
// vector
// }
// WARNING: untested code
void BreadthFirstSearch(GraphNode* node) // start node
{
if (!node) return;
queue
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 < cur-="">item;
}
}
這一思路對基于節(jié)點的連通圖表示非常簡單。請記住，對于不同表示，圖遍歷的實現(xiàn)也不相同。BFS和DFS是解決圖搜索問題的重要方法（但記住圖搜索算法有很多很多）。
雖然DFS是優(yōu)美的遞歸實現(xiàn)，但迭代實現(xiàn)也可行的。而BFS的迭代實現(xiàn)我們會用一個隊列，對DFS需要一個堆棧。圖論中的一個熱門問題，是找節(jié)點間最短路徑。來看最后一個例子。
Uber最短路線實例
Uber有5000萬乘客和700萬司機，所以高效地將司機與乘客進行匹配非常重要。司機使用Uber司機專用應用來接單，乘客就用Uber應用叫車。
首先是定位。后臺需要處理數(shù)百萬條乘客請求，并發(fā)送給附近的司機，通常會發(fā)送給多個司機。雖然將乘客請求發(fā)送給附近所有司機看起來更簡單，甚至有時候也更有效，但是進行一些預處理往往效果更好。
除了處理收到的請求，根據(jù)乘客坐標查找定位區(qū)域，進而查找坐標最近的司機外，還需要為乘客找到合適的司機。假設已經(jīng)有了包含乘客及幾個附近車輛的小地圖，（已經(jīng)對比了車輛當前坐標和乘客坐標，并確定了附近車輛，這一過程稱為地理信息處理），小地圖如下：
車輛到乘客的可能路線用黃色標出。那么現(xiàn)在的問題是計算從車輛到乘客需要的最小距離，也就是說，要找到最短路線。雖然這個問題更像Google地圖而不是Uber應該考慮的，但我們還是要解決這個簡化的問題，因為通常乘客附近有多輛車，Uber需要計算距離最近且評分最高車輛發(fā)送給乘客。
對于上圖而言，要分別計算三輛車抵達乘客的最短路線，再決定哪輛車是最佳選擇。為簡化問題，這里討論只有一輛車的情況。以下標出三條抵達乘客的路線。
抵達乘客的可能路線
接下來進入重點，先將小地圖抽象成圖：
這是無向加權(quán)圖（確切地說是邊加權(quán)圖）。為了找到頂點B（汽車）和A（乘客）之間的最短路徑，應該找包含盡可能小的權(quán)重的邊的路徑。我們用Dijkstra版本；你也可以自行設計你的方案。以下是Dijkstra算法的維基百科。
將開始的節(jié)點稱為起始節(jié)點。Y節(jié)點的路徑長度定義為從出發(fā)點到Y(jié)點的總路徑長度。Dijkstra算法將會分配一些初始距離值然后逐步改善它們。
1.將所有節(jié)點設為未訪問。設置一個包含所有未被訪問節(jié)點的集合，稱為未訪問集合。
2. 對所有頂點的路徑長度賦暫定值：將起始節(jié)點的路徑長度設為0，所有其他頂點的路徑長度設為無窮大。將起始節(jié)點設為當前節(jié)點。
3.對于當前節(jié)點，考慮其周圍所有未訪問的相鄰節(jié)點，并且計算通過當前節(jié)點到它們的暫定距離。將新計算得到的暫定距離與當前分配的距離進行比較并選擇較小的值然后分配。例如，如果當前節(jié)點A的距離為6，連之相鄰B的長度為2，則通過A到B的距離將為6 + 2 = 8。如果B先前被標記的距離大于8，則將其更改為8.否則，則保持當前值。
4.當我們考慮完當前節(jié)點的所有相鄰節(jié)點時，將當前節(jié)點標記為已訪問并將其從未訪問節(jié)點集中移除。被訪問的節(jié)點將不會再次被查看。
5.如果目標節(jié)點已經(jīng)被標記為已訪問（當目標是兩個特定節(jié)點之間的路徑）或者未訪問集合中的節(jié)點之間的最小暫定距離是無窮大時（目標完全遍歷時;發(fā)生在初始節(jié)點和剩余的未訪問節(jié)點之間沒有連接時），將會停止。算法已經(jīng)完成。
6.否則，選擇未訪問過的并且具有最小暫定距離的節(jié)點，把它作為新的“當前節(jié)點”，然后回到步驟3。
應用Dijkstra算法到示例中，頂點B（車）是起始節(jié)點。前兩步如下：
所有的節(jié)點都屬于未訪問集合，需要注意圖示右側(cè)的表格。對于所有節(jié)點，它將包含從B到前一個（標記為“Prev”）節(jié)點的所有最短距離。例如，從B到F的距離是20，前一個節(jié)點是B。
將B標記為已訪問，然后移動到它的相鄰節(jié)點F。
現(xiàn)在將F標記為已訪問，并選擇具有最小暫定距離的點為下一個未訪問節(jié)點，即G。依然需要注意左側(cè)的表格，在前面的圖例中，節(jié)點C，F(xiàn)和G已經(jīng)將它們的暫定距離設置為通過之前所提到的結(jié)點的距離。
如同算法闡述的那樣，如果目標節(jié)點被標記為已訪問（在我們的例子中，當要兩個特定節(jié)點之間的路徑時），那我們可以結(jié)束算法了。因此，下一步終止算法返回下面的值。
所以我們既有從B到A的最短距離又有通過F節(jié)點和G節(jié)點的路徑。
這是Uber中的一個再簡單不過的例子，只是滄海一粟。然而，這是很好的起點，可以幫你邁出探索圖論應用的第一步。
聯(lián)系客服
