图上的通用迭代机器（下）：范式、领域与边界

核心问题：框架是真正的统一，还是表面的巧合？

上篇建立了统一框架的骨架：Layer 0（数学规格 EQ/OPT/CST/STR）和 Layer 1（七组件迭代机器）。但一个框架的价值取决于它能走多远——如果经典算法思想（DP、贪心、分治、回溯）装不进来，或者框架只在图算法内部有效，那它就不过是表面的结构巧合。 本文的任务是双向验证：向内覆盖经典范式，向外延伸到图算法之外的领域。

核心思路：组件配置的谱 + 跨领域的结构同构

核心发现：六种经典范式都可以精确映射到迭代机器的不同组件配置——从最紧的贪心（PQ-min + 无重入）到最松的局部搜索（frontier≈1），形成一个连续的”控制复杂度谱”。而四个跨领域应用（GC、编译器 dataflow、Belief Propagation、GNN）证明这个框架的结构不是图算法的偶然巧合，而是一种更深层的计算模式。最终，COMBINE 操作的代数结构从半环到非线性构成的谱，决定了算法是否有收敛保证。

经典范式统一：把已知的算法思想装入框架

本节按控制复杂度递增的顺序，逐个审视六种经典范式。对每个范式，先讲经典认知（含数学基础），再精确映射到框架组件。

贪心：一遍，不回退

经典认知：贪心算法在每一步做出局部最优选择，且这个选择一旦做出就不需要撤销。数学上，贪心的正确性通常依赖拟阵 (matroid) 结构或贪心选择性质 + 最优子结构的组合。

Dijkstra 和 Prim 是贪心范式在图上最经典的两个实例。它们有惊人相似的结构：

数学规格：典型求解 OPT（优化目标），如 Dijkstra 求最短路径、Prim 求最小生成树。

装入框架：贪心 = label-setting frontier——SELECT 总是选局部最优节点，一旦选中 (FINISH)，其 State 值永远不会被修改。因此重入模式 = 无。

框架组件	贪心的约束
SELECT	局部最优（PQ-min）
重入	无（一次定稿）
TERMINATE	Frontier 空 或 已收集足够

关键洞察：贪心性质保证了 SELECT 取出的节点已经是最优的——不需要重入。当这个保证失效时（比如有负权边），贪心退化，需要 DP 或迭代松弛。

动态规划：一遍，但需要依赖管理

经典认知：DP 的核心是三个条件——最优子结构（大问题的最优解包含子问题的最优解）、重叠子问题（同一子问题被多次需要）、无后效性（子问题的解确定后不受后续决策影响）。

DP 的本质 = 识别出子问题的依赖关系是无环的 (DAG)，因此每个子问题只需处理一次。

数学规格：典型求解 EQ（方程/不动点）或 OPT（优化目标）——Bellman 方程、Floyd-Warshall 递推、背包递推都是方程形式。

装入框架：

• Bottom-up DP = 在子问题空间 DAG 上按拓扑序遍历——这是 BFS 逐层推进的精确实例
• Top-down + memoization = DFS + 缓存

关于 top-down DP 的重要说明：top-down+memo 是框架的隐喻性映射而非结构性映射——call stack 充当隐式 LIFO frontier，memoization 充当 visited 标记。映射的价值在于揭示结构相似性，而非声称实现等价。

框架组件	DP 的约束
Graph	子问题空间（DAG）
SELECT	拓扑序（bottom-up）或递归调用序（top-down）
COMBINE	子问题的递推关系
重入	无（每个子问题只处理一次）

桥梁：当依赖关系有环时，一遍不够——DP 变成了迭代松弛（需要重入到不动点）。

分治：DP 的特例——子问题不重叠

经典认知：分→治→合 三步。分治和 DP 的区别在于：分治的子问题不重叠（树结构），而 DP 的子问题重叠（DAG 结构）。不重叠意味着不需要 memoization。

数学规格：与 DP 相同，通常是 EQ 或 OPT。

装入框架：分治 = DFS + 回溯阶段的 COMBINE（在合并阶段才产生结果，而非展开阶段）。

框架组件	分治的约束
Graph	子问题树（不重叠）
SELECT	LIFO（DFS）
COMBINE 时机	回溯时（后向）
重入	无

