從七橋問題開始：全面介紹圖論及其應用

EQDRigobert 6年前發布 | 44K 次閱讀數據庫機器學習 Dijkstra算法

圖論是計算機科學中最重要、最有趣的領域之一，同時也是最容易被誤解的。本長文從圖論最基礎的七橋問題開始，進而結合推特與非死book 實例解釋無向圖與有向圖。此外，本文還是用大量的實例解釋表征圖、搜索樹、哈希表等關鍵概念。最后本文描述了基于深度的搜索和基于廣度的搜索等十分流行的圖算法。

理解和使用圖幫助我們成為更好的程序員。用圖思考幫助我們成為最好的，至少我們應該那么思考。圖是很多節點 V 和邊 E 的集合，即可以表示為有序對 G=(V, E)。

盡管嘗試研究過圖論，也實現了一些算法，但是我還是非常困惑，因為它實在太無聊了。

事實上，理解一件事物的最佳方式是理解其應用。我們將展示圖論的多個應用，最重要的是，有很多插圖。

七橋問題

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

在 18 世紀，這里被稱為柯尼斯堡，隸屬普魯士，這一區域有很多橋。當時，有一個與柯尼斯堡的橋相關的腦筋急轉彎：如何只穿過橋一次而穿過整個城市。下圖為柯尼斯堡七座橋的簡化圖。

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

Leonhard Euler

有時候，放棄這一問題是合理的。這就是 Leonhard Euler 的解決方法，他沒有試圖解決這一問題，而是證明其不可解決。讓我們試著去理解 Euler 的內在想法，做到像 Euler 一樣思考。首先我們從下圖開始。

圖中有四塊彼此分隔的區域，兩個島嶼和兩塊陸地，以及七座橋。探討每一區域的橋數是否有一定模式很有趣。

每塊區域的橋數

如圖所示，每塊區域的橋數皆為奇數。如果你只能穿過橋一次，區域有兩座橋，那么你就可以進入并離開該區域。

有兩座橋的區域的示例

通過圖示很容易發現，如果你通過一座橋進入一個區域，那么你也要通過第二座橋離開它。但是當第三座橋出現，則無法只穿過橋一次而離開。所以對于一塊區域，當橋數為偶時，則可以每座橋只穿過一次而離開；當橋數為奇時，則不能。請牢記。

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

注意添加的新橋

現在我們有兩個偶數和兩個奇數。讓我們在添加新橋的圖上畫一條新路線。

我們已經看到了橋的奇偶數是重要的。這里有個問題：橋的數量解決問題了嗎？難道這個數不應該一直是偶數嗎？后來發現不是的。這就是 Euler 做的，他發現了一個顯示橋數量很重要的辦法。更有意思的事，有奇數個連接點的「陸地」也很重要。這時候 Euler 開始把陸地和橋轉化成我們看得懂的圖。下面是一幅表示了哥尼斯堡七橋（K?nigsberg bridges）的圖（注意：我們「臨時」加的橋不在這里）：

抽象化七橋問題

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

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

下一個重要的事是所謂節點自由度（Degree），即連接到節點的邊數量。在我們上面的例子里，連接陸地和橋的邊的數量可以被表達成節點的自由度。

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

有限無向圖 G(V,E) 的 Euler 路徑是指 G 的每一個邊都只出現一次的路徑。如果 G 有一條 Euler 路徑，它就被稱之 Euler 圖。[注釋 1]
定理：有且僅有兩個確定的節點存在奇數自由度，其它的節點都有偶數自由度，那么該有限無向圖為 Euler 圖。【1】

左圖：有兩個節點有奇數自由度的圖像。右圖：所有節點都有奇數自由度。

首先，讓我們分清楚上面定理和理論中的新名詞。有限圖（Finite graph）是指有限數量的邊和節點的圖。

圖可以為有向的或無向的，這也是圖非常有趣的性質。你肯定看到過將非死book 和推ter 的作為有向圖和無向圖的例子。非死book 朋友關系也許可以很簡單地表示為一個無向圖，因為如果 Alice 是 Bob 的朋友的話，Bob 也必須是 Alice 的朋友。

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

與非死book 的例子相反的是，如果 Alice 在推ter 上關注了 Bob，Bob 并不需要關注 Alice。所以「關注」關系必須是有向的連接，其表示節點（用戶）有一條有向邊（關注）連接到其它的節點（用戶）。

現在，我們了解了什么是有限無向圖，讓我們再一次思考 Euler 圖：

所以為什么我們最開始就討論了哥尼斯堡七橋問題和 Euler 圖呢？在接觸答案之前接觸一下問題背后的因素（節點、邊、有向、無向）也能避免枯燥的理論方法。我們現在應該更關注于用電腦表示圖，因為這是我們最大的興趣。用電腦程序表示圖將使我們設計出一個算法來跟蹤圖路徑（graph path），這樣就能發現它是不是 Euler 路徑了。

圖表征：前言

