7.3 DAG、强连通分量与网络流：从依赖排序到资源分配
构建系统要排序依赖，模块分析要收拢循环引用，调度器要把任务分给机器。这些问题都用图，却需要不同结构：DAG、强连通分量、流网络和二分图。
DAG 与拓扑序
有向无环图（DAG）没有有向环。拓扑序是顶点的线性排列，使每条边 u→v 都满足 u 位于 v 之前。
拓扑序存在，当且仅当有限有向图是 DAG。
Kahn 算法
计算每个顶点入度
把所有入度 0 的顶点入队
while 队列非空:
取出 v，追加到结果
对每条 v→u:
indegree[u]--
若变成 0，则 u 入队若最终输出少于 |V| 个顶点，剩余部分包含环。
剩余顶点不一定都在环上。例如 A↔B 且 B→C，三者都会留下，但 C 只是被上游环阻塞。要报告具体循环成员，应进一步求 SCC 或提取回边形成的环。
多个入度 0 顶点意味着拓扑序可能不唯一。队列、堆或稳定排序策略会影响具体结果；可重复构建若依赖固定顺序，应显式规定 tie-breaker。
DFS 方法
在 DFS 退出顶点时压入序列，最后反转可得到 DAG 的拓扑序。必须同时检测回边；有环图的退出逆序不是合法拓扑序。
依赖边方向要先约定
“A 依赖 B”可以建成：
A→B // 从依赖者指向依赖也可以建成：
B→A // 从前置项指向后续项若要让拓扑序直接给出构建顺序，通常使用 B→A。算法没有理解业务语句，方向选反会得到逆序但仍看似合法。
强连通分量压缩循环
有向图中，若 u 可达 v 且 v 可达 u，二者属于同一强连通分量（SCC）；这里可达包含零长度路径，所以孤立顶点也属于自己的 SCC。互相可达是等价关系，因此 SCC 将顶点划分成块。
把每个 SCC 压成一个超级顶点，并丢弃分量内部的边，得到的凝聚图一定是 DAG。若凝聚图有环，对应分量本应合并成更大的 SCC，矛盾。
应用：
- 把循环模块报告成一个整体；
- 分析状态机中的互达区域；
- 在组件级 DAG 上排序；
- 找出网页图的强连通核心。
Kosaraju 用两次 DFS；Tarjan 用一次 DFS 配合 low-link 和栈。二者在邻接表上都可达到 O(V+E)，实现复杂度和常数不同。
流网络
流网络包含：
- 源点
s； - 与源点不同的汇点
t； - 每条有向边容量
c(u,v)≥0； - 流量
f(u,v)。
约束：
0≤f(u,v)≤c(u,v)除源、汇外，流量守恒：
Σ 入流 = Σ 出流流值定义为源点净流出量“出流减入流”，由守恒也等于汇点净流入量。常见示例没有进入源点或离开汇点的边，此时才可直接说源点出流总和。最大流要在容量与守恒约束下最大化这个净值。
残量网络与增广路
已发送一部分流后，残量网络表示还能怎样调整：
- 正向残量：尚未使用的容量；
- 反向残量：允许撤销先前流量。
找到 s→t 增广路，按路径最小残量增加流；反向边使算法能纠正早期选择。
Ford–Fulkerson 是方法框架，终止和复杂度与选路及容量类型有关。Edmonds–Karp 每次用 BFS 选最短增广路，给出 O(VE²) 的多项式界。更大实例常用 Dinic 或 push-relabel 等算法。
最大流最小割
一个 s-t 割把顶点分成：
s∈S, t∈T, S∪T=V, S∩T=∅割容量是从 S 指向 T 的边容量和。任何流都不能超过任一割容量。
最大流最小割定理：
最大流值 = 最小割容量它既给出算法最优性证书，也揭示瓶颈边集合。网络吞吐分析中，最小割是模型里的容量瓶颈；现实系统还可能受延迟、共享资源和时变容量影响。
下面的 Python 3 示例直接给出一个可行流，再枚举这个小网络的全部 4 个割。容量均为整数，恰好存在流值与割容量都为 3 的证书，因此无需靠目测判断最优：
from itertools import product
capacity = {("s", "a"): 2, ("s", "b"): 1, ("a", "b"): 1,
("a", "t"): 1, ("b", "t"): 2}
flow = dict(capacity) # This small network permits saturating every edge.
for v in ("a", "b"):
assert sum(f for (u, w), f in flow.items() if w == v) == sum(
f for (u, w), f in flow.items() if u == v)
assert all(0 <= flow[e] <= capacity[e] for e in capacity)
value = sum(f for (u, v), f in flow.items() if u == "s")
cuts = []
for bits in product((False, True), repeat=2):
side = {"s"} | {v for v, selected in zip(("a", "b"), bits) if selected}
cuts.append(sum(c for (u, v), c in capacity.items() if u in side and v not in side))
print(value, min(cuts)) # 3 3这段代码是在验证给定解，没有实现通用最大流求解器。割的子集枚举随内部顶点数指数增长，大图应使用最大流算法并从最终残量可达集提取割。
二分图匹配
二分图顶点分为 L、R，边只跨两侧。匹配是一组没有共享端点的边。
任务：机器分配：
L：任务
R：机器
边：机器能执行该任务可转成流网络：
s→每个任务，容量 1
任务→兼容机器，容量 1
每个机器→t，容量 1整数容量下最大流存在整数解，流量 1 的任务：机器边形成最大匹配。
下面直接对二分图做 Python 3 增广搜索。左右两侧身份分开，每个任务和机器容量均为 1；输入是有限静态兼容列表：
def maximum_matching(neighbors):
owner = {} # machine -> task
def augment(task, seen):
for machine in neighbors[task]:
if machine in seen:
continue
seen.add(machine)
if machine not in owner or augment(owner[machine], seen):
owner[machine] = task
return True
return False
for task in neighbors:
augment(task, set())
return {task: machine for machine, task in owner.items()}
neighbors = {"A": ["m1", "m2"], "B": ["m1"]}
print(sorted(maximum_matching(neighbors).items())) # [('A', 'm2'), ('B', 'm1')]
print(len(maximum_matching({"A": ["m1"], "B": ["m1"]}))) # 1开始可能把 A 分给 m1，B 随后要求 m1 时，递归会把 A 移到 m2，释放 m1 给 B。这就是反向调整的作用。每次成功增广增加一个匹配，且没有增广路的匹配已最大；若另有更大匹配，两者的对称差会给出一条增广路。这个简洁实现的时间为 O(|L||E|+|L|)，深递归仍受调用栈限制。
若机器可接多个任务，调整机器到汇点的容量；若任务和机器有偏好权重，则变成加权匹配或最小费用流问题，普通最大流不再表达目标。
Hopcroft–Karp 可在二分图上以 O(E√V) 求最大匹配。是否值得使用取决于规模和实现环境。
Hall 定理给出覆盖左侧的条件
二分图 G=(L,R,E) 存在覆盖 L 中所有顶点的匹配，当且仅当对任意 S⊆L：
|N(S)|≥|S|N(S) 是 S 在右侧的全部邻居。直觉是任意一组任务都必须合计拥有至少同样多的候选机器，否则抽屉容量不足。
例如两个任务都只能使用 m1，取 S={A,B} 就有 |N(S)|=1<2，无法全部分配。覆盖 L 的匹配只有在两侧大小相同的情况下才同时覆盖 R，成为整个二分图的完美匹配。
直接检查所有子集需要指数次检查，大规模时不可行，但最大匹配算法会以更有效方式判断并给出匹配或暴露缺口。
图模型的失真来源
- 把动态容量当成静态常数；
- 用单边表示实际需要双向握手的协议；
- 忽略一台机器的多个共享资源维度；
- 把可并行任务误建成全序；
- 用最大流优化吞吐，却忽略延迟和公平性；
- 匹配只看兼容性，未编码成本、配额和亲和性。
算法解决的是给定图问题。模型审查与算法正确性同样重要。
完成检查
- 为一个含循环依赖的模块图求 SCC 和凝聚 DAG；
- 用 Kahn 算法给出两个可能的拓扑序；
- 构造一个小流网络，手工找最大流和最小割；
- 把三项任务、三台机器的兼容关系转成流网络；
- 用 Hall 条件解释一个不存在完美匹配的例子；
- 为加权任务分配说明普通最大流遗漏了什么。