7.3 DAG、强连通分量与网络流：从依赖排序到资源分配
构建系统要排序依赖，模块分析要收拢循环引用，调度器要把任务分给机器。这些问题都用图，却需要不同结构：DAG、强连通分量、流网络和二分图。
DAG 与拓扑序
有向无环图（DAG）没有有向环。拓扑序是顶点的线性排列，使每条边 u→v 都满足 u 位于 v 之前。
拓扑序存在，当且仅当有限有向图是 DAG。
Kahn 算法
计算每个顶点入度
把所有入度 0 的顶点入队
while 队列非空:
取出 v，追加到结果
对每条 v→u:
indegree[u]--
若变成 0，则 u 入队若最终输出少于 |V| 个顶点，剩余部分包含环。
多个入度 0 顶点意味着拓扑序可能不唯一。队列、堆或稳定排序策略会影响具体结果；可重复构建若依赖固定顺序，应显式规定 tie-breaker。
DFS 方法
在 DFS 退出顶点时压入序列，最后反转可得到 DAG 的拓扑序。必须同时检测回边；有环图的退出逆序不是合法拓扑序。
依赖边方向要先约定
“A 依赖 B”可以建成：
A→B // 从依赖者指向依赖也可以建成：
B→A // 从前置项指向后续项若要让拓扑序直接给出构建顺序，通常使用 B→A。算法没有理解业务语句，方向选反会得到逆序但仍看似合法。
强连通分量压缩循环
有向图中，若 u 可达 v 且 v 可达 u，二者属于同一强连通分量（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 的边容量和。任何流都不能超过任一割容量。
最大流最小割定理：
最大流值 = 最小割容量它既给出算法最优性证书，也揭示瓶颈边集合。网络吞吐分析中，最小割是模型里的容量瓶颈；现实系统还可能受延迟、共享资源和时变容量影响。
二分图匹配
二分图顶点分为 L、R，边只跨两侧。匹配是一组没有共享端点的边。
任务—机器分配：
L：任务
R：机器
边：机器能执行该任务可转成流网络：
s→每个任务，容量 1
任务→兼容机器，容量 1
每个机器→t，容量 1整数容量下最大流存在整数解，流量 1 的任务—机器边形成最大匹配。
若机器可接多个任务，调整机器到汇点的容量；若任务和机器有偏好权重，则变成加权匹配或最小费用流问题，普通最大流不再表达目标。
Hopcroft–Karp 可在二分图上以 O(E√V) 求最大匹配。是否值得使用取决于规模和实现环境。
Hall 定理给出完美匹配条件
二分图 G=(L,R,E) 存在覆盖 L 中所有顶点的匹配，当且仅当对任意 S⊆L：
|N(S)|≥|S|N(S) 是 S 在右侧的全部邻居。直觉是任意一组任务都必须合计拥有至少同样多的候选机器，否则抽屉容量不足。
直接检查所有子集不可行，但最大匹配算法会以更有效方式判断并给出匹配或暴露缺口。
图模型的失真来源
- 把动态容量当成静态常数；
- 用单边表示实际需要双向握手的协议；
- 忽略一台机器的多个共享资源维度；
- 把可并行任务误建成全序；
- 用最大流优化吞吐，却忽略延迟和公平性；
- 匹配只看兼容性，未编码成本、配额和亲和性。
算法解决的是给定图问题。模型审查与算法正确性同样重要。
完成检查
- 为一个含循环依赖的模块图求 SCC 和凝聚 DAG；
- 用 Kahn 算法给出两个可能的拓扑序；
- 构造一个小流网络，手工找最大流和最小割；
- 把三项任务、三台机器的兼容关系转成流网络；
- 用 Hall 条件解释一个不存在完美匹配的例子；
- 为加权任务分配说明普通最大流遗漏了什么。