第 22 章 基本图算法

本章对应原书第 VI 部分导言与第 22 章。图是描述"关系"的通用语言：股票之间的相关性、货币之间的可兑换关系、因子之间的计算依赖、金融机构之间的拆借与担保，都可以画成图。本章讲图在计算机里怎么存，以及两种最基本的搜索——广度优先搜索（BFS）和深度优先搜索（DFS）。在它们之上可以直接得到无权最短路径、连通分量、拓扑排序、强连通分量、关节点与桥。后续的最小生成树（第 23 章）、最短路径和网络流都建立在这些基础之上，所以本章要讲透。

学习目标

读完本章，你应当能够：

1. 根据图的稀疏程度和查询需求，在邻接表、邻接矩阵（以及工程上的 CSR 格式）之间做选择，并说出各自的空间与时间代价。
2. 写出 BFS，证明它在 \(O(V+E)\) 时间内求出无权图的单源最短距离，并能复述"队列中 \(d\) 值非降且至多相差 1"这一关键引理。
3. 写出 DFS（递归与非递归），掌握发现/完成时间戳、括号定理、白色路径定理和四类边的分类。
4. 用 DFS 做拓扑排序和环检测，并掌握另一种基于入度的 Kahn 算法；用两次 DFS 求强连通分量，理解为什么第二次必须在转置图上按完成时间递减进行。
5. 把这些算法用于量化系统：因子计算管线的依赖排序与增量重算、相关性网络的冲击传播层级、可兑换资产图上的套利候选集合、金融网络中的关键节点（关节点与桥）。

读前导读

这一章在解决什么问题。 金融里到处是"谁和谁有关系"的问题：哪些股票高度相关，哪些银行之间有拆借，哪个因子要等哪个数据算完才能算，哪些货币之间可以兑换。把这些关系画出来，就是一张"图"。本章教你两件事：图在计算机里怎么存；怎么在图上系统地"走一遍"，从而回答"从这里能到哪里、最少几步、有没有绕回来的环、哪些点是牵一发动全身的关键点"。

先从零说清"图"。 这里的图不是统计图表，而是点和线：

• 顶点（vertex，也叫结点）：一个对象，比如一只股票、一家银行、一个因子、一种货币。所有顶点组成集合 \(V\)。
• 边（edge）：两个顶点之间的一条线，代表一种关系。所有边组成集合 \(E\)。整张图写作 \(G=(V,E)\)。
• 无向边与有向边：相关性是对称的（A 与 B 相关等于 B 与 A 相关），画成没有箭头的线，叫无向图；"复权价要用到原始价格"、"美元能换成欧元"有方向，画成箭头 \(u\to v\)，叫有向图。\((u,v)\) 表示从 \(u\) 到 \(v\) 的一条边。
• 邻居与度数：与 \(u\) 直接有边相连的顶点是 \(u\) 的邻居，邻居个数叫度数。银行间网络里，度数就是"与多少家银行有直接业务往来"。
• 路径与环：沿着边一步步走，经过的顶点序列叫路径，走了几条边就叫路径长度；走一圈回到起点就是环。"美元→欧元→英镑→美元"就是一个环，三角套利只可能沿着环发生。
• 连通：从 A 沿边能走到 B，就说 B 从 A 可达。
• 稀疏与稠密：5000 只股票两两之间最多约 1250 万条边；如果只连相关性很高的对，可能只有几万条，这叫稀疏图。

需要先想起来的数学。

• 矩阵与转置。 邻接矩阵就是一张 \(|V|\times|V|\) 的 0/1 表格，第 \(i\) 行第 \(j\) 列为 1 表示有边 \(i\to j\)。你熟悉的相关系数矩阵，把"大于阈值"记 1、其余记 0，就成了相关网络的邻接矩阵。转置 \(A^{\mathsf T}\) 是行列互换，对应"所有箭头反向"。见 第 00 册第 06 章 线性代数速成。
• 集合与符号。 \(|V|\) 是顶点个数；\((u,v)\in E\) 读作"边 \((u,v)\) 在边集里"；\(u\leadsto v\) 读作"从 \(u\) 有路径能到 \(v\)"；\(\iff\) 是"当且仅当"；\(\min_{u\in U}\) 是"在集合 \(U\) 中取最小"。见 第 00 册第 08 章 读懂数学证明与符号。
• 反证法与归纳法。 BFS 的正确性用反证（"假设有一个算错的，取其中最近的那个，推出矛盾"）；强连通分量的正确性用归纳。同见第 08 章。
• 复杂度 \(O(V+E)\)。 表示运算量与"顶点数 + 边数"成正比，也就是"每个点、每条线各看常数次"，这是图算法能达到的最好水平。

怎么读这一章。 22.2 必读，至少要能把一张小图画成邻接表和邻接矩阵。22.3 BFS 必读，算法本身简单，正确性证明第一次可以只看定理陈述。22.4 DFS 是本章的难点：算法和时间戳必读；括号定理、白色路径定理第一次只需理解它们在说什么，证明可以跳过；边的四分类只需记住"遇到灰色顶点 = 发现了环"。22.5 拓扑排序与量化工作最贴近（数据管线、任务调度），建议细读，Kahn 算法比 DFS 版更直观。22.6 强连通分量第一次可以只看定义、算法步骤和"套利只在同一个强连通分量里"这个用途。22.7 只看 22-2 关节点与桥的含义。22.8 实战建议先读"应用场景"和"解读"。

22.1 第 VI 部分概览与记号

原书第 VI 部分讲图算法：第 22 章是图的表示与搜索；第 23 章是最小生成树（本册第 23 章）；第 24、25 章是单源与所有结点对最短路径；第 26 章是最大流。

记号约定：图 \(G=(V,E)\) 上算法的输入规模用 \(|V|\) 和 \(|E|\) 两个参数描述。在渐近记号内部（且仅在其中），\(V\) 表示 \(|V|\)、\(E\) 表示 \(|E|\)，例如"\(O(V+E)\)"就是 \(O(|V|+|E|)\)。伪代码中用 \(G.V\)、\(G.E\) 表示顶点集和边集。

22.2 图的表示

22.2.1 邻接表

邻接表（adjacency list）是由 \(|V|\) 个链表组成的数组 \(Adj\)：对每个顶点 \(u\)，\(Adj[u]\) 包含所有满足 \((u,v)\in E\) 的顶点 \(v\)。

• 有向图所有邻接表长度之和为 \(|E|\)；无向图为 \(2|E|\)，因为边 \((u,v)\) 既出现在 \(u\) 的表里也出现在 \(v\) 的表里。
• 空间 \(\Theta(V+E)\)，适合稀疏图（\(|E|\) 远小于 \(|V|^2\)），是本书大多数算法的默认输入形式。
• 带权图把权重 \(w(u,v)\) 与 \(v\) 一起存进 \(u\) 的表。
• 缺点：判断边 \((u,v)\) 是否存在要在 \(Adj[u]\) 里查找。把每个邻接表换成散列表可以让查边期望 \(O(1)\)（原书 22.1-8）。

22.2.2 邻接矩阵

