圖論是組合數學的一個分支，也是今天在計算機科學中應用最多的數學基礎之一。一個計算機行業技術從業者對圖論的理解深度，決定了他在這個行業中能走多遠。本章從圖論的起源講起，介紹圖的遍歷、最短路徑、最大流和最大配對等核心算法。

5.1 圖的本質：點與線#

圖論的三個來源#

  • 歐拉與柯尼斯堡七橋問題：歐拉將地圖簡化為只有點和線的抽象圖，發明了圖論這個工具。他證明了由於四個節點都連接奇數條邊，無法一筆畫完成遍歷
  • 電路學家基爾霍夫：利用電路圖研究電流流動，啟發了最大流、網絡平衡等圖論問題
  • 地圖的染色問題：四色定理等問題進一步豐富了圖論工具

圖的現代應用#

  • 互聯網本身就是一張圖：服務器是節點，網絡線是邊；網頁是節點，超鏈接是邊
  • 社交網絡也是一張圖：每個社交主體構成節點，關注和追蹤的關係是邊
  • Google 的 PageRank 算法就是利用互聯網超鏈接的圖結構來計算網頁重要性

圖的嚴格定義#

  • 圖可以定義為三元組 (V, E, φ) 或四元組 (V, E, φ, f)
  • V 是節點的集合，E 是邊的集合，φ 定義了節點和邊的對應關係，f 代表邊的權重
  • 圖的連通性和節點之間的距離是重要的衡量指標
  • 圖的本質是對離散的、有限集合中各個元素之間關係的描述

要點：數學上抽象的圖是點和線的結合，節點是對現實世界對象的抽象描述，邊是對它們關係的描述。

5.2 圖的訪問：遍歷和連通性#

圖論中使用頻率最高的算法就是遍歷算法，即通過某種方式訪問到圖中所有的節點。

深度優先遍歷（DFS）#

  • 從一個節點出發，沿著一條路徑盡可能深入，直到無法繼續時回溯
  • 需要標記已訪問的節點以避免死循環
  • 遍歷過程中會產生一棵生成樹（Spanning Tree），包含圖中所有的節點及部分邊

廣度優先遍歷（BFS）#

  • 使用隊列（Queue）存儲待訪問的節點，按照層次逐層訪問
  • 先訪問起始節點的所有相鄰節點，再訪問下一層的節點

連通性與非連通圖#

  • 連通圖：任意兩個節點之間都可以通過若干條邊到達
  • 實際應用中的圖未必都是連通的，需要對多個連通分量分別遍歷，得到多棵生成樹（稱為森林）

要點：深度優先遍歷和廣度優先遍歷是圖論中最基本的兩種遍歷方法。

5.3 構建網絡爬蟲的工程問題#

從理論上講實現一個網絡爬蟲非常簡單，核心代碼不超過 100 行，但工程上有很多難題需要解決：

  • 有向圖的問題：互聯網的超鏈接是單向的，大部分有向圖不具有強連通性，從一個節點出發能訪問到所有節點的可能性要小很多
  • 節點的不可枚舉問題：互聯網上的網頁集合是未知的，需要動態地發現新網頁
  • 節點和鏈接的動態變化：網頁在不斷產生、刪除和修改
  • 體量問題：Google 的網頁有數百億個，單台服務器無法處理
  • 並行工作的協調問題：多台服務器之間如何避免重複工作，需要構建兩到三級的爬蟲系統
  • 網速限制問題：需要在不影響網站服務的前提下，以最快速度下載網頁

深度優先 vs. 廣度優先#

  • 網絡爬蟲應該用深度優先還是廣度優先，答案並非一成不變
  • 通常網絡爬蟲系統需要有專門模塊，根據不同場景有機結合兩種策略

通過網絡爬蟲可以看出計算機科學和計算機工程之間的差別。一個理論上看似不太複雜的問題，在工程上卻可能極為複雜。沒有數年全職高水平工作經驗的工程師，是不可能完成的。

5.4 動態規劃：尋找最短路徑的有效方法#

