1986 John Hopcroft & Robert Tarjan —— 圖演算法的效率革命#

「同樣一張圖，笨方法要跑到天荒地老，聰明方法瞬間結案。兩位史丹佛/康乃爾學者如何把圖論變成可執行的數學？」

案件檔案#

1970 年代，組合優化領域只問「能不能解」，不問「多快」。 Knuth（1974 案）建立了分析框架，但圖與資料結構的深層效率理論尚待開拓。兩條線索：Hopcroft 的自動機與複雜度背景、Tarjan 的高中生傳奇（18 歲與 Knuth 合作）。

判定 n 節點圖是否平面，達到線性時間 O(n)——在此之前連存圖都要 O(n²)。技法：深度優先搜尋（DFS）把圖化為 搜尋樹 + 返回邊 的結構，一切性質在樹上提取。

一次 DFS 即可線性時間求出：

強連通分量（SCC）、關節點、雙連通分量、橋
關鍵量：low-link v = min(disc[v], 所有返回邊可達的最小探索序號)
SCC 條件：low[v] == disc[v] 時彈出棧

「探索序 + 回溯值」的設計模式成為圖演算法的通用語言。

Tarjan 1975 年證明帶路徑壓縮 + 按秩合併的 Union-Find：

n 次操作的總成本 O(n · α(n))，α 為反 Ackermann 函數
α(n) < 5，對一切實際 n 而言近乎常數

攤還分析（amortized analysis）：不看單次操作，看序列總帳——此後成為資料結構理論的標準方法論（影響 Fibonacci 堆、 splay tree，皆 Tarjan 系）。

Hopcroft–Ullman 教科書（《形式語言與自動機》）與 Hopcroft–Karp 二分圖最大匹配 O(E√V)（1973）—— 理論敘事與演算法改良雙軌並進。

本案的偵探學核心：效能界不是統計，是定理。線性時間的證明依賴「計數論證」：每次操作都為某個勢函數（potential）存款或提款，總帳有界即總時間有界——這是把演算法變成可證明對象的又一里程碑（接續 Floyd 1978 案）。