這是一個很沉悶的任務，要有耐心。記得數組和鏈表之間的戰爭嗎？用如果你需要快速訪問元素就用數組，如果你需要快速插入/刪除元素就用鏈表等。我很難相信你會在像「怎樣表示列表」這樣的問題上糾結。當然，在圖論中真正的表達是非常無聊的，因為首先你應該決定你將怎樣確切地表達圖。

現在我們以一個樹來開始。你肯定已經至少一次見到了二叉樹（下面的不是二叉搜索樹）。

因為它是由節點和邊構成的，所以它就是圖。你也要想到一般最常見的二叉樹是怎樣表示的（至少在教科書上）。

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

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

BinTreeNode<Apple>* root = new BinTreeNode<Apple>("Green");

root->left = new BinTreeNode<Apple>("Yellow");
root->right = new BinTreeNode<Apple>("Yellow 2");

BinTreeNode<Apple>* yellow_2 = root->right;

yellow_2->left = new BinTreeNode<Apple>("Almost red");
yellow_2->right = new BinTreeNode<Apple>("Red");

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

當一個二叉樹是簡單的節點「集合」，每一個父節點有左子節點和右子節點的節點。二叉樹在應用簡單規則的時候是非常有意義的，例如允許快速的關鍵字查找。二叉搜索樹（BST）按序儲存他們的關鍵字。我們可以根據任何規則實現二叉樹（即使它會根據不同的規則而有不同的名字，比如，min—heap 或者 max——heap），最常見的 BST 規則是它符合二項搜索性質（也是名字的由來），即「任意節點的鍵值必須比它左邊子樹的鍵值要大，比右邊子樹上的鍵值要小。「更大」是 BST 重要的本質，當你把它改成「比更大或一樣」時，你的 BST 可以在插入新節點時解決復制鍵值得問題，除此之外它將只保留唯一鍵值的節點。你可以在網上找到很好的二項樹的文章，我們不會提供一個二元搜索樹的全面實現，但我們將展示一個簡單的二元搜索樹。

Airbnb

樹是非常有用的數據結構，你也許還沒有實現過樹型結構，但你也許無意間用過它們。像你注意到的，二叉搜索樹（Binary Search Tree）中有「搜索」，簡單來說，所有需要快速查找的事，應該被放到二叉搜索樹中。「應該」不意味著一定，在編程中最重要的事情是用合適的工具去解決問題。這里有很多案例可以看到簡單鏈表（O(N) 復雜度）搜索相比 BST（O(logN) 復雜度）搜索更受歡迎。一般來說我們可以用一個庫來實現一個 BST，但是在這個教程中我們可以重新發明我們自己的輪子（BST 是基本在所有多用途編程語言庫都有實現）。接近了「一個真實世界例子」，這里是我們試著去處理的問題：

Airbnb 房源搜索一瞥：

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

所以當用戶搜索房源時，他們也許就會「接觸」到四百萬條數據庫中的記錄。的確，在網站主頁上能夠展現的「top listings」有限，而用戶對瀏覽百萬條列表也并不感興趣。我沒有任何 Airbnb 的分析記錄, 但我們可以用編程語言中叫做「假設」的強大工具，所以我們假設單個用戶查看最多 1 千個房源就會發現中意的房源。并且最重要的因子是即時用戶的數量，因為它會影響數據結構、數據庫和項目構架的選擇。就像這看起來的那么明顯，如果這里總共有 100 個用戶，我們就不用去操心。相反，如果即時用戶數量超過了百萬級，我們必須去思考每一個決定到底對不對。每個決策都被正確的使用，這是為什么巨頭們雇傭最好的人才，為提供卓越的服務而努力的原因（Google、非死book、Airbnb、Netflix、Amazon、推ter 和許多其他公司都在處理大量的數據；招聘正確的工程師來做正確的選擇，為數百萬實時用戶每秒處理百萬級字節的數據。這就是為什么我們碼農糾結于可能遇見的數據結構，算法和問題處理，因為需要的是工程師有能力快速、有效地解決這樣大的問題）。

所以在 Airbnb 的案例里，用戶瀏覽了他們的房源主頁，Airbnb 試著去過濾房源來找出最適合的。我們怎樣處理這個問題呢？（注意這個問題是后端的，所以我們不需要管前端或者網絡流量或者 https over http 或者 Amazon EC2 over home cluster 等。首先，因為我們已經熟悉了程序員倉庫中最強大的工具（在說假設而不是抽象），我們假設處理的是完全適配 RAM 的數據。然后你也可以假設我們的 RAM 是足夠大的。足夠大去支持，但這是多大呢？這是另一個非常好的問題。需要多大的內存來存儲真正的數據呢？如果我們處理的是四百萬單元的數據（還是假設），如果我們大概知道每一個單元的大小，之后我們可以簡單地驅動需要的內存，就是 4M*sizeof(one_unit)。考慮下「房源」及其性質（properties），事實上，至少考慮一下處理這一問題必要的性質（一個「房源」是我們的單元）。我們需要用 C++結構偽代碼來表示一些問題，你可以簡單地將他們轉化為一個 MongoDB 略圖目標或者任何你想要的形式, 我們只討論性質的名字和類別。（試著去想象這是在空間經濟里用字位段或者位集合）

