拓扑排序：从课程表到构建依赖

拓扑排序给出有向无环图（DAG）顶点的一个线性次序，使得每条边 u → v 都满足 u 出现在 v 之前。有环则无解——这也是检测循环依赖的经典手段。

Kahn 算法（按入度）

反复取出入度为 0 的节点，删边并更新邻居入度。可用队列实现；若最终输出节点数少于总数，则存在环。

func topoKahn(n int, edges [][]int) ([]int, bool) {
    g := make([][]int, n)
    indeg := make([]int, n)
    for _, e := range edges {
        g[e[0]] = append(g[e[0]], e[1])
        indeg[e[1]]++
    }
    q := []int{}
    for i, d := range indeg {
        if d == 0 {
            q = append(q, i)
        }
    }
    order := make([]int, 0, n)
    for len(q) > 0 {
        u := q[0]
        q = q[1:]
        order = append(order, u)
        for _, v := range g[u] {
            indeg[v]--
            if indeg[v] == 0 {
                q = append(q, v)
            }
        }
    }
    return order, len(order) == n
}

DFS 后序翻转

对每个未访问节点 DFS，在回溯时压栈；最后反转即为一种拓扑序。环检测可用「访问中」三色标记。

工程里的坑

• 边的方向：是「A 依赖 B」还是「A 完成后才能 B」？建图前先统一语义。
• 并列节点顺序：拓扑序不唯一；需要稳定输出时，对入度 0 集合排序。
• 动态依赖：CI 里条件任务会改变图，不能一次排完就固化。

小结

课程表、镜像构建层、Terraform 资源依赖——看见「必须先完成 A 再 B」，就想到 DAG 与拓扑序。Kahn 直观好调试，DFS 在递归结构里也很自然。