计算图：图构建与遍历

可视化演示

展示图遍历三维度：拓扑排序（Kahn算法入度0优先入队O(V+E）保证执行顺序)、前序vs后序遍历（前序根→左→右用于常量折叠/后序左→右→根用于自动微分反向传播）、图模式匹配（Conv+BN+Relu子图模式匹配命中后替换为单个Fused算子），三模式切换理解编译器优化Pass执行机制。

计算图构建

主厨画作战图的第一步，不是开火，而是把每道菜的原料关系写在黑板上：“A 菜需要 B 菜提供的半成品”。在编译器里，这一步叫计算图构建：把神经网络的前向代码逐行翻译成一张图。图中的圆圈叫节点，对应一个算子（卷积、加法、激活函数等一次运算操作）；箭头叫边，对应张量的数据流向。构建流程通常是：框架解析前向函数，遇到一个算子就注册一个新节点，再把算子输入对应的上游节点连到它身上。PyTorch 的 torch.fx、TensorFlow 的 GraphDef 都在做这件事。

计算图必须满足有向无环图（DAG）约束：任何节点都不能直接或间接依赖自己，否则就会出现死循环般的依赖。后厨里不可能存在“这道菜需要自己出锅后的汤汁”这种菜谱。编译器在构建时会对每条新建的边做校验，发现环就报错拒绝编译。

作战图画好只是第一步；黑板上的图必须落成便于查阅的备忘录，否则上千道菜的关系根本记不住。这就是下一节的存储表示。

图的存储表示

后厨作战图怎么保存？有两种极端方案：一种是每个加工台贴一张“我完成后通知 B、C 两台”的小纸条；另一种是画一张超大的总表，横竖都列满所有菜名，在对应的格子里打勾。前者是邻接表，后者是邻接矩阵。

邻接表为每个节点存一份后继节点列表，内存开销是 O(V+E)，适合边稀疏的大图；邻接矩阵用 n×n 的 0/1 方阵表示任意两点之间是否有边，查询只需 O(1)，但要吃掉 O(V²) 空间。AI 编译器更常用的是 CSR（压缩稀疏行） 格式：把邻接表按行拼接，用三个数组记录每行的偏移、列号和数值，既省内存又利于顺序访问。CSR 相当于把小纸条按加工台顺序装订成册，每页只写“本台通知谁”。

大模型的计算图动辄上万节点、数万条边，用邻接矩阵意味着上亿个格子，绝大多数是 0，浪费惊人。因此工业界的图 IR（如 XLA 的 HLO、TVM 的 Relay）几乎都采用邻接表或 CSR 一类紧凑表示。

婚宴菜单不可能印全所有菜的两两关系；现实中的编译器几乎都选邻接表或 CSR，省下的内存留给真正有用的优化。

拓扑排序

作战图确定后，主厨要排上菜顺序：炖汤要提前三小时吊水，凉菜可以最后十分钟拼盘。规则只有一条——箭头必须从先做到后做。把这种顺序排出来，就是拓扑排序。

拓扑排序把 DAG 的所有节点排成一个线性序列，保证每条边的起点都出现在终点之前。最常用的 Kahn 算法 很直白：反复找出“入度为 0 的节点”（也就是原料齐全、随时可以开工的加工台），把它输出，再把它所有后继的入度减 1，重复直到图被清空。另一个实现来自 DFS：对每个节点做后序 DFS，把回溯完成的节点依次记录，最后将序列逆序输出（即逆后序），同样得到合法拓扑序；若输出的节点数少于总节点数，说明图中存在环——这就是环检测。

编译器拿到拓扑序后，就按这个顺序下发算子执行指令，保证每个算子执行时它的输入都已经算好。这就像主厨按拓扑序把任务单贴到各加工台，厨房才不会出现“汤还没吊好就开始炖佛跳墙”的混乱。

前序遍历

主厨巡视厨房时有一种走法：走到一个加工台，先把任务交代清楚（“你这台负责出高汤”），再往下走到需要高汤的台子继续交代。这种“先访问父节点、再依次访问子节点”的走法，就是前序遍历。

前序遍历从根节点出发：先处理当前节点，再递归遍历它的所有直接后继。在 AI 编译器中，自顶向下的 Pass 正是依赖这种顺序——例如形状推断（shape inference）：父节点把张量的形状信息传给子节点，子节点据此推导自己的输出形状，信息像水流一样从根流向叶子。前序遍历的递归实现非常简洁：先访问自己，再对每个子节点调用同样的函数。

要注意，前序遍历结果一般不满足拓扑序。举个反例：根节点 A 先访问子节点 B，再访问子节点 C，但图中存在边 C→B，序列里 B 却排在 C 前面，就违反了“起点在终点之前”的约束。所以前序适合“从根到叶传播信息”的任务，不适合安排执行顺序。

前序遍历像主厨“从上到下布置任务”，信息一路向下游传递；但布置任务和真正开火是两回事，真正的开火顺序是反过来的——这就是下一节要讲的从下往上的走法。

后序遍历

真正的开火顺序是反着的：高汤吊好、配菜切好，佛跳墙的加工台才开始拼装；拼装完成，才轮到下一道依赖它的菜。这种“子节点全部处理完，才处理父节点”的走法，就是后序遍历。

