图论基础：有向无环图（DAG）概念、节点与边、入度与出度、拓扑排序

说实话，刚开始做任务依赖系统的时候，我第一反应就是「这不就是个流程图嘛」。后来踩了几个坑才明白——有向无环图（DAG）才是真正能描述任务依赖关系的数学工具。你想想看，如果任务之间有循环依赖，那整个系统就死锁了，谁也跑不了。

这一节，我们就来把 DAG 的核心概念掰开揉碎。别怕，不涉及复杂的数学公式，全是工程里用得上的东西。

什么是 DAG？

DAG 的全称是 Directed Acyclic Graph，翻译过来就是「有向无环图」。拆开来看：

• 有向（Directed）：每条边都有方向，表示依赖关系从 A 指向 B，意思是「A 完成后才能做 B」。
• 无环（Acyclic）：图中不存在环路，你从任何一个节点出发，顺着箭头走，永远回不到起点。
• 图（Graph）：由节点和边组成的数据结构。

我在项目中遇到过最典型的场景——数据管道（Data Pipeline）。每个数据处理步骤是一个节点，数据流向就是边。如果 A 任务产出数据给 B 用，B 又产出数据给 C 用，这就是一条 DAG 路径。但如果你不小心让 C 又依赖回 A，那就坏了，系统会陷入死循环。

节点与边

这两个概念太基础了，但我还是想多说两句，因为很多人搞混了「节点」和「任务」的关系。

节点（Vertex / Node）

节点就是图中的基本单元。在任务依赖图里，一个节点通常代表一个可执行的任务单元。比如：

• 一个 Shell 脚本
• 一个 SQL 查询
• 一个 API 调用
• 一个数据处理函数

我个人习惯把节点分为两类：

类型	说明	示例
计算节点	执行实际逻辑，有输入输出	数据清洗、模型训练
控制节点	不执行逻辑，只做流程控制	条件判断、并行分支

边（Edge）

边表示节点之间的依赖关系。在 DAG 里，边是有方向的，用箭头表示。

举个例子：

任务A ——> 任务B ——> 任务C

意思是：A 完成后才能执行 B，B 完成后才能执行 C。箭头指向的是「被依赖方」还是「依赖方」？这里有个容易混淆的点——箭头通常从前置任务指向后置任务，即 A → B 表示「A 是 B 的前置条件」。

入度与出度

这两个概念在故障定位时特别有用。说白了，它们描述的是「一个节点在图中被依赖的程度」。

入度（In-Degree）

指向该节点的边的数量。入度 = 0 表示没有前置依赖，这类节点可以最先执行。

出度（Out-Degree）

从该节点出发的边的数量。出度 = 0 表示没有后置任务，这类节点通常是最终输出节点。

来看一个具体例子：

     A
    / \
   B   C
    \ /
     D

各节点的入度和出度：

节点	入度	出度	说明
A	0	2	起始节点，无前置依赖
B	1	1	依赖 A，产出给 D
C	1	1	依赖 A，产出给 D
D	2	0	终止节点，无后置任务

拓扑排序

拓扑排序是 DAG 里最核心的算法之一。它的作用很简单：给所有节点排个序，保证每个节点都在它的前置节点之后出现。

说白了，就是「先做谁，后做谁」的问题。

算法思路

拓扑排序有两种经典实现方式：

1. Kahn 算法（基于入度）：每次取出入度为 0 的节点，然后删除它的出边，重复直到所有节点都被处理。
2. DFS 后序遍历：深度优先遍历，在回溯时记录节点，最后反转顺序。

我个人更常用 Kahn 算法，因为它直观，而且能顺便检测环——如果处理完所有节点后还有剩余节点，说明图里有环。

Python 实现示例

from collections import deque, defaultdict

def topological_sort(graph):
    # graph: dict, key=节点, value=依赖该节点的后继节点列表
    # 计算入度
    in_degree = defaultdict(int)
    for node in graph:
        in_degree[node]  # 确保所有节点都在字典里
    for node, successors in graph.items():
        for succ in successors:
            in_degree[succ] += 1

    # 入度为0的节点入队
    queue = deque([node for node, deg in in_degree.items() if deg == 0])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)
        for succ in graph.get(node, []):
            in_degree[succ] -= 1
            if in_degree[succ] == 0:
                queue.append(succ)

    # 检测环
    if len(result) != len(graph):
        raise ValueError("图中存在环，无法进行拓扑排序")

    return result

# 示例
dag = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}
print(topological_sort(dag))  # 输出: ['A', 'B', 'C', 'D'] 或 ['A', 'C', 'B', 'D']

DAG 核心知识体系

下面这张图把这一节的核心概念串起来了，方便你对照理解：

为什么 DAG 在故障定位中这么重要？

嗯，这里要说到重点了。在任务依赖系统里，故障定位的本质就是沿着 DAG 的边反向追溯。

举个例子：假设任务 D 失败了。你不需要检查所有任务，只需要看 D 的前置节点（入度指向它的那些节点）。如果前置节点都成功了，那问题大概率出在 D 本身；如果某个前置节点失败了，那就继续往前追溯。

这就是 DAG 带来的好处——依赖关系清晰，故障传播路径可追踪。没有 DAG，你只能靠猜；有了 DAG，你可以精准定位。