桥梁：子问题从树变成 DAG（有重叠）→ 需要 memo → 变成 DP。

松弛与迭代逼近：多遍到不动点

经典认知：当依赖关系有环时，一遍不够。松弛 (relaxation) 的直觉是”弹簧”——每次 UPDATE 都把 State 往最终答案拉近一点。反复松弛，直到所有”弹簧”都平衡（不动点）。

数学规格：典型求解 EQ（方程/不动点）——Bellman 方程、PageRank 方程、dataflow 方程都是这个形式。

数学上，松弛 = 反复应用映射 $f$，直到 $x = f(x)$。这需要收敛保证——并非所有映射都会收敛。

四种收敛机制：

1. Tarski 不动点定理：完备格 + 单调传递函数 → 保证 least fixed point 存在；加上有限格高度 → 保证有限步收敛（编译器 dataflow 分析）
2. Banach 不动点定理：压缩映射 $\|f(x)-f(y)\| \leq c\|x-y\|$, $c<1$ → 保证收敛（PageRank, $d < 1$）
3. Perron-Frobenius 定理：转移矩阵谱间隙 > 0 → 保证收敛（PageRank 的谱视角）
4. 路径长度上界：最短路径最多 $V-1$ 条边 → Bellman-Ford 最多 $V-1$ 轮

无收敛保证的情形：同步 label propagation 在二部图上可能振荡；loopy belief propagation 在一般图上不保证收敛。

Chaotic Iteration Theorem（混沌迭代定理）（Cousot & Cousot, 1977）的前提条件：完备格 + 有限高度 + 单调传递函数。在这些条件下，worklist 的处理顺序不影响最终结果（least fixed point 唯一），只影响到达速度。这和”BFS/DFS 都能找到所有可达节点”是同一个数学保证。RPO (Reverse Postorder) 是”好的 SELECT”，正如 PQ 之于 Dijkstra。

框架组件	迭代松弛的约束
COMBINE	松弛操作（通常在某种半环/格上）
UPDATE	单调的 $\min$, $\cup$, $\oplus$
重入	到不动点（或有界轮数）
TERMINATE	Frontier 空（无变化）或固定轮数

桥梁：DP 和迭代松弛是同一种方法在无环/有环依赖下的表现形式。

回溯与 Branch-and-Propagate：非单调，可回退

经典认知：回溯搜索在状态空间树上进行 DFS——做一个选择（branch），推进到失败（dead end），然后撤销选择回到上一个决策点（backtrack）。

必须区分两种情况：

数学规格：典型求解 CST（约束满足）——SAT、k-着色、N-Queens 都是寻找满足约束的赋值。

1. 朴素回溯（如 naive N-Queens）：状态空间树上的 DFS + pruning。单层结构，对框架的映射较松。
2. Branch-and-Propagate（如 AC-3（弧一致性算法）+ 回溯、DPLL、CDCL）：两层嵌套——外层非单调 DFS（branch + backtrack），内层单调 frontier（约束传播 / unit propagation）。内层的 propagate 完全 fit 框架。

关键洞察：回溯的独特之处是 State 非单调——赋值可以撤销回到初始状态。这是它和所有其他范式的本质区别。在所有其他范式中，State 的变化是单调的（距离只能减小、集合只能增大、概率只能趋近）。

局部搜索：最松的映射

经典认知：hill climbing（爬山法）、模拟退火、tabu search（禁忌搜索）、遗传算法——都是在解空间图上搜索更好的解。

数学规格：典型求解 OPT（优化目标）——最小化/最大化某个目标函数，但不一定是凸优化。

装入框架：解空间图上的 frontier（通常 size ≈ 1）。SELECT = 当前解的邻域中选最好的（或概率性选择）。

诚实标注：这是最松的映射——骨架一致（当前解 → 生成邻居 → 评估 → 接受/拒绝），但 frontier 退化为单点，COMBINE 是完整的目标函数评估，收敛无保证。框架提供的教学价值是让学生看到”局部搜索在做什么”，而不是声称它和 BFS 等价。

范式流动图

