1972 - 塔揚強連通分量（線性時間圖論演算法）#
案件摘要#
1972 年，史丹佛的博士生 Robert Tarjan（1948–） 與康乃爾的 John Hopcroft（1934–） 系統化地研究深度優先搜尋（DFS），發表了一連串線性時間的圖論演算法， 其中最耀眼的是 Tarjan 的強連通分量（SCC）演算法：
強連通分量：有向圖中互相可達的極大點集—— - 圖 \(G\) 的 SCC 是把點劃分成互相可達的區塊； - Tarjan 用一個巧妙的 low-link 值，在一次 DFS 中就偵測出所有區塊； - 同時期，並查集（union-find） 加上路徑壓縮，達到近乎常數的均攤時間。
這些演算法成為編譯器、資料庫、網路的基石—— 兩人於 1986 年共同獲得圖靈獎。
前因 -- 為什麼會有這個案子#
- Dijkstra 的最短路徑（1959）： Edsger Dijkstra 發表 \(O(V^2)\) 的最短路徑演算法（見
1959-迪傑斯特拉最短路徑.md）—— 圖論演算法的第一個經典，但只處理單源最短路徑， 有向圖的整體結構（誰可達誰、哪些點互相綁在一起）仍無有效演算法。 - Knuth 的演算法分析（1968）： Donald Knuth 出版《The Art of Computer Programming》第一卷（見
1968-克努特演算法藝術.md）—— 演算法需要嚴格的複雜度分析成為共識：
「線性時間」開始成為圖論演算法的聖杯。 - Cook 的 NP-完全（1971）： Stephen Cook 證明 SAT 是 NP-完全（見 1971-庫克NP完全.md）—— 許多問題註定無多項式時間解； 反過來說，能在線性時間解決的問題格外珍貴—— SCC 與並查集正是這樣的問題。 - 康乃爾與史丹佛的聯手（1970–1972）： John Hopcroft 在康乃爾大學研究** DFS 的系統化應用（平面圖測試、雙連通分量）； Robert Tarjan 是史丹佛的博士生（師從 Knuth 與 Floyd），1971–72 年間 在 Hopcroft 的啟發下，把 DFS 變成一把萬用偵探放大鏡**：
線索與推理 -- 數學式、程式、理論#
第一條線索：DFS 森林與發現時間#
深度優先搜尋在圖上走出一棵（或一片）DFS 森林： - 發現時間（discovery time）： \(disc[v]\) = 節點 \(v\) 第一次被拜訪的序號； - DFS 的邊分成：樹邊（往下探索）、回邊（指回祖先）、跨邊； - 關鍵性質：一個 SCC 的所有節點，在 DFS 森林中構成一個（且只有一個）子樹區塊—— SCC 的根是區塊中發現時間最小的節點。
第二條線索：low-link——Tarjan 的偵探放大鏡#
定義： \(low[v]\) = 從 \(v\) 出發，經過至多一條回邊能到達的最小發現時間：
- 初始化： \(low[v] = disc[v]\) （自己）；
- 回邊 \((v,w)\) ： \(low[v] = \min(low[v], disc[w])\) （指回堆疊上的舊節點）；
- 子樹回傳： \(low[u]\) 吸收回父節點： \(low[parent] = \min(low[parent], low[u])\) 。 判定法則：當 DFS 從 \(v\) 返回時，若
此時從堆疊彈出到 \(v\) 為止的所有節點，恰好構成一個 SCC！ 整個演算法只做一次 DFS： \(O(V+E)\) ——線性時間。
第三條線索：並查集與均攤分析#
並查集（union-find）維護不相交集合，支援兩個操作： - \(find(x)\) ：找 \(x\) 所在集合的代表（根）； - \(union(x, y)\) ：合併兩個集合。 兩大加速技巧（Tarjan 與 van Leeuwen 分析）： - 路徑壓縮： \(find\) 之後，路徑上所有節點直接指向根； - 按秩合併：矮的樹掛到高的樹下，避免退化成長鏈。 均攤複雜度（Tarjan, 1975）：
其中 \(\alpha(n)\) 是 Ackermann 反函數——增長得比 \(\log n\) 、 \(\log^* n\) 都慢：
均攤分析（amortized analysis）：單次操作可能慢，但序列的總成本除以操作數 ——這個思想成為演算法分析的標準工具。
Python：Tarjan SCC 與並查集#
# 1) Tarjan SCC（迭代式深度優先搜尋，避免遞迴深度限制）
def tarjan_scc(graph):
"""Tarjan 1972：線性時間強連通分量（low-link 法）"""
index_counter = [0]
stack, on_stack = [], set()
index, low = {}, {}
sccs = []
for root in graph:
if root in index:
continue
work = [(root, iter(graph[root]))] # 模擬遞迴的呼叫堆疊
while work:
v, it = work[-1]
if v not in index:
index[v] = low[v] = index_counter[0]
index_counter[0] += 1
stack.append(v)
on_stack.add(v)
advanced = False
for w in it:
if w not in index:
work.append((w, iter(graph[w]))) # 樹邊：向下探索
advanced = True
break
elif w in on_stack:
low[v] = min(low[v], index[w]) # 回邊：更新 low-link
if advanced:
continue
work.pop()
if work:
u = work[-1][0]
low[u] = min(low[u], low[v]) # 回傳：父節點吸收子樹
if low[v] == index[v]: # v 是 SCC 的根
comp = []
while True:
w = stack.pop()
on_stack.discard(w)
comp.append(w)
if w == v:
break
sccs.append(comp)
return sccs
# 2) 並查集（Union-Find）：路徑壓縮 + 按秩合併
class UnionFind:
"""Tarjan–van Leeuwen：路徑壓縮 + 按秩合併，均攤 O(α(n))"""
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
root = x
while self.parent[root] != root:
root = self.parent[root]
while self.parent[x] != root: # 路徑壓縮：全部指向根
self.parent[x], x = root, self.parent[x]
return root
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False
if self.rank[rx] < self.rank[ry]: # 按秩合併：矮樹掛到高樹
rx, ry = ry, rx
self.parent[ry] = rx
if self.rank[rx] == self.rank[ry]:
self.rank[rx] += 1
return True
# 3) 對範例圖測試： SCC：{0,1,2}、{3,4}、{5}
graph = {
0: [1], 1: [2], 2: [0, 3],
3: [4], 4: [3, 5],
5: []
}
print("Tarjan SCC（強連通分量）：")
for i, comp in enumerate(sorted(tarjan_scc(graph), key=lambda c: min(c))):
print(f" 分量 {i}: {sorted(comp)}")
print("\n並查集（路徑壓縮 + 按秩合併）：")
uf = UnionFind(6)
for a, b in [(0, 1), (1, 2), (3, 4)]:
uf.union(a, b)
print(" 合併 (0,1), (1,2), (3,4) 後：")
for a, b in [(0, 2), (2, 4), (4, 5)]:
print(f" find({a}) == find({b})？{uf.find(a) == uf.find(b)}")
print(f" 再合併 (2,4)：{uf.union(2, 4)}")
print(f" find(0) == find(4)？{uf.find(0) == uf.find(4)}")
Tarjan SCC（強連通分量）：
分量 0: [0, 1, 2]
分量 1: [3, 4]
分量 2: [5]
並查集（路徑壓縮 + 按秩合併）：
合併 (0,1), (1,2), (3,4) 後：
find(0) == find(2)？True
find(2) == find(4)？False
find(4) == find(5)？False
再合併 (2,4)：True
find(0) == find(4)？True
結案 -- 後果與影響#
- 編譯器與資料流分析（1970s–）： SCC 是編譯器的日常工具——
- 呼叫圖分析：找出遞迴群組、決定內聯順序；
- 資料流分析：在 SCC 縮減圖上迭代求解到不動點；
- 模組依賴：偵測循環依賴、決定編譯順序。
- 資料庫與網路（1970s–）：
- 查詢最佳化：SQL 的遞迴 CTE、遞迴查詢在 SCC 上求值；
- 網路路由：網路拓撲的強連通結構分析；
- 垃圾回收：引用圖中互相綁定的物件群組（循環引用偵測）。
- 並查集的普及（1970s–）：
- Kruskal 最小生成樹、動態連通性、圖像分割、格子遊戲；
- Python（網路X）、Java、C++ 函式庫都內建 union-find；
- 均攤分析成為演算法課程的標準內容（CLRS 教科書專章）。
- 圖論演算法的黃金年代（1971–1975）：
Tarjan 接著用並查集解決離線最小生成樹驗證等問題（1975–79）， 並證明並查集的 \(\alpha(n)\) 下界——均攤分析與下界證明雙全。 - 圖靈獎（1986）： Hopcroft 與 Tarjan 共同獲得 1986 年圖靈獎—— 表揚他們「對演算法與資料結構設計分析的奠基性貢獻」。
Hopcroft 之後轉向自動機理論（Hopcroft–Ullman 教科書）； Tarjan 至今仍是演算法界的常青偵探（Fibonacci 堆、splay tree、LCT）。 - 歷史定位：Tarjan 與 Hopcroft 把圖論演算法帶進線性時代—— 他們證明：只要選對工具（DFS、並查集），許多問題根本不難；
一次 DFS，看穿整張圖。
關鍵人物與文獻#
- R. Tarjan：Depth-First Search and Linear Graph Algorithms（SIAM J. Computing, 1972）；並查集均攤分析（1975）；Efficiency of a Good But Not Linear Set Union Algorithm（1975）；1986 圖靈獎。
- J. Hopcroft：與 Tarjan 合作的平面圖測試（1971）、雙連通分量、SCC；Introduction to Automata Theory, Languages, and Computation（1979, 與 Ullman）；1986 圖靈獎。
- E. W. Dijkstra：最短路徑（1959）——圖論演算法的先驅。
- D. Knuth：The Art of Computer Programming（1968–）——Tarjan 的博士導師。
- S. Cook：NP-完全（1971）——襯托線性時間演算法的珍貴。
- M. van Leeuwen：與 Tarjan 合作出路徑壓縮 + 按秩合併的複雜度分析（1984）。
- 相關案件：
1959-迪傑斯特拉最短路徑.md、1968-克努特演算法藝術.md、1971-庫克NP完全.md、1960-霍爾快速排序.md。