数据结构与算法 - DAG

2025-12-30

全文 ≈ 670字 | 预计阅读时长 2分钟

有向无环图（Directed Acyclic Graph，简称 DAG）是一种图结构，由若干顶点和带方向的边组成。与普通有向图不同的是，DAG 中不存在环路——也就是说，不可能从某个顶点出发，沿着边的方向走一圈，最终又回到原点。

背景

项目QueryBuilder模块初始指标依赖层级相对固定，但版本多次迭代后，指标之间逐渐形成了复杂的依赖路径。原有的逻辑已无法支持，所以引入有向无环图（DAG），用于对指标依赖关系进行建模和解析。

定义

DAG 中的每个节点只关心两类关系：我依赖的和依赖我的。

type Node struct {
    dependencies []*Node // 当前节点依赖的前置节点
    dependents   []*Node // 依赖当前节点的后置节点
}

从任意节点开始执行时，需要先判断它是否具备执行条件。

- 如果 len(dependencies) == 0（入度），说明当前节点没有任何前置依赖节点，可以立即执行。

- 如果 len(dependencies) > 0，则表示仍然存在尚未完成的前置依赖节点，当前节点需要等待。

当节点执行完成后，需要处理对其他节点的前置依赖关系。

- 如果 len(dependents) == 0，说明当前节点已经处于依赖路径的尾端，不需要执行其他操作。

- 如果 len(dependents) > 0，则表示需要把这些节点的前置依赖节点数量-1。

通俗地说，当前节点是否可以执行，取决于入度是否为0。

实现

在具体实现时，有一个容易误解的点：不能直接通过 dependencies 或 dependents 的长度来判断节点是否可以执行，需要根据运行时状态inDegree判断节点是否可执行。

type dag struct {
    nodes    map[string]*Node
}

type Node struct {
    id           string
    dependencies []*Node // 当前节点依赖的前置节点
    dependents   []*Node // 依赖当前节点的后置节点
}

func (d *dag) Execute() (nodeIds []string, err error) {
    // 入度
    inDegree := make(map[string]int)
    for id, node := range d.nodes {
        inDegree[id] = len(node.dependencies)
    }

    // 初始化队列
    queue := make([]string, 0)
    for id, dependNum := range inDegree {
        if dependNum != 0 {
            continue
        }
        queue = append(queue, id)
    }

    // bfs + kahn
    for len(queue) > 0 {
        // 出队
        id := queue[0]
        queue = queue[1:]

        // 影响后置节点
        curNode := d.nodes[id]
        for _, depend := range curNode.dependents {
            inDegree[depend.id]--
            if inDegree[depend.id] != 0 {
                continue
            }
            queue = append(queue, depend.id)
        }
        nodeIds = append(nodeIds, id)
    }

    // 如果没处理完所有节点，说明有环
    if len(nodeIds) != len(d.nodes) {
        return nil, errors.New("cycle detected in DAG")
    }

    return
}

最后

忙碌了一年，辞旧迎新之际～记录一下

附上完整代码：dag