邻接矩阵（adjacency matrix）给顶点编号 \(1,\dots,|V|\)，用 \(|V|\times|V|\) 矩阵 \(A=(a_{ij})\) 表示，\(a_{ij}=1\) 当且仅当 \((i,j)\in E\)。

• 空间 \(\Theta(V^2)\)，与边数无关；适合稠密图或需要快速判断两点间有没有边的场合。
• 无向图的邻接矩阵对称，\(A=A^{\mathsf T}\)，可以只存上三角。
• 带权图存 \(a_{uv}=w(u,v)\)，无边处按问题方便存 NIL、0 或 \(\infty\)。
• 无权图每个元素只需 1 位。

原书图 22.1 给出一个 5 个顶点、7 条边的无向图（边 1-2、1-5、2-3、2-4、2-5、3-4、4-5）的两种表示；图 22.2 给出一个 6 个顶点、8 条边的有向图（1→2、1→4、2→5、3→5、3→6、4→2、5→4、6→6）的两种表示。

白话解释：用三只股票 A、B、C 举例，设只有 A–B、B–C 的相关性超过阈值。 邻接表就是一份"通讯录"：A: [B]；B: [A, C]；C: [B]。每只股票后面列出它的邻居。总共写了 4 个名字，正好是边数 2 的两倍（无向边在两头各记一次）。 邻接矩阵就是一张 3×3 的 0/1 表：A 行为 (0,1,0)，B 行为 (1,0,1)，C 行为 (0,1,0)。它关于对角线对称，因为相关性是对称的。 两者怎么选：股票池 5000 只，矩阵要 2500 万格，不管有没有边都占着；如果每只股票平均只有 20 个高相关邻居，邻接表只需记约 10 万个名字。反过来，要频繁问"A 和 B 之间有没有边"，矩阵一查就知道，通讯录得翻一遍 A 的名单。

22.2.3 几个用表示法巧解的问题

• 转置图（原书 22.1-3）：\(G^{\mathsf T}=(V,E^{\mathsf T})\)，\(E^{\mathsf T}=\{(v,u):(u,v)\in E\}\)。邻接表下扫描一遍 \(O(V+E)\)，矩阵下就是转置 \(O(V^2)\)。强连通分量算法要用到它。
• 通用汇点（原书 22.1-6）：入度 \(|V|-1\)、出度 0 的顶点。用邻接矩阵可以 \(O(V)\) 判断：从 \((1,1)\) 出发，遇到 1 就往下走（当前行的顶点不可能是汇点），遇到 0 就往右走（当前列的顶点不可能是汇点），最后只剩一个候选，再检查一次它的行和列。
• 关联矩阵（原书 22.1-7）：\(|V|\times|E|\) 的矩阵 \(B\)，有向边 \(j\) 离开 \(i\) 时 \(b_{ij}=-1\)，进入 \(i\) 时 \(b_{ij}=1\)。\(BB^{\mathsf T}\) 的对角线是各顶点的度数，非对角线是两顶点间边数的相反数——这就是图的拉普拉斯矩阵，谱聚类的出发点。

22.2.4 工程上的选择

CSR（compressed sparse row）把所有邻接表首尾相接存进一个数组，再用一个长 \(|V|+1\) 的偏移数组标出每个顶点的起止位置。它本质上就是"数组化的邻接表"，缓存友好，scipy.sparse 和大多数图计算库都用它。股票相关性网络先是一个稠密矩阵，阈值化或取 MST 后变稀疏，两种表示都会用到。

22.3 广度优先搜索

22.3.1 算法

广度优先搜索（breadth-first search, BFS）从源点 \(s\) 出发，系统地探索边，"发现"从 \(s\) 可达的每个顶点，算出 \(s\) 到每个顶点的距离（最少边数），并构造一棵以 \(s\) 为根的广度优先树。之所以叫"广度优先"，是因为它沿着已发现和未发现顶点的边界均匀地向外扩展：先发现所有距离为 \(k\) 的顶点，再发现距离为 \(k+1\) 的。

为了说明进度，原书给顶点涂三种颜色：白色表示未发现，灰色表示已发现但邻接表还没扫完（构成边界），黑色表示已扫完。黑色顶点的邻居都已被发现。区分灰黑只是为了便于理解，去掉也不影响结果（原书 22.2-3）。

from collections import deque
def BFS(G, s):
    for u in G.V - {s}:
        u.color = WHITE; u.d = float('inf'); u.pi = None
    s.color = GRAY; s.d = 0; s.pi = None
    Q = deque([s])
    while Q:                          # 不变式：Q 恰为灰色顶点的集合
        u = Q.popleft()
        for v in G.Adj[u]:
            if v.color == WHITE:      # 第一次遇到 v
                v.color = GRAY
                v.d = u.d + 1
                v.pi = u              # u 是 v 的前驱（父结点）
                Q.append(v)
        u.color = BLACK

原书图 22.3 在顶点 r, s, t, u, v, w, x, y 的无向图上从 \(s\) 运行 BFS，最终距离为：\(s=0\)；\(r=w=1\)；\(v=t=x=2\)；\(u=y=3\)。

广度优先树的形状可能依赖于邻接表中邻居的顺序，但距离 \(d\) 不依赖（原书 22.2-5）。

白话解释：BFS 就像往水里扔一块石头，波纹一圈圈往外扩。源点 \(s\) 是石头落点；第一圈是 \(s\) 的所有邻居（距离 1）；第二圈是"邻居的邻居"中还没被碰到的（距离 2）…… 代码里的几样东西：Q 是一个队列（先进先出，像银行排队叫号），保证先发现的先处理，于是近的一定比远的先处理；u.d 记距离；u.pi（\(\pi\)，读作 pi）记"我是被谁发现的"，相当于记下来路，最后顺着 pi 往回倒就能还原出一条最短路径；颜色只是记账：白=还没碰到，灰=已排上队，黑=处理完毕。 金融直觉：在相关性网络上从一只"出事"的股票做 BFS，距离 1 是直接高相关的股票，距离 2 是"相关的相关"，这给出冲击可能传导的层级。

运行时间（聚合分析）：初始化后再也不会有顶点被涂白，所以每个顶点至多入队、出队一次，队列操作共 \(O(V)\)；每个邻接表只在其顶点出队时扫描一次，总长 \(\Theta(E)\)；初始化 \(O(V)\)。总时间 \(O(V+E)\)，与邻接表的规模成线性。若输入是邻接矩阵，扫描一个顶点的邻居要 \(O(V)\)，总时间变为 \(O(V^2)\)（原书 22.2-4）。

22.3.2 BFS 求出的是最短路径

定义最短路径距离 \(\delta(s,v)\) 为从 \(s\) 到 \(v\) 的所有路径中边数的最小值，不可达时为 \(\infty\)。