// feel free to reorganize this struct to avoid redundant space
// usage because of aligning factor
// Remark 1: some of the properties could be expressed as enums,
// bitset is chosen for as multi-value enum holder.
// Remark 2: for most of the count values the maximum is 16
// Remark 3: price value considered as integer,
// int considered as 4 byte.
// Remark 4: neighborhoods property omitted 
// Remark 5: to avoid spatial queries, we're 
// using only country code and city name, at this point won't consider 
// the actual coordinates (latitude and longitude)
struct AirbnbHome
{
  wstring name; // wide string
  uint price;
  uchar rating;
  uint rating_count;
  vector<string> photos; // list of photo URLs
  string host_id;
  uchar adults_number;
  uchar children_number; // max is 5
  uchar infants_number; // max is 5
  bitset<3> home_type;
  uchar beds_number;
  uchar bedrooms_number;
  uchar bathrooms_number;
  bitset<21> accessibility;
  bool superhost;
  bitset<20> amenities;
  bitset<6> facilities;
  bitset<34> property_types;
  bitset<32> host_languages;
  bitset<3> house_rules;
  ushort country_code;
  string city;
};

假設。上面的結構不是完美的（很顯然），而且這里有很多假設或者不完整的地方，去再讀一下免責聲明。我只是看了下 Airbnb 的過濾器和應該存在的符合搜索查詢的設計性產權表。這只是個例子。現在我們應該能計算每一個 AirbnbHome 對象會在內存中占用多少空間。name 是一個 wstring 來支持多語言的名字/頭銜的，這個意味著每一個字符占了 2 字節（我們不想擔心字符大小如果我們需要用其他的語言，但在 C++中，char 是 1 字節然后 wchar 是 2 字節）。

快速的看一下 Airbnb 的表可以讓我們估計房源的名字可以占到最多 100 個字符（雖然最多的是 50 個左右，而不是 100 個），我們會認為 100 個字符是最多的量，這占了差不多 200 字節的內存。uint 是 4 字節，uchar 是 1 字節,ushort 是 2 字節（還是假設）。假設圖片是在儲存服務旁邊，像 Amazon S3（目前據我所知，這個假設對于 Airbnb 來說是最可能實現的，當然這也是假設）而且我們有這些照片的 URL，而且考慮這里沒有 URL 的標準尺寸的限制，但這事實上有一個眾所周知的上線-2083 字符，我們將要用這個當成任何 URL 的最大尺寸。所以考慮到這個，平均每個房源有 5 張照片，這可以占到 10Kb 內存。

讓我們重新想一下，一般儲存用同樣的基礎 URL 服務，像 http(s)://s3.amazonaws.com/<bucket>/<object>，這樣就是說，這里有一個基本的模式來建 URL 并且我們只需要儲存真實照片的 ID，讓我們說用了一些獨特的 ID 生成器，可以為圖片對象返回 20 字節長度的獨特的字符 ID，看起來像 https://s3.amazonaws.com/some-know-bucket/。這提供了我們好多空間效率，所以為了 5 張照片儲存字符 ID，我們只需要 100 字節內存。

同樣的「手段」可以用 host_id 來做，就是說，房主的用戶 ID，占了 20 字節的內存（實際上我們可以就讓用戶用數字 ID，但考慮到一些 DB 系統像 MongoDB 有非常詳細的 ID 生成器，我們假設 20 字節的字符 ID 是「中位」長度，已經可以用很小的改動就能適用于大部分 DB 系統了。Mongo 的 ID 長度是 24 字節）。最后，我們將用一個最多 4 字節 32 位大小對象的位集合和一個比 32 位大的 64 位小的位集合一起作為一個 8 字節的獨享。注意這是個假設。我們在這個例子里為了所有的表達了枚舉的性質用了位集合，但位集合可以取不止一個值，換種說法這是一種多種選擇的多選框。

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

位集合（Bitset）允許儲存 20 個不同數據而只用 20 個字節。

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

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

或者更專業一點：

const int KITCHEN = 0;
const int HEATING = 1;
const int WASHER = 2;
//...
bool HasWasher(AirbnbHome* h)
{
  return (h != nullptr) && h->amenities[WASHER];
}

bool HasWasherAndKitchen(AirbnbHome* h)
{
  return (h != nullptr) && h->amenities[WASHER] && h->amenities[KITCHEN];
}

bool HasAllAmenities(AirbnbHome* h, const std::vector<int>& amenities)
{
  bool has = (h != nullptr);
  for (const auto a : amenities) {
    has &= h->amenities[a];
  }
  return has;
}

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

