图、依赖与拓扑顺序

本节目标

用节点和边表达任意关系，明确边方向与邻接表示；能遍历有环图而不重复访问，并判断何时存在覆盖全部节点的拓扑序。

节点、边与方向

图 $G=(V,E)$ 由节点集合 $V$ 和边集合 $E$ 组成。边可有向或无向。Agent 工作流通常使用有向依赖图。

“summarize 依赖 validate”有两种常见记录方式：

# 前驱表：任务 -> 它依赖的前置任务
predecessors = {
    "extract": set(),
    "validate": {"extract"},
    "summarize": {"validate"},
}
 
# 后继表：前置任务 -> 完成后可能解锁的任务
successors = {
    "extract": {"validate"},
    "validate": {"summarize"},
    "summarize": set(),
}

两者都正确，但方向相反。Python graphlib.TopologicalSorter(graph) 的映射值是该键节点的前驱。项目更新入度时常同时构建后继表。变量名必须写清，不能只叫 graph 后靠猜。

邻接表与邻接矩阵

• 邻接表：node → 相邻节点，空间通常为 $O(V+E)$，适合稀疏依赖图；
• 邻接矩阵：$V\times V$ 表格，检查一条边直接，但空间为 $O(V^2)$；
• 边列表：保存 (source, target)，便于传输/批处理，频繁查邻居前通常需建索引。

任务工作流边数通常远少于节点对数，邻接表更自然。数据库或图引擎的内部索引不等同于这个内存字典模型。

图遍历必须记录 visited

普通图可能有环或多条路径到同一节点。BFS 最小示例：

from collections import deque
 
 
def reachable(
    successors: dict[str, set[str]], start: str
) -> list[str]:
    if start not in successors:
        raise KeyError(start)
    seen = {start}
    queue = deque([start])
    order: list[str] = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in sorted(successors[node]):
            if neighbor not in seen:
                if neighbor not in successors:
                    raise ValueError(f"缺失节点: {neighbor}")
                seen.add(neighbor)
                queue.append(neighbor)
    return order

seen 在入队时更新，避免同一节点被多次加入。sorted 固定教学输出；若节点不可比较，应使用稳定 ID 或显式顺序键。

DAG 与拓扑序

有向无环图（Directed Acyclic Graph, DAG）存在拓扑序：每条 前驱 → 后继 边中，前驱都在后继之前。合法拓扑序可能不唯一；确定性输出需要额外平局规则。

Kahn 思路：

1. 计算每个节点入度（未完成前驱数）；
2. 将入度 0 的节点加入 ready；
3. 取出 ready 节点，依次把后继入度减 1；
4. 新变成 0 的后继加入 ready；
5. 若最终处理数少于节点数，剩余节点被一个或多个依赖环阻塞。

不含优先级时，该过程为 $O(V+E)$。用堆选择 ready 中的下一任务，会增加每个节点入堆/出堆的 $O(\log V)$ 成本。

有环时还能做什么

“图中有环”意味着不存在覆盖全部节点的完整拓扑序，不等于任何节点都不能开始。与环无关的无环分量仍可能执行；循环节点以及依赖它们的下游最终被阻塞。

TopologicalSorter.prepare() 检测到环会抛 CycleError，但调用方仍可通过 get_ready() 取得能继续推进的节点。若错误只列出“剩余阻塞节点”，不要把每个阻塞节点都声称为环成员；下游可能只是被环连带阻塞。精确报告环成员需要单独的强连通分量或环路径分析，本课程不设为必修。

TopologicalSorter 的两种使用

静态顺序：

from graphlib import TopologicalSorter
 
predecessors = {
    "extract": set(),
    "validate": {"extract"},
    "summarize": {"validate"},
}
order = tuple(TopologicalSorter(predecessors).static_order())

static_order() 的同层顺序可能受插入顺序影响；若结果要逐字节重放，应在输入构建或自定义 ready 选择层定义平局规则。并发式 prepare() / get_ready() / done() 只管理依赖可用性，不替你执行线程、处理失败或持久化状态。

练习

1. 为“读取→解析→校验→索引”同时写前驱表和后继表。
2. 为链、菱形、多独立分量手算入度和至少一个拓扑序。
3. 加入 index → parse 形成环，区分环成员与被环阻塞下游。
4. 用 reachable 遍历一个含回边的图，证明每个节点只出现一次。
5. 比较邻接表和矩阵对 10,000 节点、20,000 条边的空间增长，不必给固定字节数。

自测

• “A 依赖 B”在前驱表中如何表示？
• BFS 为什么在入队时加入 seen？
• 一个 DAG 的拓扑序是否一定唯一？
• 图中有环是否表示所有无关节点都不能执行？
• 剩余 blocked 节点是否都一定属于环？
• TopologicalSorter 的映射值表示前驱还是后继？

下一步与相关概念

• 下一节：结构组合、容量边界与性能诊断。
• 工作流执行、状态恢复和重试见 工作流自动化。

参考资料

获取日期：2026-07-14。

• Python 3.14：graphlib
• MIT OCW 6.006：Graph Search