六种范式不是孤立的——它们之间存在”条件变化→范式迁移”的关系：

• 失去贪心性质 → 从贪心迁移到 DP 或迭代松弛
• 依赖从无环变有环 → 从 DP 迁移到迭代松弛
• 子问题不重叠 → DP 简化为分治
• 需要撤销状态 → 迁移到回溯
• 放弃精确解 → 迁移到局部搜索

跨领域 Rosetta Stone

框架不只统一图算法——它跨越到 GC、编译器、概率推断和图神经网络。

GC Tri-color Marking = Boolean 可达性方程的 Frontier 迭代

GC 的标记阶段在求解什么方程？

$\text{marked}(v) = (v \in \text{roots}) \lor \exists u: \text{marked}(u) \land (u \to v)$

这就是 Boolean 可达性方程——和 BFS 求解的方程结构完全相同。

GC tri-color invariant（没有黑→白的直接引用）= BFS 的”已完成节点的所有邻居都已发现”——是同一个不变式的不同表述。

独特元素：Write Barrier。并发 GC 中 mutator 在遍历过程中修改图（新增引用）。Write barrier 是动态图上的 repair 机制——在静态图搜索中没有对应物。

历史注记：同一个 Dijkstra 发明了最短路算法 (1959) 并是 tri-color invariant (1978) 的主要作者之一。据我们所知，他从未显式写过两者的结构联系——尽管 EWD 编号达 1300+，我们无法完全排除这种可能。

编译器 Dataflow 分析 = 格上方程组的 Worklist 迭代

Dataflow 分析在求解什么方程？

$\text{out}(b) = f_b\Big(\bigsqcup_{p \in \text{pred}(b)} \text{out}(p)\Big)$

其中 $f_b$ 是 transfer function，$\bigsqcup$ 是格上的 join（如集合并）。

这和 Bellman-Ford 的结构是对称的：Bellman-Ford 在热带半环 $(\mathbb{R}_{\geq 0} \cup \{\infty\}, \min, +)$ 上松弛，dataflow 在集合格上松弛。两者都需要重入（值变化时把后继重新加入 worklist），两者都在不动点终止。

Chaotic Iteration Theorem 保证：在满足前提条件时，worklist（工作列表）的处理顺序不影响正确性。RPO（Reverse Postorder，逆后序）顺序是编译器实践中最常用的 SELECT 策略——它利用了 CFG 的结构（大多数 flow 向前流动），正如 Dijkstra 的 PQ-min 利用了非负权假设。

Belief Propagation = 消息方程的迭代求解

Factor graph 上的 BP 在求解什么方程？

$\mu_{f \to x}(x) = \sum_{\sim x} f(\mathbf{x}) \prod_{y \neq x} \mu_{y \to f}(y)$

其中 $\sum_{\sim x}$ 表示对除 $x$ 以外的所有变量求和（边缘化），$\mu_{y \to f}$ 是从变量 $y$ 到因子 $f$ 的消息。

树上 BP = 两遍 DP（叶→根，根→叶），精确收敛。这是 DP 范式的直接实例：子问题依赖是无环的（树结构），每条消息只需计算一次。

Loopy BP = 在有环图上做同样的消息传递——但依赖有环，所以变成了迭代松弛到（期望的）不动点。不保证收敛，可能振荡或收敛到错误的边际分布。

GNN Message Passing = 参数化消息方程的截断迭代

GNN 的每一层在做什么？

$h_v^{(k+1)} = \sigma\Big(W \cdot \text{AGG}\big(\{h_u^{(k)}: u \in N(v)\}\big)\Big)$

结构上和 BP 相似——聚合邻居信息来更新节点状态。标准 GCN (Kipf & Welling, 2017) 通常在邻接矩阵上添加自环 ($\tilde{A} = A + I$)，使聚合包含节点自身特征；上式为简化的一般形式。GNN 与 BP 有两个关键差异：

1. 不迭代到收敛，而是固定 $K$ 层（截断迭代）
2. 参数 $W$ 通过梯度下降学习，而非手工设定

GIN (Graph Isomorphism Network) 在图区分能力上等价于 1-WL test (Xu et al., 2019)——注意这是区分能力的等价，不是一般计算等价。