• 引理 22.1　对任意边 \((u,v)\in E\)，\(\delta(s,v)\le\delta(s,u)+1\)。（先到 \(u\) 再走一步就到 \(v\)。）
• 引理 22.2（上界）　BFS 结束时对所有 \(v\)，\(v.d\ge\delta(s,v)\)。对入队次数归纳：\(v\) 被发现时 \(v.d=u.d+1\ge\delta(s,u)+1\ge\delta(s,v)\)，之后 \(v.d\) 不再改变。
• 引理 22.3（队列结构）　若队列为 \(\langle v_1,\dots,v_r\rangle\)（\(v_1\) 为队头），则 \(v_r.d\le v_1.d+1\)，且 \(v_i.d\le v_{i+1}.d\)。也就是说，队列中的 \(d\) 值非降，且至多只有两种相邻的取值。对队列操作归纳：出队只会让条件更宽松；入队 \(v\) 时正在扫描的 \(u\) 刚出队，新的队头 \(v_1\) 满足 \(v_1.d\ge u.d\)，于是 \(v.d=u.d+1\le v_1.d+1\)，且原队尾 \(v_r.d\le u.d+1=v.d\)。
• 推论 22.4　若 \(v_i\) 比 \(v_j\) 先入队，则 \(v_i.d\le v_j.d\)。

定理 22.5（BFS 的正确性）　BFS 发现从 \(s\) 可达的每个顶点，结束时对所有 \(v\) 有 \(v.d=\delta(s,v)\)；并且对可达的 \(v\ne s\)，从 \(s\) 到 \(v.\pi\) 的最短路径再接上边 \((v.\pi,v)\) 就是一条从 \(s\) 到 \(v\) 的最短路径。

证明（反证）：设 \(v\) 是 \(d\) 值错误的顶点中 \(\delta(s,v)\) 最小的一个。由引理 22.2，\(v.d>\delta(s,v)\)，且 \(v\) 可达、\(v\ne s\)。取最短路径上 \(v\) 的前一个顶点 \(u\)，则 \(\delta(s,v)=\delta(s,u)+1\)，且按 \(v\) 的选法 \(u.d=\delta(s,u)\)。于是

看 \(u\) 出队时 \(v\) 的颜色：若为白，BFS 会令 \(v.d=u.d+1\)，与 (22.1) 矛盾；若为黑，\(v\) 已先于 \(u\) 出队，由推论 22.4 \(v.d\le u.d\)，矛盾；若为灰，\(v\) 是在某个比 \(u\) 先出队的 \(w\) 出队时变灰的，\(v.d=w.d+1\le u.d+1\)，仍矛盾。

推导拆解：这是"最小反例"式的反证法，思路分三步。 第一步，假设 BFS 算错了，那么在所有算错的顶点里，挑一个真实距离最小的 \(v\)。好处是：比 \(v\) 更近的顶点都算对了，可以放心使用。 第二步，\(v\) 的真实最短路径上前一个顶点 \(u\) 离 \(s\) 更近一步，所以 \(u\) 算对了：\(u.d=\delta(s,u)=\delta(s,v)-1\)。BFS 只会高估不会低估（引理 22.2），所以 \(v\) 算错只能是 \(v.d\) 偏大，这就是式 (22.1)：\(v.d>u.d+1\)。 第三步，看 \(u\) 出队、检查邻居 \(v\) 的那一刻，\(v\) 只可能是白、灰、黑三种之一，每一种都会推出 \(v.d\le u.d+1\)，与 (22.1) 冲突。白：BFS 当场把 \(v.d\) 设为 \(u.d+1\)。黑：\(v\) 先出队，按推论 22.4 它的 \(d\) 不会更大。灰：\(v\) 是被一个更早出队的 \(w\) 发现的，\(w.d\le u.d\)。 三种情况全部矛盾，所以"存在算错的顶点"这个假设不成立。

22.3.3 广度优先树

定义前驱子图 \(G_\pi=(V_\pi,E_\pi)\)：\(V_\pi\) 是 \(\pi\) 不为 NIL 的顶点加上 \(s\)，\(E_\pi=\{(v.\pi,v):v\in V_\pi-\{s\}\}\)。BFS 得到的 \(G_\pi\) 是一棵广度优先树：包含所有可达顶点，且树中从 \(s\) 到每个 \(v\) 的唯一简单路径就是 \(G\) 中的一条最短路径（引理 22.6）。\(E_\pi\) 中的边称为树边。沿 \(\pi\) 指针递归即可打印路径，时间与路径长度成线性：

def PRINT_PATH(G, s, v):
    if v == s:
        print(s)
    elif v.pi is None:
        print("no path from", s, "to", v, "exists")
    else:
        PRINT_PATH(G, s, v.pi)
        print(v)

两个值得掌握的 BFS 应用习题：二部图判定（原书 22.2-7，摔跤手分成"好人""坏人"两派、每场比赛双方不同派）——按 BFS 层数的奇偶染色，若有边连接同色顶点则不是二部图；树的直径（原书 22.2-8）——从任意点 BFS 找到最远点 \(a\)，再从 \(a\) BFS 找到最远点 \(b\)，\(a\) 到 \(b\) 的距离就是直径。

22.4 深度优先搜索

22.4.1 算法与时间戳

深度优先搜索（depth-first search, DFS）的策略是尽可能"深"：总是从最近发现、且还有未探索出边的顶点继续走；一个顶点的边都探索完了，就回溯（backtrack）到发现它的那个顶点。从一个源点能到的都发现后，如果还有白色顶点，就选一个作为新源点继续。所以 DFS 产生的前驱子图是由若干深度优先树组成的深度优先森林。

DFS 给每个顶点打两个时间戳（timestamp）：\(v.d\) 是发现时刻（变灰），\(v.f\) 是完成时刻（邻接表扫完、变黑）。时间戳都是 1 到 \(2|V|\) 之间的整数，且

def DFS(G):
    for u in G.V:
        u.color = WHITE; u.pi = None
    global time; time = 0
    for u in G.V:
        if u.color == WHITE:
            DFS_VISIT(G, u)            # u 成为一棵新深度优先树的根

def DFS_VISIT(G, u):
    global time
    time += 1; u.d = time            # u 刚被发现
    u.color = GRAY
    for v in G.Adj[u]:               # 探索边 (u, v)
        if v.color == WHITE:
            v.pi = u
            DFS_VISIT(G, v)
    u.color = BLACK                  # u 完成
    time += 1; u.f = time

原书图 22.4 在图 22.2 那样的有向图（顶点 u, v, w, x, y, z）上运行 DFS：从 u 出发得到 u 1/8、v 2/7、y 3/6、x 4/5；再从 w 出发得到 w 9/12、z 10/11。

白话解释：BFS 是"一圈圈往外扩"，DFS 则是"一条路走到黑，走不通再退回上一个岔口换路"，像沿着股权链做穿透式尽调：先查母公司的第一家子公司，再查这家子公司的第一家孙公司……查到底了才退回来查下一家。 时间戳"1/8"的读法：\(u\) 在第 1 个时刻被发现（开始查），在第 8 个时刻完成（它名下所有能查的都查完了）。上例中 \(v\) 是 2/7、\(y\) 是 3/6、\(x\) 是 4/5：从 \(u\) 一路往下走到 \(x\)，\(x\) 最先完成，然后逐层退回。一个顶点的区间 \([d,f]\) 就是"它在调查中的那段时间"，它名下的所有后代都在这段时间里被发现并完成。 代码里 DFS_VISIT 调用自己（递归），每深入一层就"压一层栈"，退回时"弹一层"，灰色顶点恰好是此刻栈里那一串祖先。