后序遍历先递归处理所有子节点，再把当前节点放进序列，因此它是自底向上 Pass 的骨架。常量折叠（constant folding）先递归把子表达式算成常量，再把父算子替换成常量结果；内存规划先处理子节点的生命周期，父节点的输出才能安全复用缓冲区。代码生成里“先编译子图、再拼接父算子”也遵循同样的逻辑。

后序遍历与拓扑排序关系密切：把后序序列取逆序，就得到一个合法的拓扑序（这正是 DFS 实现拓扑排序的原理）。动画演示里 G、E、F 先被点亮，D 在其后，A 最后——每个节点出现时它的下游都已就绪，逆序读出来就是"A → C → B → D → F → E → G"这样的执行顺序。

后厨里“备料齐了才开火”的顺序，正好就是编译器执行算子、回收内存的顺序——从上到下布置，从下到上执行，两者配合才能让整张图顺畅跑起来。

图匹配与替换

老师傅看到菜谱里“糖、醋、生抽、水淀粉、小火收汁”连续五步，立刻认出这就是糖醋汁配方，直接拿出调好的酱料替换整段步骤。编译器里的图匹配做的就是这件事：在大图里认出某个固定的子图结构，然后用一个等价但更高效的算子把它整体替换掉。

具体做法分三步：定义模式（pattern）——一张小 DAG，比如“Conv 后接 BN”；在目标图中寻找与模式结构相同的子图；命中后执行替换，例如把 Conv+BN 融合成一个 ConvBN 算子，省掉一次中间张量的写盘与读盘。算子融合、精度回退（fp32→fp16 的模式替换）、布局转换，都是图匹配的典型应用。

这里的“认出”不是靠算子名字比对，而是子图同构（subgraph isomorphism）：存在一个从模式节点到目标图节点的映射，把模式里每条边都保持到图里的边。子图同构在一般图上是个难问题（NP 完全），所以编译器会用锚定节点、拓扑序剪枝、模式哈希库等技巧加速，这也是图匹配工程实现真正的难点。

就像老师傅用现成酱料替换五步烹制，图匹配把一个 6 节点的子图折叠成 1 个融合算子，推理引擎的延迟与显存占用因此大幅下降——这就是计算图遍历与匹配在真实世界的价值。

AI 应用场景

Python 演示

class Node:    def __init__(self, name, op):        self.name = name        self.op = op        self.inputs = []  class Graph:    def __init__(self):        self.nodes = {}     def add(self, name, op, inputs):        n = Node(name, op)        n.inputs = list(inputs)        self.nodes[name] = n     def successors(self, u):        return [v for v, n in self.nodes.items() if u in n.inputs]     def topo_order(self):        indeg = {name: len(n.inputs) for name, n in self.nodes.items()}        ready = [name for name, d in indeg.items() if d == 0]        order = []        while ready:            u = ready.pop(0)            order.append(u)            for v in self.successors(u):                indeg[v] -= 1                if indeg[v] == 0:                    ready.append(v)        if len(order) != len(self.nodes):            raise RuntimeError("cycle detected")        return order     def postorder_from(self, u, visited, out):        visited.add(u)        for v in self.successors(u):            if v not in visited:                self.postorder_from(v, visited, out)        out.append(u)     def postorder(self):        visited = set()        out = []        for name, n in self.nodes.items():            if not n.inputs and name not in visited:                self.postorder_from(name, visited, out)        return out  def match_pattern(g, src_op, dst_op):    pairs = []    for dst, n in g.nodes.items():        if n.op == dst_op:            for src in n.inputs:                if g.nodes[src].op == src_op:                    pairs.append((src, dst))    return pairs  def main():    g = Graph()    g.add("x", "input", [])    g.add("w1", "const", [])    g.add("conv1", "conv", ["x", "w1"])    g.add("bn1", "bn", ["conv1"])    g.add("relu1", "relu", ["bn1"])    g.add("w2", "const", [])    g.add("conv2", "conv", ["relu1", "w2"])    g.add("bn2", "bn", ["conv2"])    g.add("relu2", "relu", ["bn2"])    g.add("out", "add", ["relu1", "relu2"])     print("topo: ", g.topo_order())    print("post: ", g.postorder())    pairs = match_pattern(g, "conv", "bn")    print("conv-bn pairs: ", pairs)  if __name__ == "__main__":    main()

1. self.nodes = {}用字典按名字索引节点，相当于给每个加工台贴一张名牌。
2. def add(self, name, op, inputs)构建图的入口：每遇到一个算子就注册一个节点并记录输入依赖。
3. indeg = {name: len(n.inputs) for name, n in self.nodes.items()}Kahn 算法的起点：统计每个节点的入度，即“还差几样原料”。
4. ready = [name for name, d in indeg.items() if d == 0]原料齐全（入度为 0）的加工台先开工。
5. for v in self.successors(u): indeg[v] -= 1节点完成后通知下游：入度减 1，可能有新加工台备齐原料。
6. raise RuntimeError("cycle detected")输出节点数不足即存在环，编译器因此拒绝执行。
7. def postorder_from(self, u, visited, out):后序 DFS 核心：先递归子节点，最后把自身放入序列。
8. out.append(u)这一行的位置决定了是前序还是后序，是遍历中最关键的一行。
9. pairs = match_pattern(g, "conv", "bn")图匹配入口：找出所有可融合的 Conv→BN 边。

常见误区

面试题