核心概念#

本章介紹圖論（Graph Theory）的基礎概念，以及如何用圖的遍歷算法來實現網絡爬蟲（Web Crawlers），自動下載互聯網上的所有網頁。

1. 圖論#

  • 圖論起源於 1736 年歐拉（Leonhard Euler）對哥尼斯堡七橋問題的研究：能否每座橋恰好走一遍並回到原點？歐拉證明不可能，由此開創圖論
  • 圖由節點和連接節點的弧組成。例如中國公路網：城市是節點，國道是弧
  • 圖的遍歷有兩種主要算法：
    • 廣度優先搜索（BFS, Breadth-First Search）：先訪問所有直接相連的節點，再逐層擴展
    • 深度優先搜索（DFS, Depth-First Search）：沿一條路走到底，再回頭探索其他路
  • 無論哪種方法，都需要記錄已訪問的節點，避免重複訪問或遺漏

2. 網絡爬蟲#

  • 互聯網本質上是一張大圖：每個網頁是一個節點，超鏈接（Hyperlinks）是連接網頁的弧
  • 網絡爬蟲從任一網頁出發，用圖的遍歷算法自動訪問每個網頁並存儲
  • 世界上第一個網絡爬蟲是麻省理工學生馬休·格雷（Matthew Gray）於 1993 年寫的「WWW Wanderer」
  • 實際工程中的規模驚人：Google 在 2013 年索引約 10000 億個網頁，假設每秒下載一個網頁，下載 100 億個需要 317 年

一個商業的網絡爬蟲需要成千上萬個伺服器通過高速網絡連接，如何建立和協調這樣的系統，是網絡設計和程序設計的藝術。

3. 延伸閱讀：圖論的兩點補充說明#

歐拉七橋問題的證明#

  • 將每塊連通的陸地作為一個頂點，每座橋作為一條邊，可以將問題抽象為圖
  • 定理：如果一個圖能從一個頂點出發，每條邊不重複地遍歷一遍回到該頂點，那麼每一個頂點的度（相連的邊數）必須為偶數
  • 哥尼斯堡七橋的圖中有多個頂點的度為奇數，因此不可能一次走遍

構建網絡爬蟲的工程要點#

  • BFS vs DFS：搜索引擎的爬蟲基本上採用 BFS，因為首頁直接鏈接的網頁通常最重要；但實際排程更接近優先級排序（Priority Queue）
  • 頁面分析和 URL 提取：現代網頁大量使用 JavaScript 生成 URL，需要模擬瀏覽器才能提取完整鏈接
  • URL 去重：使用哈希表（Hash Table）記錄已下載的網頁，避免重複下載；分布式系統中維護統一的哈希表是一大挑戰
  • 解決方案：明確每台伺服器的分工，並採用批量查詢來減少通信次數

本章小結#

圖論出現後很長時間只應用於小規模問題，但隨著互聯網的出現，圖的遍歷方法找到了用武之地。很多看似抽象的數學方法，會隨著時間推移突然派上大用場。

Backward Boolean Algebra And Search Pagerank Forward