最后，對于國家編碼和城市名。像上面代碼注釋中提到的一樣（看標注），我們不會儲存經緯度來避免地理-空間問題，我們儲存國家代碼和城市名字來縮小用地名搜索的范圍（為了簡介省略街名，原諒我）。國家代碼可以被用兩個字符，3 個字符或者 3 個數字來表示，我們會用 ushort 儲存數字表達。不幸的是，城市比國家多了太多，所以我們不能使用「城市編碼」，我們只會儲存真實的城市名，保留平均 0 為 50 字節的城市名字和特別的名字。我們最好用一個附加的布爾變量來表示這是不是一個特別長的名字，所以我們將會加上附加的 32 字節來保證最終的結構大小。我們也假設在 64 位系統上工作，即使我們為 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<string> 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 字節加上 32 個多出的字節，若我們四舍五入到 500 字節。所以每一個對象「home」最多占 500 字節，并且對于所有房源列表，500 字節*4 百萬=1.86Gb ~2Gb。我們在搭建結構時做了很多假設，讓儲存在內存中更便宜。無論我們對這數據做什么，我們需要至少 2Gb 內存。如果你無聊，忍著，我們剛開始。

現在是任務最難的地方了，為這個問題選擇合適的數據結構（來盡可能有效的過濾表）不是最難的任務。最難的是（對我而言）按照一系列濾波器搜索列表。如果只有一個搜索鍵（key）（即只有一個濾波器），我們可以很輕易地解決這個問題。假設用戶只關心價格，我們需要的只是在給定的范圍以價格下降的順序找到 Airbnbhome 對象（合適的家）。如果我們要用二元搜索樹來解決這個問題，則可按下圖形式執行。

如果需要遍歷所有的 4 百萬個對象，這搜索樹會長得很大很大。另外，需要占用的內存也會越來越多。這只是因為我們用了二元搜索數來存儲對象，每一個樹節點給它的左右子樹兩個額外的指針，加起來是每個子指針有 8 個額外的比特（假設是 64 位系統）。對于 400 百萬節點它加起來就是 62Mb，對于 2Gb 對象的數據來說是很小的，但還是不能輕易地「忽略」。

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

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

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

計算算法復雜度的重點是找到運算次數與輸入規模之間的依賴關系，舉例來說，上面的數列有 100 個元素，運算的次數也是 100，如果數列的數量（輸入）增長到 1423，運算次數也會增長到 1423（最差的情況）。所以，輸入和運算次數之間的關系在這里是非常清晰的，它也被叫做線性關系，運算次數和數列的增長一樣快。增長是復雜度的關鍵，我們說在一個未排序的數列中搜索需要 O（N）次運算，來強調尋找它需要最多用 N 次運算，（甚至最多到 N 的常數倍數運算，比如 3N 次）。另一方面，訪問數列上的任意元素只需要常數時間，比如 O（1）。這是因為數列的結構是一個連續結構，并且包含相同類型的元素，所以訪問特定的元素只需要計算它與數列第一個元素的相對位置。

有一點非常明確，二元搜索樹按排序順序保存其節點。那么在二元搜索樹中搜索元素的算法復雜度是多少呢？我們應該在最壞的情況下計算查找元素所需的操作次數。

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

（1）目標節點被發現；

（2）如果要找的值小于節點的值，則匹配將繼續到節點的左子樹；

（3）如果要找的值大于節點的值，則匹配將繼續到節點的右子樹。

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

回到樹搜索的問題，二元搜索樹中的元素搜索時間為 O（logN）。為什么不使用哈希表？哈希表有常數的訪問時間，這使得在幾乎任何地方使用哈希表都是合理的。

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

就像一個哈希表，我們通過房源的價格來匹配每一套房子。所有具有相同價格的房源都歸入單獨的二元搜索樹。如果我們存儲房源的 ID 而不是上面定義的完整對象（AirbnbHome 結構），也可以節省一些空間。最可能的情況是將所有房源的完整對象保存在哈希表，并將房源 ID 映射到房源的完整對象中，以及保存另一個哈希表（或更好的，一個數組），該哈希表將價格與房源 ID 進行映射。因此，當用戶請求價格范圍時，我們從價格表中獲取房源 ID，將結果裁剪成固定大小（即分頁，通常在一頁上顯示 10-30 個項目），然后使用每個房源 ID 獲取完整的房源對象。請記得，要注意平衡。平衡對二元搜索樹至關重要，因為它是在 O（logN）內完成樹操作的唯一保證。當你按排序順序插入元素時，二元搜索樹不平衡的問題就會很明顯，最終，樹將變成連接列表，這顯然會導致線性時間復雜度。現在假設我們所有的搜索樹都是完美平衡的。再看看上面的圖。每個數組元素代表一棵大樹。如果我們改變這個樹，變成圖呢？

這是一個「更接近真實」的圖。這個圖展示了最隱蔽的數據結構和圖，帶領我們到了（下文）。

圖表征：進階