代数深化

上篇说过，不同算法的 COMBINE 操作工作在不同的代数结构上。这种差异不是表面的——它直接决定了算法是否有收敛保证。

从左到右，代数结构越来越弱：

代数结构	代表	收敛保证
热带半环 $(\mathbb{R}_{\geq 0}\cup\{\infty\}, \min, +)$	Dijkstra, BF	Bellman 正确性定理
Max-product 半环 $([0,1], \max, \times)$	Viterbi	有限格
集合格 $(\mathcal{P}(D), \cup, \text{gen/kill})$	Dataflow	Tarski
实数半环 $(\mathbb{R}, +, \times)$	PageRank	Banach
概率半环	BP (tree)	精确 (DAG)
Majority vote（非半环）	Label Prop	无保证
非线性 (W·AGG + σ)	GNN	截断

框架不假装 COMBINE 代数”都一样”——相反，识别出 COMBINE 的代数结构，正是判断算法是否有收敛保证的关键。

全系列算法映射表

下面的交互表格覆盖了本学习路径中的主要算法。你可以按数学规格、求解方法、重入模式筛选，快速定位任何算法在框架中的位置。

全系列算法 × 框架映射表

数学规格:全部EQOPTCSTSTR求解方法:全部FIDPB&PGSCOMPNESTED重入模式:全部NoBoundedFixed-ptBacktrackYesK layers显示 26/26 个算法

Art.	算法	数学	求解	SELECT	COMBINE	重入	终止	收敛
1	BFS	EQ	FI	FIFO	d+1	No	Frontier ∅	Finite
1	DFS	STR	FI	LIFO	disc/finish	No	Frontier ∅	Finite
2	Tarjan SCC	EQ	FI	LIFO	min(low)	No	Frontier ∅	Finite
2	Kosaraju SCC	STR	FI	Finish-order	reachability	No	Frontier ∅	Finite
3	Topo Sort (Kahn)	STR	FI	In-degree=0	decrement	No	Frontier ∅	Finite
5	LCA (Binary Lifting)	STR	DP	k increasing	up[v][k-1]	No	k=log n	Finite
5	Tree Diameter	EQ	FI	FIFO (2×BFS)	d+1	No	Frontier ∅	Finite
5	Centroid Decomp	STR	COMP	Recursive	subtree size	No	Leaf	Finite
6	Dijkstra	EQ	FI	PQ-min(d)	d[u]+w	No	Frontier ∅	Finite
6	Bellman-Ford	EQ	FI	FIFO	d[u]+w	Bounded	V-1 rounds	Bounded
6	Floyd-Warshall	EQ	DP	k,i,j order	min(d,d+d)	No	k=V	Finite
6	DAG Relaxation	EQ	DP	Topo order	d[u]+w	No	All visited	Finite
7	A*	EQ	FI	PQ-min(f)	g+w	No	Goal popped	Finite
8	PageRank	EQ	FI	All (sync)	Σ PR/out	Fixed-pt	ε converge	Banach
8	Label Propagation	EQ	FI	All (sync)	majority	Fixed-pt	No change	None
9	Louvain	OPT	FI	Scan	ΔQ	Fixed-pt	No move	Monotone
10	Bron-Kerbosch	CST	B&P	Pivot DFS	intersect	Backtrack	P∪X=∅	Finite
11	Prim	OPT	FI	PQ-min(key)	w(u,v)	No	V-1 edges	Finite
11	Kruskal	OPT	GS	Sort by weight	Union-Find	No	V-1 edges	Finite
12	Dinic Max-Flow	OPT	NESTED	BFS+DFS	augment	Yes	No aug path	Finite
13	Hopcroft-Karp	OPT	NESTED	BFS+DFS	augment	Yes	No aug path	Finite
14	Greedy Coloring	CST	GS	DSatur/order	min unused	No	All colored	Finite
15	Christofides	OPT	NESTED	MST+Match	Euler+shortcut	No	Tour complete	Finite
17	BP (tree)	EQ	DP	Leaf→root	msg product	No	2 passes	Exact
17	BP (loopy)	EQ	FI	All (sync)	msg product	Fixed-pt	ε / max iter	None
20	GNN (GCN)	EQ	FI	All (sync)	W·AGG+σ	K layers	K layers	Truncated