編輯距離問題#

  • 自動校正拼寫錯誤的核心概念：編輯距離（Editing Distance）
  • 三種基本操作：插入、替換、刪除，以差異的字母數量為單位
  • 編輯距離滿足三角形不等式
  • 兩個拼寫的所有可能對應方式可以用一個網格圖中的路徑來描述，從左下角到右上角的路徑數是卡特蘭數（指數級別）

Dijkstra 算法#

  • 將「尋找全程最短路徑」的問題分解成一個個尋找局部最短路徑的小問題，用遞歸方式加以解決
  • 算法步驟：
    • 先算出起點 S 到所有相鄰節點的最短距離
    • 找到能直接到達的節點中最近的，然後把這些節點連同原來的節點放到新的集合中
    • 重複上述過程直到找到終點 E
  • 複雜度為 O(|V|² + |E|)，將指數級複雜度降為平方級複雜度
  • 前提是所有邊的距離都是正數

有向無環圖（DAG）#

  • 有回路的有向圖可能導致 Dijkstra 算法失效
  • 有向無環圖在金融市場的套利交易中有特殊應用

拼寫校正的實際改進#

  • 將錯誤拼寫和正確拼寫的編輯距離從單純的數字差距變成加權距離
  • 考慮鍵盤上字母的位置、多詞漏掉空格等實際情況
  • 使用語言模型來選擇最可能的正確拼寫

要點：在加權有向圖中，尋找從某一點到另一點的最短路徑是一個很有意義的問題。如果採用窮舉的方法是指數複雜度，而採用動態規劃的方法可以降為平方複雜度。

5.5 最大流：解決交通問題的方法#

最大流問題的背景#

  • 在有權重的有向圖中，權重可以代表兩個節點之間的帶寬或流量
  • 實際應用：互聯網的信息流量、公路網絡的車流、供水供電系統等
  • Google 等公司需要在全球數據中心之間高效傳輸海量數據

最小切割與最大流#

  • 將連通圖從中間切開，分為起始節點和目標節點兩部分
  • 最大流等於最小切割的容量（最大流-最小切割定理）
  • 要讓網絡流量達到最大，就要讓切割線上的每條邊都達到飽和

Ford-Fulkerson 算法#

  • 從任意一種滿足條件的流量分配開始
  • 找到一條從 S 到 T 的增廣路徑（Augmenting Path），增加流量
  • 不斷迭代直到無法再找到增廣路徑
  • 改進版本：Edmonds-Karp 算法，複雜度為 O(|V||E|²)

現實中的複雜性#

  • 多重優化標準（不僅是總量，還有優先級）
  • 網絡流量的動態變化
  • 傳輸方向切換的延時
  • 網絡故障的應對

要點：最小切割流量和最大流之間的關係。最大流算法的精髓是通過在水平（流量）和垂直（切割）兩個維度不停地切換來解決問題。

5.6 最大配對：流量問題的擴展#

二分圖的最大配對#

  • 二分圖（Bipartite Graph）：節點集 V 被分為兩個不相交的子集 V₁ 和 V₂，所有邊都橫跨在兩個子集之間
  • 配對：在兩個節點集之間尋找一對一的對應關係
  • 最大配對：讓產生對應的節點數達到最多

應用場景#

  • 網約車司機和乘客的配對
  • 婚戀網站上男女雙方的配對
  • 讀者和被推薦新聞之間的配對
  • 搜索關鍵詞和廣告的配對

與最大流的等價性#

  • 將二分圖擴展為一個有起始節點 S 和目標節點 T 的連通圖
  • 二分圖的最大配對等同於實現從 S 到 T 的最大流
  • 可以直接使用 Ford-Fulkerson 算法解決，在二分圖中複雜度只有 O(|E|)

三類難度的配對問題#

  • 靜態的一對一配對（如打車）：最容易
  • 動態的配對（如外賣）：難度在於動態變化帶來的不確定性
  • 廣告配對（如 Google 廣告系統）：體量最大，最為複雜。Google 雲計算系統的核心模塊 MapReduce 最初就是為優化廣告配對而設計的

要點：最大流問題和最大配對問題從本質上講是一回事，或者說它們是等價的。理解等價思想的本質是成為頂級計算機專家的必要條件。能夠看出這些具體問題是圖論中的配對問題，同時明白配對問題和最大流問題的關鍵，就達到了四級工程師的水準。