圖論的缺點是缺乏單獨定義，這就是為什么你無法在庫中找到 std::graph。我們已經嘗試過表示「特別的」圖 BST。重點在于，樹是圖，但圖未必是樹。最后一張示例圖表明在一個抽象圖下面有很多樹，「價格 vs 房源」和一些節點的類型不同，價格只有價格值的圖節點，表示滿足特定價格的房源 ID（房源節點）的樹。這很像混合數據結構，不同于我們在教科書示例中見到的簡單圖形。圖表示的重點：不存在固定、「權威」的圖表示結構（這與 BST 不同，后者用左／右子指針代表基于節點的特定表示，盡管你可以用一個數組表示 BST）。你可以用最便捷的方式表示一個圖，重點在于你把它「看作」是圖。「看圖」的意思是使用適用于圖的算法。

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

首先，將 N-ary 樹節點表示為：

struct NTreeNode
{
  T value;
  vector<NTreeNode*> children;
};

該結構僅表示樹的一個節點，完整的樹如下所示：

// almost pseudocode
class NTree
{
public:
  void Insert(const T&);
  void Remove(const T&);
  // lines of omitted code
private:
  NTreeNode* root_;
};

該類別是圍繞單個樹節點 root_ 的抽象。我們可以用它構建任意大小的樹。這是樹的起點。如果要添加新的樹節點，我們就要為其分配內存，將該節點添加至樹的根節點處。

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

這是圖嗎？我認為，是的。但這幅圖與前面的 N-ary 相同，只不過稍微旋轉了一下。只要你看到一棵樹，無論它是蘋果樹、檸檬樹，還是二叉搜索樹，你都可以確定它也是一張圖。因此，通過設計圖節點（圖節點）結構，我們能夠提出同樣的結構：

struct GraphNode
{
  T value;
  vector<GraphNode*> adjacent_nodes;
};

這樣可以創建圖嗎？還不夠。看下面兩幅圖，找不同：

二者都是圖

左側的圖沒有可以「進入」的點（與其說是樹，它更像森林），相反，右側的圖沒有不可達的節點，聽起來很熟悉。

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

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

class ConnectedGraph
{
public:
  // API

private:
  GraphNode* root_;
};

類似圍繞單個節點（根節點）構建的 N-ary 樹，連通圖也可以圍繞根節點構建。樹有「根」，即它們有起始點。連通圖可以用帶有根節點的樹來表示（當然還有其他屬性），不過要注意，實際的表示可能會隨著算法或具體問題發生變化。但是，考慮基于節點的圖本質，非連通圖可以按照下面的方式來表示：

class DisconnectedGraphOrJustAGraph
{
public:
  // API

private:
  std::vector<GraphNode*> all_roots_;
};

樹狀圖可以清晰自然地表示 DFS/BFS 這樣的圖遍歷。但是，高效路徑追蹤等需要不同的表示方法。還記得歐拉圖嗎？為了追蹤圖的「eulerness」（真實性），我們應該追蹤圖中的歐拉路徑。這意味著遍歷每個邊一次就要訪問所有節點；如果追蹤結束后我們仍有未遍歷的邊，則該圖沒有歐拉路徑，因此它不是歐拉圖。更快的方法是：檢查節點的度（假設每條邊都保存了度），如定義所述，如果圖的節點度是奇數，則它不是歐拉圖。該檢查的復雜度是 O(|V|)，其中 |V| 是圖節點的數量。我們可以在插入新的邊緣的同時追蹤節點的奇數／偶數度，同時插入新的邊以增加奇數／偶數度檢查的復雜度到 O(1)。下面介紹圖表示和返回路徑的 Trace() 函數。

// A representation of a graph with both vertex and edge tables
// Vertex table is a hashtable of edges (mapped by label)
// Edge table is a structure with 4 fields
// VELO = Vertex Edge Label Only (e.g. no vertex payloads)