诚实的边界

真正不 fit 的

1. 纯代数方法（矩阵求逆、高斯消元）——绕过了逐节点求解，直接在整个矩阵上操作
2. 随机构造（ER/WS/BA 图生成模型）——不是”求解”已有图上的问题，而是”构造”新图
3. 少数构造性算法（Hierholzer 欧拉回路）——用了栈但核心操作是拼接路径段，不是在求解方程

灰色地带

• 同步 vs 异步：框架默认异步（Gauss-Seidel 风格：更新立即可见），同步算法（如 synchronous PageRank）需要 double-buffering——框架能表达但需要额外标注
• COMBINE 代数不统一：从结合律+交换律的半环到非线性 GNN，跨度巨大。框架统一了结构骨架，但不统一代数性质
• 嵌套算法（max-flow、matching）：外层迭代 × 内层 frontier——不是单层迭代机器，需要用 NESTED 求解方法标注

框架的价值定位

这个框架不是要证明”所有图算法本质相同”——那不是真的。它的价值在于：

1. 提供共同词汇：用 SELECT/COMBINE/UPDATE/重入 等术语讨论不同领域的算法，降低跨领域理解的门槛
2. 揭示结构相似性：GC marking 和 BFS 的同构不是显而易见的，但框架让它变得可见
3. 定位差异所在：当两个算法的骨架相同时，差异必然在具体组件的选择上——这让比较变得精确
4. 辅助算法设计：面对新问题时，“写出数学规格 → 选择求解方法 → 实例化组件”是一个系统化的设计路径

工程实践中的统一视角

这个框架不只是教学工具——它在工业系统中有直接对应：

• Pregel / GraphX / Apache Giraph：vertex-centric 编程模型 = 框架的直接实现。compute(messages) = COMBINE + UPDATE，sendMessageTo(neighbor) = 产生 proposal，superstep 边界 = 同步控制策略
• LLVM Dataflow：worklist 的三种顺序（RPO/PO/WTO）= 三种 SELECT 策略。LLVM 的 DataFlowSolver 类结构几乎逐行对应框架组件
• V8 / Go GC：concurrent tri-color marking = 框架实例化 + write barrier 作为动态图修复机制

总结

本文填充了上篇建立的框架，从三个方向验证了它的覆盖面：

经典范式统一：

• 贪心 = label-setting frontier（PQ-min + 无重入），Dijkstra 和 Prim 共享这个骨架
• DP = 子问题 DAG 上的遍历（每节点一次），bottom-up = BFS 逐层，top-down = DFS + memo（隐喻性映射）
• 分治 = DP 在不重叠子问题（树）上的特例，COMBINE 在回溯阶段
• 迭代松弛 = 有环依赖下的多遍到不动点，四种收敛保证机制
• 回溯 = 非单调 State（可撤销）。Branch-and-Propagate 有两层嵌套：外层 DFS + 内层单调 frontier
• 局部搜索 = 解空间图上的 frontier≈1，最松但仍可见的映射

跨领域 Rosetta Stone：

• GC tri-color = Boolean 可达性方程的 BFS（结构完全同构）
• Dataflow 分析 = 格上方程组的 worklist 迭代（Chaotic Iteration 保证顺序无关性）
• Belief Propagation = 消息方程的 DP（树上精确）或迭代松弛（有环不保证收敛）
• GNN = 参数化消息方程的截断迭代（固定 $K$ 层 + 梯度学习）

代数深化：

• COMBINE 的代数结构从半环到非线性构成一个谱——结构越强，收敛保证越强
• 四种收敛机制：Tarski、Banach、Perron-Frobenius、路径长度上界

诚实的边界：

• 纯代数方法、随机构造、少数构造性算法不 fit
• 嵌套算法需要多层标注
• COMBINE 代数不统一——框架统一了骨架，不统一性质

现在，带着这个统一视角，让我们重新审视最基础的图遍历——下一站 Art. 1: BFS 与 DFS。后续每篇文章都会在末尾的 callout 中将该篇算法映射回本文的框架，形成一个完整的回指网络。