4. 依赖图建模

在文件系统构建中，依赖关系天然具有方向性：一个目标文件由若干源文件生成，一个模块链接若干库，一个镜像打包若干目录。把这些关系抽象为有向图，是依赖裁剪从“经验判断”走向“可计算”的关键一步。本节围绕有向图、依赖闭包、强连通分量与拓扑排序四个概念，说明它们在构建系统中的具体表示方法与工程价值。

一、核心原理：构建依赖的有向图表征

构建系统通常把每个可构建单元（源文件、目标文件、库、镜像节点）视为图的顶点，把“A 需要 B 才能生成”视为从 A 指向 B 的有向边。例如 app.bin 依赖 libfs.a，libfs.a 依赖 inode.o 与 block.o，就形成一条有向路径。边的方向表示“依赖指向被依赖者”，与构建执行顺序相反，这一点在阅读依赖图时最容易混淆。

依赖图可用邻接表表示，便于遍历与裁剪：

graph = {
  "app.bin":   ["libfs.a", "libc.a"],
  "libfs.a":   ["inode.o", "block.o", "super.o"],
  "inode.o":   ["inode.c", "fs.h"],
  "block.o":   ["block.c", "fs.h"],
  "super.o":   ["super.c", "fs.h"],
  "libc.a":    ["string.o", "stdio.o"]
}

有了这张图，裁剪问题就转化为图论问题：哪些顶点是根目标的可达集合？哪些顶点互相纠缠形成环？按什么顺序处理才能保证被依赖者先完成？

二、依赖闭包：裁剪的“安全边界”

依赖闭包指从某个根节点出发，沿有向边可达的全部节点集合。对文件系统构建而言，根节点通常是最终镜像或顶层目标，闭包内的节点是“必须保留”的最小候选集，闭包外的节点才是可裁剪对象。计算闭包常用深度优先或广度优先遍历：

def closure(graph, root):
    seen, stack = set(), [root]
    while stack:
        n = stack.pop()
        if n in seen: continue
        seen.add(n)
        stack.extend(graph.get(n, []))
    return seen

keep = closure(graph, "app.bin")
# keep = {app.bin, libfs.a, libc.a, inode.o, block.o,
#         super.o, inode.c, block.c, super.c, fs.h,
#         string.o, stdio.o}

闭包给出的是上界：闭包外的节点一定可以删除，闭包内的节点仍需进一步判断是否被条件编译、运行时开关或配置项真正使用。因此工程上常把闭包作为第一层粗筛，再叠加符号引用、Kconfig 选项等细筛手段。

三、强连通分量：识别循环依赖

当图中存在 A→B→C→A 这样的回路时，A、B、C 属于同一个强连通分量（SCC）。在文件系统构建中，SCC 往往意味着头文件互相包含、模块循环引用或生成规则互相触发。SCC 的工程含义是：分量内部无法单独裁剪，必须整体保留或整体重构。常用 Tarjan 或 Kosaraju 算法在线性时间内求出所有 SCC，并将每个 SCC 收缩为一个超级节点，得到有向无环图（DAG）。

四、拓扑排序：确定构建与裁剪顺序

在 DAG 上执行拓扑排序，可得到满足“被依赖者在前、依赖者在后”的线性序列。构建系统据此安排编译与链接顺序；裁剪工具则按逆拓扑序自底向上判断节点是否可删——先处理叶子节点，再处理上层节点，避免误删仍被引用的中间产物。

# 逆拓扑序裁剪示意
order = topo_sort(dag)          # 被依赖者在前
for node in reversed(order):    # 从最终目标向下回溯
    if not referenced(node) and node not in roots:
        remove(node)

下面这张图展示了从根目标 app.bin 出发的依赖图：实线箭头表示依赖方向，虚线框标出依赖闭包范围，fs.h 与两个目标文件构成一个强连通分量，右侧给出拓扑排序结果。

五、案例场景：裁剪一个嵌入式文件系统镜像

某嵌入式项目构建 rootfs.img，依赖图包含 180 个节点。团队先计算闭包，得到 132 个必留节点；再求 SCC，发现 fs.h、inode.o、block.o 构成一个 3 节点环，原因是头文件互相包含。拆分头文件后环被打破，DAG 上执行拓扑排序，按逆序删除 41 个未被引用的调试模块与冗余库，镜像体积下降约 18%，构建时间缩短约 12%。

六、误区与复盘

• 把边方向画反：依赖边应指向被依赖者，若画成“被依赖者指向依赖者”，拓扑序与裁剪顺序会整体颠倒。
• 忽略 SCC 直接删节点：环内节点互相引用，单独删除会导致链接失败或运行时缺符号。
• 把闭包当作最终结果：闭包只是上界，条件编译、运行时开关、配置项都可能让闭包内节点实际未被使用。
• 拓扑序不唯一却强行固定：多个合法拓扑序都正确，裁剪工具应关注偏序约束而非唯一序列。

掌握有向图、依赖闭包、强连通分量与拓扑排序这四件工具后，依赖裁剪就从“凭感觉删文件”升级为“按图计算、按序执行、按环重构”的可重复工程流程，为后续的符号级裁剪与配置驱动裁剪打下坚实基础。