class ConnectedVELOGraph {
public:
    struct Edge {
        Edge(const std::string& f, const std::string& t)
            : 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<std::string> Trace(const std::string& v) {
        std::vector<std::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_map<std::string, Edge*> vertices_;
    std::vector<Edge*> edges_;
};

注意 bug，bug 到處都是。該代碼包含大量假設，比如標簽，我們可以通過節點理解字符串標簽，確保你可以將其更新成任意事物。接下來，是命名。如注釋中所述，VELOGraph 僅適用于 Vertex Edge Label Only Graph。重點在于，該圖表示包括一個將節點標簽映射至節點關聯邊的表、一個包含與邊相連的兩個節點的邊列表，和一個僅用于 Trace() 函數的 flag。查看 Trace() 函數實現，它使用邊的 flag 來標記已經遍歷過的邊（在任意 Trace() 調用之后應該重置 flag）。

示例：推ter

另一種表示叫做相鄰矩陣，它在有向圖中有用，就像我們在推ter 關注圖中所使用的那樣。

有向圖

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

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

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

上圖表示了 Patrick 和 Sponge Bob 等人之間的距離（也稱為加權圖）。如果節點間沒有沒有直接路徑，那么我們就把它設為無窮大，它既不意味著根本沒有路徑，也不意味著一定有路徑。它可以在應用算法搜索兩個節點間路徑時定義。當然，我們還有更好的方法來儲存節點和邊之間的關系，如關聯矩陣。

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

鄰接矩陣與鄰接列表

右圖表示鄰接列表（adjacency list），每個列表描述了圖中的一組鄰近節點。在圖表中，我們突出了哈希表的用法，因為任何節點的訪問復雜度都是 O（1）。而且對于鄰近節點列表，我們并沒有提到任何具體的數據結構，也不會從列表轉化為向量。重點是，如果要確定 Patrick 是否關注 Liz，我們應該遍歷哈希表中每一個元素（常數時間），而鄰近矩陣需要查看每一個與 Liz 相關的元素（線性時間）。線性時間在這一點上并不是那么糟，因為我們經需要循環與 Patrick 相關的固定數目的節點。

如果我們用空間復雜度表示推特，這需要 3 億個哈希表記錄，每個記錄指向一個向量（選擇向量以避免鏈表的左/右指針所產生的內存開銷）。此外，雖然沒有統計數據，但平均推特關注的人數是 707 個。所以如果我們考慮每個哈希表記錄指向一個有 707 個用戶 ID 的數組，且每個 ID 有 8 個字節，那么現在我們可以計算出儲存空間約為 12TB。

現在少很多了，但我們仍然不確定 12TB 是否是一個合理的數字。如果在 32Gb RAM 的專用服務器上一個月需要 30 美元，那么 12TB 加上一些控制服務器和備用服務器等（約需要額外兩倍數量）核算下來需要 1500 臺服務器，每月的成本達到了 45K 美元。這對于我們來說當然是難以接受的價格，但對于推特來說就非常便宜了。但推特需要提高響應的速度，即用戶發的推文需要第一時間發送給關注的人。但理想的時間是多少？我們并不能作出任何假設和抽象，因此我們可以探討一下現實世界產品系統的響應。以下是我們在推文時經常遇到情況。

同樣我們并不知道一條推文需要多少時間才能發送到所有的關注者，但公開的數據表明每天約有 500 億條推文。所以經驗看來一般推文的時間在 5 秒內，同時我們還要注意哪些擁有超百萬粉絲的名人，推特可能會分配更多的資源來推送名人「超級有用」的內容。

為了解決推文的分發問題，我們并不需要以下的圖，我們需要關注者的列表。前面的哈希表和一些列表允許我們高效地搜索特定關注者關注的所有用戶，但它并不允許高效地搜索關注特定用戶所有關注者，因此我們必須掃描所有的哈希表鍵值。這也就是為什么我們應該構建另一個圖，它與以下我們展示的圖對稱相反。這個新的圖由包含 3 億個節點的哈希表組成，每個節點指向相鄰節點的獵鳥（結構相同），但是這次相鄰節點的列表將表示關注者。

因此基于該示例，無論何時 Liz 發推特，Spone Bob 和 Ann 都必須在他們的時間線上找到特定的推文。一項普遍使用的解決該問題的技術是為每個用戶的時間線保持獨立的結構。假設推特有 3 億的用戶，我們可以假定至少存在 3 億個時間線（每人一個）。簡單的說，無論何時發推，我們應該找到他的關注者并且更新他們的時間軸，時間線可以被表征成連結串列或平衡樹（以推文的日期作為節點關鍵字）。

// '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*> user_followers = GetUserFollowers(author->id);  // 2. insert tweet into each timeline  for (auto follower : user_followers) {    InsertTweetIntoUserTimeline(follower->id, tw->id);  } }

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

// Warning: a bunch of pseudocode ahead void RangeInsertIntoTimelines(vector<long> 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<long> 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 或推特面臨問題的冰山一角，還有很多問題需要各位讀者共同探討。

推特的推文分發問題關鍵在于對圖的利用，即使我們不使用任何的圖算法，僅用圖表示。而真正的圖算法是相當復雜的。在使用圖表示之前，我們討論了 Airbnb 房源和高效過濾的問題，主要困難在于當過濾器關鍵字超過一個的時候，就無法高效地過濾家園。那么使用圖算法能帶來什么好處嗎？值得一試。我們可以將每個過濾器表示成一個獨立的節點，每個過濾器可以代表特定的屬性（價格、城市名、國家、生活設施等）。

Airbnb 過濾器節選

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

擁有高級類型的 Airbnb 過濾器

現在，我們可以將 Airbnb 房源（home）表示成節點，然后將這些節點和對應的屬性節點連接起來。

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

節點的數量比看起來的更多

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

如果我們測量空間復雜度的最壞情況，即每個家庭具有滿足所有過濾器的所有屬性，則要存儲的邊總量將為 7 萬×400 萬。如果我們將每個邊表示為一個 ID 對：{filter_id; home_id}，如果我們重新考慮 ID，并使用 4 個字節（int）數字 ID 為過濾器 ID，8 個字節（long）ID 為房源使用的 ID，那么每個邊緣至少需要 12 個字節。因此，存儲 7 萬* 400 萬個 12 字節值需要大約 3TB 的內存。我們在計算中犯了一個小錯誤，由于在 Airbnb 中有 65,000 個活躍城市，因此過濾器的數量約為 7 萬個（統計數據）。

好消息是，同一個家庭不能位于不同的城市。也就是說，我們實際與城市邊配對的數量是 400 萬（每個家庭位于一個城市），因此我們將計算 70k-65k = 5000 個過濾器，這意味著我們需要 5000 * 400 萬* 12 個字節的內存，小于 0.3Tb。聽起來不錯。但是什么給了我們這個偶圖？最常見的網站/移動請求將由多個過濾器組成，例如：

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"]

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

圖算法

或許，任何用圖執行的計算過程都可以分類為「圖算法」，你可以實現一個輸出圖的所由節點的函數，然后將其命名為「<你的名字>的節點輸出算法」。但真正可怕的是教科書中列出的圖算法：

Coloring
Hopcroft–Karp
Hungarian
Prüfer coding
Tarjan's off-line least common ancestors
Topological sort

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

給定一個 Airbnb 房源（H）的偶圖和過濾器（F），其中 H 的每個節點可以多于 F 的一個相鄰節點（共享一個公共邊）。尋找 H 的由節點構成的子集，該子集和 F 的子集的節點相鄰。

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

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

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

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

二值樹遍歷非常漂亮，這大多是因為它們的遞歸本質。有三種基本的遍歷方式稱為中序（in-order）、后序（post-order）和前序（pre-order）。如果你曾經遍歷過連結串列，這些概念是很好懂的。在連結串列中，你只需要輸出當前節點的值（在下方的代碼中稱為 item），并繼續到達下一個節點。

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

這和二值樹幾乎相同，輸出節點的值，然后到達下一個節點，但在這里，「下一個」指的是兩個節點，左節點和右節點。因此你需要分別到達左節點和右節點。不過你有三個不同的選擇：

輸出節點值，然后到達左節點，再到達右節點。
到達左節點，然后輸出節點值，再到達右節點。
到達左節點，然后到達右節點，再輸出節點值。

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

前序遍歷的細節追蹤

很明顯遞歸函數的形式很優雅，雖然其計算成本很高。每次我們遞歸地調用一個函數，也就意味著我們調用了一個完全的新函數（如上圖所示）。其中「新」的意思是函數變量和局域變量需要分配其它的堆棧內存空間。這正是為什么遞歸調用的成本如此高（額外的堆棧空間分配和多函數調用）和危險（堆棧溢出），很明顯地使用迭代實現會更好。在關鍵任務（航空、NASA 探測車等）的系統編程中，遞歸調用是完全禁止的。

實例：Netflix

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

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

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

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

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

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

倒排索引

哈希表，再提一次。是的，我們將為此倒排索引（索引結構存儲來自內容的映射）保留哈希表。哈希表會將關鍵字映射到物品的 BST。為什么選擇 BST？因為我們希望保持它們的排序并同時提供連續排序的部分（響應前端請求），例如一次請求（分頁）中的 100 個物品。這并不能說明 BST 的強大功能，但假設我們還需要在搜索結果中進行快速查找，例如，你需要關鍵字為「機器」的所有 3 星電影。

請注意，可以在不同的樹中復制物品，因為通常可以使用多個關鍵字找到物品。我們將使用如下面定義的物品進行操作：

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

每次將新物品插入數據庫時，其標題都將被處理并添加到大型索引表中，該表將關鍵字映射到物品。可能有許多物品共享相同的關鍵字，因此我們將這些物品保存在按照評分排序的 BST 中。當用戶搜索某個關鍵字時，他們會得到按其評分排序的物品列表。我們如何從排序的樹中獲取列表？通過按順序遍歷。

// 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<Item*> GetItemsByKeywordInSortedOrder(string keyword)
{
  // assuming IndexTable is a big hashtable mapping keywords to Item BSTs
  BST<Item*> 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<Item*> sorted_result = items.InOrderProduceVector();
  return sorted_result;
}

這里是一種 InOrderProduceVector() 實現：

template <typename BlaBla>
class BST
{
public:
  // other code ...
  vector<BlaBla*> InOrderProduceVector()
  {
    vector<BlaBla*> 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<BlaBla*>& destination)
  {
    if (!node) return;
    InOrderProduceVectorHelper_(node->left, destination);
    destination.push_back(node->item);
    InOrderProduceVectorHelper_(node->right, destination);
  }

private:
  BSTNode* root_;
};

但是呢，我們首先需要最高評價的物品，來替換掉按順序遍歷生成最低評級的物品。這是因為它的性質，是從低到高的順序遍歷物品，「自下而上」。為了得到我們想要的東西，即列表按降序而不是升序排列，我們應該仔細查看順序遍歷實現。我們所做的是通過左節點，然后打印當前節點的值和通過右邊的節點。當我們第一次通過左節點時，這就是為什么我們首先獲得了「最左」節點（最左節點），這是具有最小值的節點。因此，簡單地將實現更改為首先通過正確的節點將導致我們按照列表的降序排列。我們會像其他人一樣將其命名，這是一種逆序的遍歷。讓我們更新上面的代碼（引入單個列表、警告、錯誤）：

// Reminder: this is pseudocode, no bother with "const&", "std::" or others
// forgive me C++ fellows

template <typename BlaBla>
class BST
{
public:
  // other code ...