运行时间：DFS 主循环 \(\Theta(V)\)；DFS-VISIT 对每个顶点恰好调用一次（调用时顶点必为白色并立即涂灰）；DFS-VISIT(G, v) 中的循环执行 \(|Adj[v]|\) 次，合计 \(\Theta(E)\)。总时间 \(\Theta(V+E)\)。

递归实现在顶点很多时会栈溢出（Python 默认递归深度上限约 1000），工程上要改写成显式栈的非递归版本（原书 22.3-7）。改写时要注意：为了得到正确的完成时间，栈里要保存"顶点 + 它的邻接表扫描到哪里了"，而不是简单地把所有邻居一次压栈。本章 22.8 节的代码就是这样写的。

22.4.2 括号定理与白色路径定理

把"发现 \(u\)"写成左括号"\((u\)"、"完成 \(u\)"写成右括号"\(u)\)"，DFS 的历史就是一个括号正确嵌套的表达式。原书图 22.5 的例子：\((s\,(z\,(y\,(x\ x)\ y)\,(w\ w)\ z)\ s)\ (t\,(v\ v)\,(u\ u)\ t)\)。

定理 22.7（括号定理 parenthesis theorem）　对任意两个顶点 \(u,v\)，下列三者恰有一个成立：

• 区间 \([u.d,u.f]\) 与 \([v.d,v.f]\) 完全不相交，且两者在深度优先森林中互不为后代；
• \([u.d,u.f]\) 完全包含在 \([v.d,v.f]\) 内，\(u\) 是 \(v\) 的后代；
• \([v.d,v.f]\) 完全包含在 \([u.d,u.f]\) 内，\(v\) 是 \(u\) 的后代。

证明：不妨设 \(u.d<v.d\)。若 \(v.d<u.f\)，\(v\) 是在 \(u\) 为灰色时被发现的，因而是 \(u\) 的后代；\(v\) 比 \(u\) 发现得晚，必须先完成，搜索才能回到 \(u\)，所以区间嵌套。若 \(u.f<v.d\)，由 (22.2) 两区间不相交，谁都不是在对方为灰时被发现的，互不为后代。

推论 22.8　\(v\) 是 \(u\) 的真后代当且仅当 \(u.d<v.d<v.f<u.f\)。

白话解释：把每个顶点的 \([d,f]\) 想成一笔贷款的"起息日到到期日"。括号定理说：任意两笔要么时间上完全不重叠，要么一笔完全落在另一笔里面，不会出现交错（例如 \(u\) 是 1–5、\(v\) 是 3–8 这种情况）。原因是 DFS 是栈式的：后开始的必须先结束，才能回到先开始的那个。完全包含 ⟺ 祖孙关系；不重叠 ⟺ 互不相干。"真后代"指后代但不是自己。 白色路径定理换一种说法：在开始查 \(u\) 的那一刻，凡是能从 \(u\) 出发、只经过"还没查过的"顶点走到的，最终都会被算作 \(u\) 名下的后代。这两个定理是后面证明的"计算器"，读懂陈述即可。

定理 22.9（白色路径定理 white-path theorem）　在深度优先森林中，\(v\) 是 \(u\) 的后代，当且仅当在发现 \(u\) 的时刻 \(u.d\)，存在一条从 \(u\) 到 \(v\) 的、全由白色顶点组成的路径。

证明的"⇐"方向：设有这样的白色路径，但 \(v\) 没有成为 \(u\) 的后代；不妨设路径上 \(v\) 之前的顶点都成了后代（否则换成路径上第一个非后代的顶点）。令 \(w\) 是路径上 \(v\) 的前一个顶点，它是 \(u\) 的后代，\(w.f\le u.f\)。\(v\) 必须在 \(w\) 完成前被发现（\(w\) 扫描邻接表时会看到 \(v\)），又晚于 \(u.d\)，所以 \(u.d<v.d<w.f\le u.f\)，由括号定理 \(v\) 是 \(u\) 的后代，矛盾。

白色路径定理是后面拓扑排序和强连通分量正确性证明的主要工具。

22.4.3 边的分类

DFS 把边分成四类：

1. 树边（tree edge）：深度优先森林中的边。\((u,v)\) 是树边当且仅当 \(v\) 是因探索 \((u,v)\) 而首次被发现的。
2. 后向边（back edge）：把 \(u\) 连到其祖先 \(v\) 的边。有向图中的自环也算后向边。
3. 前向边（forward edge）：把 \(u\) 连到其后代 \(v\) 的非树边。
4. 横向边（cross edge）：其他所有边——同一棵树中互不为祖先的顶点之间，或不同树之间。

DFS 在第一次探索边 \((u,v)\) 时，看 \(v\) 的颜色就能分类：

• \(v\) 为白色：树边；
• \(v\) 为灰色：后向边（灰色顶点恰好构成当前递归栈上的一条祖先链）；
• \(v\) 为黑色：\(u.d<v.d\) 时是前向边，\(u.d>v.d\) 时是横向边。

用时间戳刻画（原书 22.3-5）：树边或前向边 \(\iff u.d<v.d<v.f<u.f\)；后向边 \(\iff v.d\le u.d<u.f\le v.f\)；横向边 \(\iff v.d<v.f<u.d<u.f\)。

白话解释：四类边里最重要的是后向边，因为它意味着有环。遇到灰色顶点 \(v\)，说明 \(v\) 是当前这条调查链上的某个祖先，还没查完；现在又从它的后代 \(u\) 指回了它，等于"\(v\to\cdots\to u\to v\)"绕了一圈。在因子管线里，这就是"A 要等 B 算完，B 又要等 A 算完"的循环依赖。 其余三类只需知道含义：树边是 DFS 实际走过的路；前向边是"跳级"指向已查完的后代（例如祖父直接持有孙公司股份）；横向边连到另一支已经查完、没有祖孙关系的顶点。

定理 22.10　无向图的 DFS 中，每条边要么是树边，要么是后向边。设 \(u.d<v.d\)，\(v\) 一定在 \(u\) 为灰色期间被发现并完成。若这条边首先沿 \(u\to v\) 方向被探索，\(v\) 当时一定是白的（否则早就沿 \(v\to u\) 探索过了），是树边；若首先沿 \(v\to u\) 方向被探索，\(u\) 还是灰的，是后向边。

22.5 拓扑排序

22.5.1 定义与算法

有向无环图（directed acyclic graph, dag）的拓扑排序是所有顶点的一个线性次序，使得对每条边 \((u,v)\)，\(u\) 都排在 \(v\) 前面。可以想象成把顶点排在一条水平线上，所有边都从左指向右。有环的图不存在拓扑排序。