  vector<BlaBla*> ReverseInOrderProduceVector(int offset, int limit)
  {
    vector<BlaBla*> 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<BlaBla*>& destination, int offset, int limit)
  {
    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<Item*> GetItemsByKeywordInSortedOrder(string keyword, offset, limit) // pagination using offset and limit
{
  // assuming IndexTable is a big hashtable mapping keywords to Item BSTs
  BST<Item*> 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<Item*> sorted_result = items.ReverseInOrderProduceVector(offset, limit);
  return sorted_result;
}

通過排序關鍵詞查找電影或產品

這就對了，我們可以非常快速地提供物品搜索結果。如上所示，反轉索引在搜索引擎中最常用，例如谷歌搜索。雖然谷歌搜索引擎非常復雜，它確實利用了某些簡單的思想，來將搜索查詢匹配到文檔上，并盡可能快速地提供結果。

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

DFS vs. BFS

如果你對這個問題不熟悉，想想你在遍歷樹的時候可用于存儲節點的數據結構。如果對比分層遍歷樹和上文介紹的其他方式（前序/順序/后序遍歷），就會發現兩種主要的圖遍歷方法：深度優先搜索（DFS）和廣度優先搜索（BFS）。

深度優先搜索尋找最遠的節點，廣度優先搜索先尋找最近的節點。

深度優先搜索——更多動作，更少思考。
廣度優先搜索——在進一步行動之前先仔細觀察四周。

DFS 很像前序/順序/后序遍歷，而 BFS 用于分層輸出樹節點。我們需要一個隊列（數據結構）來存儲圖的「層級」，同時輸出（訪問）其「父級」。在之前的插圖中，節點是隊列中淺藍色的點。每一層的節點被從隊列中取走，同時在訪問每個被取走的節點時，我們還應該將其子節點插入隊列（為下一層做準備）。下列代碼很簡單，可以幫助大家了解 BFS。代碼假設圖是連通的，盡管我們可以修改代碼，使其應用于非連通圖。

// Assuming graph is connected // and a graph node is defined by this structure // struct GraphNode { //   T item; //   vector<GraphNode*> children; // } // WARNING: untested code void BreadthFirstSearch(GraphNode* node) // start node {  if (!node) return;  queue<GraphNode*> 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 << cur->item;  } }

在基于節點的連通圖表示上可以輕松地了解基本思想。記住圖遍歷的實現因圖表示而異。BFS 和 DFS 在解決圖搜索問題中是重要的工具（但是存在大量圖搜索算法）。盡管 DFS 具備優雅的遞歸實現，但進行迭代實現更合理。我們使用隊列進行 BFS 的迭代實現，而 DFS 則需要堆棧。圖領域中一個最流行的問題，同時也可能是你閱讀本文的原因之一是尋找圖節點之間的最短路徑。這需要我們進行最后一個實驗。

示例：Uber

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

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

黃色路線是車輛到用戶處的可能路徑。問題在于計算車輛到達用戶的最小距離，即尋找最短路徑。盡管這更多地涉及谷歌地圖而不是 Uber，我們仍然嘗試解決這一特定和簡化案例，其原因主要在于通常存在多輛車，Uber 可能需要計算離用戶最近的車。就這張插圖而言，這意味著計算全部三輛車的最短路徑并確定哪輛車最適合該行程。為了使問題簡潔，我們將討論只有一輛車的情況。下圖顯示了一些到達用戶的可能路徑。

車輛到達用戶的可能路徑

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

這是一個無定向的加權圖（更具體地說是，邊加權）。為了找到從 B（車）到 A（用戶）的最短途徑，我們應該找到他們之間的一條邊權重最小的路。你可以自由的設計你自己版本的解決方案，我們還是使用 Dijkstra 的版本。下面的步驟是從維基百科上找到的 Dijkstra 的算法的步驟。

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

1. 標記所有未訪問節點。創建所有未訪問節點的集合「unvisited set」。

2. 為每個節點分配一個實驗距離值：初始節點的距離值設置為 0，其他節點設置為無窮大。將初始節點設置為當前節點。

3. 對于當前節點，考慮其所有未訪問近鄰，通過當前節點計算它們的實驗距離。對比新計算的實驗距離和當前分配的值，分配較小的值。例如，如果當前節點 A 的距離是 6，連接 A 與近鄰 B 的邊長度為 2，則經過 A 到 B 的距離是 6 + 2 = 8。如果 B 之前標記的距離大于 8，則將其更改為 8。反之，保留當前值。

4. 當我們考慮完當前節點的所有近鄰之后，將當前節點標記為已訪問，并從 unvisited set 中移除。已訪問節點無需再檢查。

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

6. 反之，選擇標記有最小實驗距離的未訪問節點，將其設置為新的「當前節點」，并返回第 3 步。

在我們的示例中，我們首先將節點 B（車輛）設置為初始節點。前兩步：