dag 常用来表示事件之间的先后约束。原书图 22.7 的例子是 Bumstead 教授穿衣服：内裤→裤子、裤子→鞋、裤子→腰带、衬衫→腰带、衬衫→领带、领带→夹克、腰带→夹克、袜子→鞋，手表与其他无关。DFS 的时间戳为：内裤 11/16、裤子 12/15、鞋 13/14、衬衫 1/8、领带 2/5、夹克 3/4、腰带 6/7、袜子 17/18、手表 9/10。按完成时间递减排列，得到拓扑序：袜子、内裤、裤子、鞋、手表、衬衫、腰带、领带、夹克。

def TOPOLOGICAL_SORT(G):
    # 调用 DFS(G) 计算每个顶点的完成时间 v.f；
    # 每当一个顶点完成，就把它插到链表头部
    # 返回的链表即按 v.f 递减排列
    ...

DFS \(\Theta(V+E)\)，每次插入链表头 \(O(1)\)，总时间 \(\Theta(V+E)\)。

22.5.2 正确性

引理 22.11　有向图无环，当且仅当对它做 DFS 不产生后向边。

• ⇒（逆否）：若有后向边 \((u,v)\)，\(v\) 是 \(u\) 的祖先，树中有 \(v\leadsto u\) 的路径，加上 \((u,v)\) 成环。
• ⇐（逆否）：若有环 \(c\)，令 \(v\) 是环上第一个被发现的顶点，\((u,v)\) 是环上指向 \(v\) 的边。在 \(v.d\) 时刻，环上其余顶点构成一条从 \(v\) 到 \(u\) 的白色路径，由白色路径定理 \(u\) 成为 \(v\) 的后代，\((u,v)\) 是后向边。

定理 22.12　TOPOLOGICAL-SORT 对 dag 输出拓扑排序。只需证明对任意边 \((u,v)\) 有 \(v.f<u.f\)：探索 \((u,v)\) 时 \(v\) 不可能是灰色（否则是后向边，与无环矛盾）；若 \(v\) 是白色，它成为 \(u\) 的后代，\(v.f<u.f\)；若 \(v\) 是黑色，它已经完成，而 \(u\) 还没完成，同样 \(v.f<u.f\)。

金融直觉：拓扑排序就是月结关账的工作顺序：先过账，再做调整分录，再出试算平衡表，最后出报表——每一步都排在它所依赖的步骤之后。"按完成时间递减"为什么对？完成时间越晚，说明它越是"上游"：DFS 必须先把一个顶点所有下游都查完，它自己才能完成。所以最后完成的是最上游（例如原始数据），排在最前面。 定理的证明只需检查任意一条依赖 \(u\to v\)：\(v\) 一定比 \(u\) 先完成。三种颜色里，灰色被"无环"排除；白色说明 \(v\) 会成为 \(u\) 的后代，后代先完成；黑色说明 \(v\) 早就完成了。

22.5.3 另一种方法：Kahn 算法

原书 22.4-5 给出另一种思路：反复找一个入度为 0 的顶点输出，并删去它的出边。用一个队列存当前入度为 0 的顶点，每条边只让入度减一次，总时间 \(O(V+E)\)。图中有环时，环上的顶点入度永远不会降到 0，算法结束时会剩下一批没有输出的顶点——这正好把环所在的区域指了出来。工程中的任务调度器常用这种写法，因为它天然支持"并行执行同一批入度为 0 的任务"。

拓扑序上的动态规划很常用。例如统计 dag 中从 \(s\) 到 \(t\) 的路径数（原书 22.4-2）：按拓扑序，\(\mathrm{paths}(v)=\sum_{(u,v)\in E}\mathrm{paths}(u)\)。原书图 22.8 中从 p 到 v 恰有 4 条路径：pov、poryv、posryv、psryv。

22.6 强连通分量

22.6.1 定义

有向图的强连通分量（strongly connected component, SCC）是一个极大的顶点集合 \(C\)，使得 \(C\) 中任意两个顶点 \(u,v\) 互相可达（\(u\leadsto v\) 且 \(v\leadsto u\)）。许多有向图算法先把图分解成强连通分量，在每个分量上分别求解，再按分量之间的连接关系组合结果。

白话解释：有向图里"A 能到 B"不等于"B 能到 A"。强连通分量是一群"彼此之间来回都走得通"的顶点。货币兑换的例子：美元、欧元、英镑可以互相换来换去，是一个强连通分量；某种只能买入、不能卖回的资产，只能单独成一个分量。把每个分量缩成一个点之后，分量之间的箭头不可能形成环（引理 22.13），整张图变成一张"上下游"清晰的依赖图。

分量图（component graph）\(G^{SCC}\) 把每个强连通分量收缩成一个顶点，分量之间有边当且仅当原图中有一条边从一个分量指向另一个。原书图 22.9：顶点 a–h 的有向图，强连通分量为 {a,b,e}、{c,d}、{f,g}、{h}。

引理 22.13　分量图是 dag。若分量 \(C\) 中有路径到达 \(C'\)，就不可能有路径从 \(C'\) 回到 \(C\)，否则两者应当合并成一个分量。

22.6.2 算法：两次 DFS

转置图 \(G^{\mathsf T}\) 把所有边反向，它与 \(G\) 的强连通分量完全相同（互相可达的关系在反向后不变）。

def STRONGLY_CONNECTED_COMPONENTS(G):
    DFS(G)                       # 1. 求每个顶点的完成时间 u.f
    GT = transpose(G)            # 2. O(V+E)
    # 3. 在 GT 上 DFS，主循环按 u.f 递减的顺序考察顶点
    # 4. 第 3 步得到的每棵深度优先树就是一个强连通分量

这个算法归功于 Kosaraju 与 Sharir，总时间 \(\Theta(V+E)\)。

22.6.3 为什么正确

把顶点集合 \(U\) 的发现时间和完成时间推广为 \(d(U)=\min_{u\in U}u.d\)、\(f(U)=\max_{u\in U}u.f\)（都指第一次 DFS 的时间戳）。

引理 22.14　设 \(C,C'\) 是不同的强连通分量，若存在边 \((u,v)\)，\(u\in C\)、\(v\in C'\)，则 \(f(C)>f(C')\)。

证明分两种情况。若 \(d(C)<d(C')\)：令 \(x\) 是 \(C\) 中第一个被发现的顶点，此刻 \(C\cup C'\) 全白，从 \(x\) 到它们都有白色路径，所以它们都成为 \(x\) 的后代，\(x.f=f(C)>f(C')\)。若 \(d(C)>d(C')\)：令 \(y\) 是 \(C'\) 中第一个被发现的顶点，\(C'\) 全部成为 \(y\) 的后代，\(y.f=f(C')\)；由引理 22.13，从 \(C'\) 到不了 \(C\)，所以 \(y\) 完成时 \(C\) 仍全白，之后才会被发现，\(f(C)>f(C')\)。

推论 22.15　在 \(G^{\mathsf T}\) 中，若有边从 \(C\) 指向 \(C'\)，则 \(f(C)<f(C')\)。也就是说，转置图中跨分量的边总是从完成较早的分量指向完成较晚的分量。

于是第二次 DFS 的过程是这样的：它从 \(f\) 最大的分量 \(C\) 中某个顶点出发，在 \(G^{\mathsf T}\) 中，\(C\) 没有指向其他未访问分量的边（那些分量的 \(f\) 都更小），所以这棵树恰好是 \(C\)；接着从剩下的分量中 \(f\) 最大的那个出发，它在 \(G^{\mathsf T}\) 中指出去的边只能通向已访问的分量……每棵树都恰好是一个强连通分量（定理 22.16，对树的个数归纳）。

白话解释：为什么要"先正向 DFS、再在反向图上按完成时间从大到小 DFS"？ 把分量想成上下游。第一次 DFS 之后，完成最晚的分量一定是最上游的（引理 22.14：有边从 \(C\) 指向 \(C'\)，则 \(C\) 完成更晚）。 如果第二次直接在原图上从最上游出发，会顺着箭头一路漏到下游，把好几个分量混成一棵树。把箭头全部反向之后，最上游的分量变成了"没有出口"的那个：从它出发，走得到的只有它自己。于是第二次 DFS 每次都从"剩下的里面最上游"的分量开始，每次正好圈出一个分量，然后把它从考虑中划掉，再处理下一个。 一句话：反向图 + 从最上游开始，等于每次都从"出不去的角落"开始搜，搜到的就是一整个分量，不多不少。

换个角度看，第二次 DFS 是按拓扑序访问 \(G^{SCC}\) 的顶点。原书 22.5-3 问：能不能省掉转置，第二次 DFS 在原图上按完成时间递增进行？答案是不行，可以构造反例。

22.7 思考题选讲

• 22-1 用 BFS 给边分类：无向图的 BFS 中没有后向边和前向边，树边满足 \(v.d=u.d+1\)，横向边满足 \(v.d=u.d\) 或 \(u.d+1\)；有向图的 BFS 中没有前向边，横向边满足 \(v.d\le u.d+1\)，后向边满足 \(0\le v.d\le u.d\)。
• 22-2 关节点、桥与双连通分量：连通无向图中，关节点（articulation point）是删去后图不再连通的顶点；桥（bridge）是删去后图不再连通的边；双连通分量（biconnected component）是极大的边集，其中任意两条边都在同一个简单环上。设 \(G_\pi\) 为 DFS 树：(a) 根是关节点当且仅当它在 \(G_\pi\) 中至少有两个孩子；(b) 非根顶点 \(v\) 是关节点，当且仅当 \(v\) 有某个孩子 \(s\)，使 \(s\) 及其后代都没有指向 \(v\) 的真祖先的后向边。定义
  \[v.low=\min\big(v.d,\ \{w.d:(u,w)\text{ 是 }v\text{ 的某个后代 }u\text{ 的后向边}\}\big),\]
  可以在 DFS 中 \(O(E)\) 算出。于是：非根 \(v\) 是关节点 \(\iff\) 存在孩子 \(s\) 使 \(s.low\ge v.d\)；树边 \((v,s)\) 是桥 \(\iff s.low>v.d\)（等价于它不在任何简单环上）。这就是 Tarjan 的 low-link 方法，一次 DFS 就能求出全部关节点和桥。
• 22-3 欧拉回路：强连通有向图存在经过每条边恰一次的回路，当且仅当每个顶点的入度等于出度；可以 \(O(E)\) 构造（把边不相交的环拼接起来）。
• 22-4 可达性：每个顶点有唯一标号 \(L(u)\)，求每个顶点能到达的顶点中标号最小者。做法是在转置图上按标号从小到大做搜索，每次只标记还没标记的顶点，\(O(V+E)\)。

22.8 量化实战

22.8.1 应用场景

因子计算管线与任务调度。 因子研究的数据管线天然是一个 dag：原始价格和公司行为数据生成复权价，复权价生成收益率和均线，收益率生成波动率和动量，若干因子合成综合因子，最后得到组合权重。Airflow、Dagster 这类调度器做的事情，本质上就是本章的拓扑排序：按拓扑序执行任务，同一批入度为 0 的任务可以并行。还有两个直接的用途：

• 增量重算：某个上游数据被修正（比如补录了一次拆股），只需重算它的所有下游。从被修改的节点做一次 BFS/DFS 得到受影响的集合，再按拓扑序执行即可。
• 循环依赖检测：配置错误导致"组合权重又被用来算波动率"之类的循环，在 DFS 中表现为后向边，在 Kahn 算法中表现为剩余的无法输出的顶点。上线前跑一遍检测，能避免任务永远等不到上游。

相关性网络与冲击传播。 把相关系数超过阈值的股票对连边，得到无权的相关性网络。从一只受冲击的股票做 BFS，距离为 1 的是直接高相关的股票，距离为 2 的是"相关的相关"，依此类推。BFS 层级可以作为冲击传播层次的粗略刻画；不可达的股票说明在这个阈值下与冲击源处于不同的板块。连通分量（用 BFS/DFS 或上一章的并查集）给出阈值下的分组。

可兑换资产图与套利候选。 把货币或数字资产当顶点，"可以从 A 换到 B"当有向边。只有处于同一个强连通分量里的资产之间才能循环兑换，所以三角套利环只可能出现在同一个强连通分量内部。先做 SCC 分解，可以把套利搜索限制在小得多的子图上。真正判断是否存在套利，需要以 \(-\ln(\text{汇率})\) 为边权、检测负权环，那是 Bellman–Ford 算法的工作，见本册最短路径一章（原书第 24 章）。

金融网络中的关键节点。 在银行间拆借、担保、供应链这类网络中，关节点是"删掉它，网络就裂成几块"的机构，桥是"唯一连接两个群体的业务关系"。它们是风险传导的瓶颈，也是监管和压力测试关注的对象。思考题 22-2 的 low-link 方法一次 DFS 就能全部找出来。

22.8.2 代码

下面的代码全部用 Python 字典表示邻接表，实现了 BFS、带时间戳和边分类的非递归 DFS、Kahn 算法、Kosaraju 强连通分量和 Tarjan 关节点/桥算法，并分别与 scipy 或暴力方法对照：

1. 一个 12 个节点的因子管线 dag：DFS 拓扑排序、增量重算集合、人为加入循环依赖后的检测；
2. 60 只股票（6 个行业、2 个板块）的阈值相关网络：BFS 层级、与 scipy.sparse.csgraph.shortest_path 对照；
3. 一个可兑换资产图的强连通分量，与 scipy 对照；
4. 两个银行群通过少数机构相连的网络：关节点与桥，与"逐个删点看是否断开"的暴力结果对照。

import numpy as np
from collections import deque
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components, shortest_path

# ======== 通用工具：邻接表用 dict[顶点] -> list[邻居] ========
def bfs(adj, s):
    d, pi = {s: 0}, {s: None}
    Q = deque([s])
    while Q:
        u = Q.popleft()
        for v in adj[u]:
            if v not in d:                       # 白色顶点
                d[v] = d[u] + 1; pi[v] = u; Q.append(v)
    return d, pi

def dfs(adj, order=None):
    """非递归 DFS，返回发现/完成时间、前驱和边分类（有向图）。"""
    color = {u: "W" for u in adj}; d, f, pi, kind = {}, {}, {}, {}
    time = 0
    for s in (order or adj):
        if color[s] != "W": continue
        pi[s] = None; time += 1; d[s] = time; color[s] = "G"
        stack = [(s, iter(adj[s]))]
        while stack:
            u, it = stack[-1]
            for v in it:
                if color[v] == "W":
                    kind[(u, v)] = "树边"; pi[v] = u
                    time += 1; d[v] = time; color[v] = "G"
                    stack.append((v, iter(adj[v]))); break
                elif color[v] == "G": kind[(u, v)] = "后向边"
                else: kind[(u, v)] = "前向边" if d[u] < d[v] else "横向边"
            else:                                 # u 的邻接表扫完：完成
                stack.pop(); color[u] = "B"; time += 1; f[u] = time
    return d, f, pi, kind

# ======== 1. 拓扑排序：因子计算管线 ========
pipeline = {
    "raw_price": ["adj_price"], "corp_action": ["adj_price"],
    "adj_price": ["ret_1d", "ma_20"], "ret_1d": ["vol_20", "momentum_60"],
    "ma_20": ["trend"], "vol_20": ["risk_parity_w", "low_vol"],
    "momentum_60": ["composite"], "low_vol": ["composite"], "trend": ["composite"],
    "composite": ["portfolio"], "risk_parity_w": ["portfolio"], "portfolio": [],
}
d, f, pi, kind = dfs(pipeline)
topo = sorted(pipeline, key=lambda u: -f[u])          # 按完成时间递减
print("DFS 拓扑序:", " -> ".join(topo))
print("存在后向边(有环)?", any(k == "后向边" for k in kind.values()))

def kahn(adj):
    indeg = {u: 0 for u in adj}
    for u in adj:
        for v in adj[u]: indeg[v] += 1
    Q = deque(u for u in adj if indeg[u] == 0); out = []
    while Q:
        u = Q.popleft(); out.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0: Q.append(v)
    return out, [u for u in adj if indeg[u] > 0]       # 第二项非空说明有环

# 只重算受影响的下游：从被修改的节点 BFS，再按拓扑序排列
for changed in ["ma_20", "corp_action"]:
    dirty, _ = bfs(pipeline, changed)
    print(f"{changed} 变更后需按序重算:", [u for u in topo if u in dirty])

bad = {k: list(v) for k, v in pipeline.items()}
bad["portfolio"] = ["vol_20"]                           # 误配置：组合权重反过来影响波动率
order, stuck = kahn(bad)
print("加入循环依赖后 Kahn 算法卡住的节点:", sorted(stuck))
_, _, _, kind_bad = dfs(bad)
print("DFS 找到的后向边:", [e for e, k in kind_bad.items() if k == "后向边"])

# ======== 2. 相关性网络上的 BFS：冲击传播层级 ========
rng = np.random.default_rng(22)
N, T, K = 60, 750, 6                                    # 60 只股票、6 个行业、2 个板块
lab = np.repeat(np.arange(K), N//K)
sec = np.array([0, 0, 0, 1, 1, 1])                      # 行业 -> 板块
S = rng.normal(0, 1, (T, 2))
F = 0.7*S[:, sec] + 0.7*rng.normal(0, 1, (T, K))        # 行业因子受板块因子驱动
R = 0.5*rng.normal(0, 1, (T, 1)) + 0.8*F[:, lab] + rng.normal(0, 1, (T, N))
C = np.corrcoef(R.T)
A = (C > 0.35) & ~np.eye(N, dtype=bool)                 # 阈值化的无权相关网络
adj = {i: list(np.flatnonzero(A[i])) for i in range(N)}
src = 0
dist, _ = bfs(adj, src)
layers = {}
for v, k in dist.items(): layers.setdefault(k, []).append(v)
print(f"从股票 {src} 出发的 BFS 层级规模:", {k: len(v) for k, v in sorted(layers.items())})
sp = shortest_path(csr_matrix(A.astype(float)), unweighted=True, indices=src)
ok = all(sp[v] == dist.get(v, np.inf) for v in range(N))
print("与 scipy 无权最短路一致:", ok, "| 不可达股票数:", int(np.isinf(sp).sum()))
print("无向连通分量数:", connected_components(csr_matrix(A), directed=False)[0])

# ======== 3. 强连通分量：可兑换资产图 ========
edges = [("USD","EUR"),("EUR","USD"),("EUR","GBP"),("GBP","USD"),
         ("USD","JPY"),("JPY","USD"),("USD","USDT"),("USDT","BTC"),
         ("BTC","USDT"),("BTC","ETH"),("ETH","BTC"),("ETH","STK"),   # STK: 只能买入不能换回
         ("CNY","USD")]                                               # CNY: 只能换出
nodes = sorted({x for e in edges for x in e}); id_ = {s: i for i, s in enumerate(nodes)}
G = {u: [] for u in nodes}
for u, v in edges: G[u].append(v)

def kosaraju(G):
    _, f, _, _ = dfs(G)
    GT = {u: [] for u in G}
    for u in G:
        for v in G[u]: GT[v].append(u)
    order = sorted(G, key=lambda u: -f[u])
    _, _, pi, _ = dfs(GT, order)
    root = {}
    for u in order:                                     # 沿前驱找每个顶点所在树的根
        r = u
        while pi[r] is not None: r = pi[r]
        root[u] = r
    comps = {}
    for u in G: comps.setdefault(root[u], []).append(u)
    return [sorted(c) for c in comps.values()]

sccs = kosaraju(G)
print("强连通分量:", sorted(sccs, key=len, reverse=True))
M = csr_matrix((np.ones(len(edges)), ([id_[u] for u,_ in edges], [id_[v] for _,v in edges])),
               shape=(len(nodes),)*2)
print("scipy 强连通分量个数:", connected_components(M, directed=True, connection="strong")[0])

# ======== 4. 关节点与桥（思考题 22-2）：无向网络的脆弱节点 ========
def articulation_and_bridges(adj):
    disc, low, parent = {}, {}, {}
    aps, bridges, t = set(), [], 0
    for s in adj:
        if s in disc: continue
        parent[s] = None; t += 1; disc[s] = low[s] = t
        stack = [(s, iter(adj[s]))]; children = {s: 0}
        while stack:
            u, it = stack[-1]
            for v in it:
                if v not in disc:
                    parent[v] = u; children[u] += 1; children[v] = 0
                    t += 1; disc[v] = low[v] = t
                    stack.append((v, iter(adj[v]))); break
                elif v != parent[u]:
                    low[u] = min(low[u], disc[v])          # 后向边
            else:
                stack.pop()
                p = parent[u]
                if p is not None:
                    low[p] = min(low[p], low[u])
                    if low[u] > disc[p]: bridges.append((p, u))
                    if parent[p] is not None and low[u] >= disc[p]: aps.add(p)
        if children[s] >= 2: aps.add(s)
    return aps, bridges

# 两个紧密的"银行群"通过少数机构相连
net = {i: set() for i in range(12)}
def link(a, b): net[a].add(b); net[b].add(a)
for grp in [range(0, 5), range(6, 11)]:
    g = list(grp)
    for i in g:
        for j in g:
            if i < j and rng.random() < 0.7: link(i, j)
    for i in range(len(g)-1): link(g[i], g[i+1])           # 保证群内连通
link(4, 5); link(5, 6); link(10, 11)
aps, br = articulation_and_bridges({k: sorted(v) for k, v in net.items()})

def n_comp_without(x):
    sub = {u: [v for v in net[u] if v != x] for u in net if u != x}
    seen, cnt = set(), 0
    for s in sub:
        if s in seen: continue
        cnt += 1; seen |= set(bfs(sub, s)[0])
    return cnt
brute = {x for x in net if n_comp_without(x) > 1}
print("关节点:", sorted(aps), "| 暴力删点验证:", sorted(brute))
print("桥:", br)

运行输出：

DFS 拓扑序: corp_action -> raw_price -> adj_price -> ma_20 -> trend -> ret_1d -> momentum_60 -> vol_20 -> low_vol -> composite -> risk_parity_w -> portfolio
存在后向边(有环)? False
ma_20 变更后需按序重算: ['ma_20', 'trend', 'composite', 'portfolio']
corp_action 变更后需按序重算: ['corp_action', 'adj_price', 'ma_20', 'trend', 'ret_1d', 'momentum_60', 'vol_20', 'low_vol', 'composite', 'risk_parity_w', 'portfolio']
加入循环依赖后 Kahn 算法卡住的节点: ['composite', 'low_vol', 'portfolio', 'risk_parity_w', 'vol_20']
DFS 找到的后向边: [('portfolio', 'vol_20')]
从股票 0 出发的 BFS 层级规模: {0: 1, 1: 9, 2: 3, 3: 17}
与 scipy 无权最短路一致: True | 不可达股票数: 30
无向连通分量数: 2
强连通分量: [['EUR', 'GBP', 'JPY', 'USD'], ['BTC', 'ETH', 'USDT'], ['CNY'], ['STK']]
scipy 强连通分量个数: 4
关节点: [4, 5, 6, 10] | 暴力删点验证: [4, 5, 6, 10]
桥: [(10, 11), (5, 6), (4, 5)]

解读：

• 管线：DFS 按完成时间递减给出的顺序满足所有依赖。ma_20 变更后只需重算 4 个节点；corp_action（公司行为，如拆股分红）变更后几乎全部下游都要重算，但 raw_price 不受影响。加入 portfolio → vol_20 这条错误依赖后，Kahn 算法输出不了环上及其下游的 5 个节点，DFS 则精确指出了造成环的那条后向边。
• 相关网络：阈值 0.35 下全网分成 2 个连通分量，正好对应模拟中的 2 个板块。从股票 0 出发，1 跳可达 9 只（大多是同行业），2 跳 3 只，3 跳 17 只（同板块的其他行业），另一板块的 30 只不可达。BFS 距离与 scipy 的无权最短路完全一致。
• SCC：法币 {USD, EUR, GBP, JPY} 是一个分量，{USDT, BTC, ETH} 是另一个（这个图里 USD 能换成 USDT，但 USDT 换不回 USD），只能买入的 STK 和只能换出的 CNY 各自单独成分量。三角套利只需在前两个分量内部搜索。
• 关节点与桥：机构 4、5、6 构成两个银行群之间唯一的通道，10 是外围机构 11 的唯一联系人；(4,5)、(5,6)、(10,11) 是桥。low-link 算法的结果与暴力删点完全一致，但只需要一次 \(O(V+E)\) 的 DFS，而暴力法要 \(O(V(V+E))\)。

本章小结

图有两种标准表示：邻接表 \(\Theta(V+E)\) 空间，适合稀疏图；邻接矩阵 \(\Theta(V^2)\) 空间，适合稠密图和快速查边。BFS 用 FIFO 队列逐层扩展，\(O(V+E)\) 时间求出无权图的单源最短距离，正确性依赖"队列中 \(d\) 值非降且至多相差 1"。DFS 用递归或栈尽量深入，\(\Theta(V+E)\) 时间产生发现/完成时间戳；括号定理和白色路径定理刻画了时间戳与祖先关系，边按探索时另一端的颜色分成树边、后向边、前向边、横向边，无向图只有前两种。由此得到：有向图无环当且仅当 DFS 没有后向边；拓扑排序就是按完成时间递减输出；强连通分量用两次 DFS 求出——先在 \(G\) 上求完成时间，再在 \(G^{\mathsf T}\) 上按完成时间递减搜索，每棵树是一个分量。在量化系统中，这些算法分别用于管线调度与增量重算、相关性网络分析、套利候选筛选和风险传导关键节点识别。

练习

基础

1. 给定邻接表，在 \(O(V+E)\) 时间内计算每个顶点的出度和入度。（原书 22.1-1。）
2. 用邻接矩阵在 \(O(V)\) 时间内判断有向图是否有通用汇点。（原书 22.1-6。提示：见 22.2.3。）
3. 用 BFS 判断一个无向图是否为二部图，并给出两部分的划分，要求 \(O(V+E)\)。（原书 22.2-7。）
4. 写出用显式栈实现、能正确给出发现和完成时间的非递归 DFS。（原书 22.3-7。）
5. 证明：在有向图中，探索边 \((u,v)\) 时若 \(v\) 是黑色，则 \(u.d<v.d\) 时它是前向边、\(u.d>v.d\) 时它是横向边。（原书 22.3-5。）

进阶

6. 给出一个线性时间算法，统计 dag 中从 \(s\) 到 \(t\) 的简单路径条数。（原书 22.4-2。提示：拓扑序上的动态规划。）
7. 给出一个 \(O(V)\) 时间（与 \(|E|\) 无关）的算法，判断无向图是否含有简单环。（原书 22.4-3。提示：无环的无向图至多 \(|V|-1\) 条边，DFS 最多看 \(|V|\) 条边就会发现后向边。）
8. 说明为什么不能把强连通分量算法的第二次 DFS 改为"在原图上按完成时间递增"进行，构造反例。（原书 22.5-3。）
9. 在 \(O(V+E)\) 时间内求出分量图 \(G^{SCC}\)，且不含重边。（原书 22.5-5。）然后用它判断一个有向图是否"半连通"（任意两点至少单向可达）。（原书 22.5-7。提示：分量图的拓扑序中相邻分量之间都要有边。）
10. 修改 22.8.2 的关节点代码，使它同时输出每条边所属的双连通分量编号（思考题 22-2(h)）。把它用在一个模拟的银行间拆借网络上，并讨论：关节点与"度数最高的节点"有何不同？哪一个更能说明系统性风险的传导瓶颈？

原书推荐习题：22.1-3、22.1-6、22.2-7、22.2-8、22.3-5、22.3-7、22.3-12、22.4-2、22.4-5、22.5-3、22.5-5，思考题 22-2、22-3。

原书对照