土法炼钢兴趣小组的算法知识备份

拓扑排序：依赖解析的核心

2026-06-08 · algorithms · #topological-sort #dag #dependency #kahn #build-system #scheduler

目录

2003 年，一个 Debian 开发者在安装一组包时发现 apt-get 死循环了。原因是两个包互相写了 Pre-Depends，而 dpkg 在尝试按依赖顺序安装时进入了无限递归。这不是 bug——这是拓扑排序遇到环时最诚实的反应：不存在合法的安装顺序，算法无法给出一个不存在的答案。

在软件工程中，拓扑排序无处不在。你每次运行 make，每次 npm install，每次 cargo build，背后都有一个拓扑排序在默默工作。它决定了哪个文件先编译、哪个包先安装、哪个任务先执行。这个算法本身极其简单——简单到大多数人学过就忘了。但当你真的需要在生产环境中实现一个依赖解析器时，才会发现那些被教科书略过的细节才是真正的麻烦。

本文从 DAG 的基本定义讲起，深入 Kahn 算法和 DFS 两种经典实现，讨论环检测、字典序最小排序、并行拓扑排序和 DAG 最长路径等进阶话题，给出完整的 C 实现，最后用真实的构建系统和任务调度场景串联所有知识点。

Kahn 算法执行过程

一、DAG 与拓扑序的形式化定义

拓扑排序的前提是 DAG（Directed Acyclic Graph，有向无环图）。我们先把定义钉死。

有向图：一个图 G = (V, E)，其中 E 中的每条边 (u, v) 是有序对，表示从 u 到 v 的单向关系。

无环：图中不存在任何顶点 v 使得从 v 出发沿有向边可以回到 v 自身。形式化地说，不存在长度大于等于 1 的有向路径 v -> v1 -> … -> v。

拓扑序（Topological Order）：对 DAG 中所有顶点的一个线性排列 v1, v2, …, vn，使得对于每条有向边 (vi, vj)，都有 i < j。换言之，如果 u 依赖 v（存在边 v -> u），那么 v 一定排在 u 前面。

几个关键性质：

  1. 存在性：一个有向图存在拓扑序，当且仅当它是 DAG。这是一个充要条件。
  2. 非唯一性：除非图是一条链（每个节点恰好一个前驱一个后继），否则拓扑序不唯一。对于 n 个独立节点的图，有 n! 种拓扑序。
  3. 入度为零的必然性：任何 DAG 至少有一个入度为 0 的节点。证明：假设所有节点入度都大于等于 1，从任意节点沿入边回溯，由于节点有限，必然回到已经访问过的节点，形成环，矛盾。

这第三条性质正是 Kahn 算法的理论基础。

拓扑排序和偏序（Partial Order）的关系值得一提。DAG 定义了一个偏序关系：如果存在从 u 到 v 的路径，则 u < v。拓扑排序就是把这个偏序”线性化”（linearization），得到一个全序，使其与偏序兼容。这在序理论中叫做线性扩展（Linear Extension）。

从复杂度的角度看：

这意味着”找一个拓扑序”是容易的，但”有多少种拓扑序”这个计数问题是计算上极其困难的。

二、Kahn 算法：入度与 BFS

Kahn 算法由 Arthur B. Kahn 于 1962 年提出，是最直观的拓扑排序方法。核心思想是反复剥离入度为 0 的节点。

算法步骤

1. 计算所有节点的入度
2. 将入度为 0 的节点全部加入队列
3. 当队列非空时：
   a. 弹出队首节点 u，加入输出序列
   b. 对 u 的每个邻居 v：
      - in_degree[v] -= 1
      - 若 in_degree[v] == 0，将 v 加入队列
4. 若输出序列长度 < |V|，则图中存在环

为什么能检测环

如果图中存在环，环上的所有节点的入度永远不会降为 0。因为每个环上节点至少有一条来自环内的入边。当算法结束时，队列为空但还有节点未被处理——这些就是在环上（或依赖于环上节点）的节点。

时间复杂度分析

空间方面需要入度数组 O(V) 和队列 O(V)，总空间 O(V)（不计图本身的存储）。

伪代码的精确实现

以下是考虑了边界情况的伪代码：

def kahn_topo_sort(graph):
    n = len(graph.vertices)
    in_degree = [0] * n
    for u in graph.vertices:
        for v in graph.adj[u]:
            in_degree[v] += 1

    queue = deque()
    for v in range(n):
        if in_degree[v] == 0:
            queue.append(v)

    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph.adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)

    if len(order) != n:
        return None  # 存在环
    return order

这段代码有一个重要特性：输出顺序依赖于初始入度为 0 的节点进入队列的顺序。如果用普通 FIFO 队列，结果是”某一个”合法拓扑序。如果想要字典序最小的拓扑序，把队列换成最小堆即可——这是后面第五节的内容。

三、DFS 拓扑排序：后序的逆序

DFS 方法在算法竞赛和编译器实现中更常见，因为它可以和环检测、强连通分量等算法共享基础设施。

核心思想

对图做 DFS，当一个节点的所有后继都已经被访问完毕后，将该节点压入栈。最终栈的出栈顺序（即后序遍历的逆序）就是一个合法的拓扑序。

为什么后序的逆序是拓扑序？对于任意边 (u, v)： - 如果在 DFS 中先访问 u，那么 v 会在 u 的 DFS 子树中被访问，v 的后序时间戳小于 u 的后序时间戳，逆序后 u 在 v 前面。 - 如果在 DFS 中先访问 v，那么在访问 u 时 v 已经完成（因为 u -> v 的边不可能让 v 是 u 的祖先，否则就有环），v 的后序时间戳小于 u 的，逆序后 u 依然在 v 前面。

算法步骤

1. 初始化所有节点为"未访问"
2. 对每个未访问的节点调用 DFS
3. DFS(u):
   a. 标记 u 为"进行中"
   b. 对 u 的每个邻居 v：
      - 若 v 为"进行中"：发现环（反向边）
      - 若 v 为"未访问"：递归 DFS(v)
   c. 标记 u 为"已完成"
   d. 将 u 压入结果栈
4. 将栈反转得到拓扑序

三色标记法

上述算法中，节点有三种状态：

颜色 状态 含义
白色 未访问 尚未被 DFS 触及
灰色 进行中 已进入但未退出，在当前 DFS 路径上
黑色 已完成 所有后继都已处理

关键：如果在 DFS 过程中遇到一个灰色节点，说明从当前节点可以到达一个正在 DFS 路径上的祖先——这就是一条反向边（back edge），证明环的存在。

伪代码

def dfs_topo_sort(graph):
    n = len(graph.vertices)
    color = [WHITE] * n
    result = []
    has_cycle = False

    def dfs(u):
        nonlocal has_cycle
        if has_cycle:
            return
        color[u] = GRAY
        for v in graph.adj[u]:
            if color[v] == GRAY:
                has_cycle = True
                return
            if color[v] == WHITE:
                dfs(v)
        color[u] = BLACK
        result.append(u)

    for v in range(n):
        if color[v] == WHITE:
            dfs(v)

    if has_cycle:
        return None
    result.reverse()
    return result

Kahn vs DFS：如何选择

维度 Kahn（BFS） DFS
直觉 剥离入度为 0 的层 后序逆序
环检测 输出数量 < V 发现反向边
最小字典序 队列换堆即可 需要额外处理
并行化 天然按层并行 困难
递归深度 无递归 最坏 O(V)
实际用途 构建系统、包管理 编译器、强连通分量

在工程实践中，构建系统（Make、Bazel）几乎都用 Kahn 的变体，因为它天然支持”层级并行”——同一层（同一轮入度降为 0）的任务可以并行执行。而编译器后端更倾向 DFS，因为它可以和支配树、活跃变量分析等后续 pass 共享 DFS 框架。

四、环检测的深层问题

在教科书里，环检测是拓扑排序的”副产品”。但在工程中，仅仅报告”存在环”是不够的——用户需要知道哪些节点构成了环。

Kahn 算法中定位环

Kahn 算法结束后，所有入度没有降为 0 的节点要么在环上，要么依赖于环上的节点。要找到实际的环，需要在这些”遗留节点”的子图中做进一步搜索（比如跑 DFS 找反向边，或者用 Tarjan 找强连通分量）。

def find_cycle_kahn(graph, remaining_nodes):
    """在 Kahn 算法剩余节点中找环"""
    # 在 remaining_nodes 的导出子图上做 DFS
    visited = set()
    path = []
    path_set = set()

    def dfs(u):
        visited.add(u)
        path.append(u)
        path_set.add(u)
        for v in graph.adj[u]:
            if v not in remaining_nodes:
                continue
            if v in path_set:
                # 找到环：从 v 到当前 path 末尾
                cycle_start = path.index(v)
                return path[cycle_start:]
            if v not in visited:
                result = dfs(v)
                if result:
                    return result
        path.pop()
        path_set.remove(u)
        return None

    for u in remaining_nodes:
        if u not in visited:
            cycle = dfs(u)
            if cycle:
                return cycle
    return None

DFS 中提取环路径

DFS 的三色标记天然可以记录环路径。当发现反向边 (u, v) 时，v 是灰色的，意味着 v 在当前递归调用栈上。从调用栈中 v 的位置到栈顶，就是一个环。

实际包管理器的处理

不同的工具对环的态度截然不同：

一条经验法则：编译时依赖不应该有环，运行时依赖可以谨慎地允许环。编译时依赖的环意味着无法确定编译顺序；运行时依赖的环可以通过延迟初始化、接口注入等手段打破。

五、字典序最小的拓扑排序

这是算法竞赛中的高频题目，也是某些确定性要求下的工程需求（比如生成可重现的构建计划）。

问题定义

给定 DAG，求所有合法拓扑序中字典序最小的一个。

解法

将 Kahn 算法中的普通队列替换为最小堆（优先级队列）。每次弹出编号/名称最小的入度为 0 的节点。

import heapq

def smallest_topo_order(graph):
    n = len(graph.vertices)
    in_degree = [0] * n
    for u in range(n):
        for v in graph.adj[u]:
            in_degree[v] += 1

    heap = []
    for v in range(n):
        if in_degree[v] == 0:
            heapq.heappush(heap, v)

    order = []
    while heap:
        u = heapq.heappop(heap)
        order.append(u)
        for v in graph.adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                heapq.heappush(heap, v)

    return order if len(order) == n else None

复杂度

由于使用了堆，每次插入/弹出是 O(log V)，总复杂度变为 O(V log V + E)，略高于普通 Kahn 的 O(V + E)。在 V 很大但对确定性有要求的场景下（如 Bazel 的 action graph），这个代价是值得的。

字典序最大

对称地，用最大堆即可。或者更巧妙地：用最大堆做”反向拓扑”（出度为 0 的先弹出），然后反转结果——但这只在某些特定条件下成立，不能直接把最大堆套在 Kahn 上就得到字典序最大的拓扑序。这是一个常见的陷阱。

正确的做法：将图反向（所有边反转），在反向图上用最大堆跑 Kahn，得到的序列再反转，才是字典序最大的拓扑序。

六、并行拓扑排序：按层剥离

在构建系统中，我们不仅需要一个拓扑序，还需要知道”哪些任务可以并行执行”。Kahn 算法天然提供了这个信息。

层级分解

修改 Kahn 算法，每次不是逐个弹出节点，而是将当前队列中所有入度为 0 的节点作为一”层”整体弹出：

def level_topo_sort(graph):
    n = len(graph.vertices)
    in_degree = [0] * n
    for u in range(n):
        for v in graph.adj[u]:
            in_degree[v] += 1

    current_level = [v for v in range(n) if in_degree[v] == 0]
    levels = []

    while current_level:
        levels.append(current_level)
        next_level = []
        for u in current_level:
            for v in graph.adj[u]:
                in_degree[v] -= 1
                if in_degree[v] == 0:
                    next_level.append(v)
        current_level = next_level

    total = sum(len(level) for level in levels)
    if total != n:
        return None  # 存在环
    return levels

层数的含义

层数（level count）等于 DAG 中最长路径的长度加一。这意味着：

Bazel 的实现

Google 的 Bazel 构建系统正是用这种方式工作的。它将构建动作（action）组织成 DAG，按层并行执行。Bazel 的 --jobs 参数控制每层内的最大并行度。当你用 bazel build //... 构建整个项目时，内部的拓扑排序决定了执行计划：

Layer 0: [生成 proto 代码, 编译 IDL]          # 无依赖，立即启动
Layer 1: [编译 proto 客户端, 编译 proto 服务端]  # 依赖 Layer 0
Layer 2: [编译 service A, 编译 service B]       # 依赖 Layer 1
Layer 3: [链接最终二进制]                       # 依赖 Layer 2

实际中 Bazel 不是严格按层执行的——它用的是一种贪心调度：只要一个任务的所有前驱都完成了就立即执行，不等同层的其他任务。这在实际中比严格的层级并行更高效，但理论上的时间下界是一样的。

七、DAG 最长路径与关键路径

问题定义

在带权 DAG 中，求从任意源点到任意汇点的最长路径。这个问题在一般图上是 NP-hard 的，但在 DAG 上可以利用拓扑排序在 O(V + E) 内解决。

算法

思路是动态规划：按拓扑序处理节点，对每个节点 u，用 u 的所有入边更新 u 的最长距离。

def dag_longest_path(graph, weights):
    """weights[(u, v)] 是边 (u, v) 的权重"""
    order = kahn_topo_sort(graph)
    if order is None:
        return None  # 有环

    dist = [-float('inf')] * len(graph.vertices)
    parent = [-1] * len(graph.vertices)

    # 所有源点（入度为 0）的距离初始化为 0
    in_deg = compute_in_degree(graph)
    for v in range(len(graph.vertices)):
        if in_deg[v] == 0:
            dist[v] = 0

    for u in order:
        for v in graph.adj[u]:
            w = weights.get((u, v), 1)
            if dist[u] + w > dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u

    return dist, parent

关键路径方法（CPM）

关键路径方法（Critical Path Method）是项目管理中的经典技术，本质就是 DAG 最长路径。

在项目管理中： - 节点是任务，边是依赖关系 - 边权是前序任务的持续时间 - 最长路径就是项目的最短完成时间 - 路径上的任务没有任何松弛时间（slack = 0），任何一个延迟都会延长项目

最早开始时间（Earliest Start, ES）和最晚开始时间（Latest Start, LS）可以通过一次正向遍历和一次反向遍历分别求出：

正向（拓扑序）：ES[v] = max(ES[u] + duration[u]) for all u -> v
反向（逆拓扑序）：LS[v] = min(LS[w] - duration[v]) for all v -> w
松弛时间：Slack[v] = LS[v] - ES[v]
关键路径：Slack[v] == 0 的所有节点

这和构建系统的并行调度直接对应：关键路径上的任务是瓶颈，优化它们才能缩短总构建时间。

在构建系统中的应用

当你运行 make -j16 却发现构建时间比预期长时，通常是关键路径太长。make 虽然能并行编译，但如果存在一条很长的串行依赖链（比如 A -> B -> C -> D -> E 必须依次编译），那么无论开多少个并行 job 都无法加速这条链。

Bazel 提供了 --profile 选项来可视化构建过程的关键路径。Buck2 在其设计文档中明确将关键路径分析作为构建优化的核心指标。

八、完整 C 实现

以下是一个完整的、生产可用的 C 实现，同时包含 Kahn 算法和 DFS 拓扑排序，以及环检测。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_VERTICES 1024
#define MAX_EDGES    8192

/* ---- 图的邻接表表示 ---- */

typedef struct Edge {
    int to;
    int next;
} Edge;

typedef struct Graph {
    int head[MAX_VERTICES];
    Edge edges[MAX_EDGES];
    int edge_count;
    int vertex_count;
} Graph;

void graph_init(Graph *g, int n) {
    g->vertex_count = n;
    g->edge_count = 0;
    memset(g->head, -1, sizeof(int) * n);
}

void graph_add_edge(Graph *g, int from, int to) {
    Edge *e = &g->edges[g->edge_count];
    e->to = to;
    e->next = g->head[from];
    g->head[from] = g->edge_count;
    g->edge_count++;
}

/* ---- Kahn 算法（BFS 拓扑排序） ---- */

int kahn_topo_sort(const Graph *g, int *order) {
    int n = g->vertex_count;
    int in_degree[MAX_VERTICES];
    int queue[MAX_VERTICES];
    int front = 0, rear = 0;
    int count = 0;

    memset(in_degree, 0, sizeof(int) * n);

    /* 计算入度 */
    for (int u = 0; u < n; u++) {
        for (int i = g->head[u]; i != -1; i = g->edges[i].next) {
            in_degree[g->edges[i].to]++;
        }
    }

    /* 入度为 0 的节点入队 */
    for (int v = 0; v < n; v++) {
        if (in_degree[v] == 0) {
            queue[rear++] = v;
        }
    }

    /* BFS 主循环 */
    while (front < rear) {
        int u = queue[front++];
        order[count++] = u;

        for (int i = g->head[u]; i != -1; i = g->edges[i].next) {
            int v = g->edges[i].to;
            in_degree[v]--;
            if (in_degree[v] == 0) {
                queue[rear++] = v;
            }
        }
    }

    return count;  /* count < n 表示有环 */
}

/* ---- DFS 拓扑排序（含环检测） ---- */

typedef enum { WHITE, GRAY, BLACK } Color;

typedef struct {
    const Graph *graph;
    Color color[MAX_VERTICES];
    int stack[MAX_VERTICES];
    int stack_top;
    bool has_cycle;
} DFSContext;

static void dfs_visit(DFSContext *ctx, int u) {
    if (ctx->has_cycle) return;

    ctx->color[u] = GRAY;

    for (int i = ctx->graph->head[u]; i != -1;
         i = ctx->graph->edges[i].next)
    {
        int v = ctx->graph->edges[i].to;

        if (ctx->color[v] == GRAY) {
            ctx->has_cycle = true;
            return;
        }
        if (ctx->color[v] == WHITE) {
            dfs_visit(ctx, v);
            if (ctx->has_cycle) return;
        }
    }

    ctx->color[u] = BLACK;
    ctx->stack[ctx->stack_top++] = u;
}

int dfs_topo_sort(const Graph *g, int *order) {
    DFSContext ctx;
    ctx.graph = g;
    ctx.stack_top = 0;
    ctx.has_cycle = false;
    int n = g->vertex_count;

    for (int i = 0; i < n; i++) {
        ctx.color[i] = WHITE;
    }

    for (int v = 0; v < n; v++) {
        if (ctx.color[v] == WHITE) {
            dfs_visit(&ctx, v);
            if (ctx.has_cycle) return -1;
        }
    }

    /* 后序逆序 => 拓扑序 */
    for (int i = 0; i < n; i++) {
        order[i] = ctx.stack[n - 1 - i];
    }
    return n;
}

/* ---- 层级并行拓扑排序 ---- */

int level_topo_sort(const Graph *g, int *order, int *level_sizes) {
    int n = g->vertex_count;
    int in_degree[MAX_VERTICES];
    int cur_buf[MAX_VERTICES], nxt_buf[MAX_VERTICES];
    int cur_size = 0, nxt_size;
    int count = 0, num_levels = 0;

    memset(in_degree, 0, sizeof(int) * n);
    for (int u = 0; u < n; u++) {
        for (int i = g->head[u]; i != -1; i = g->edges[i].next) {
            in_degree[g->edges[i].to]++;
        }
    }

    for (int v = 0; v < n; v++) {
        if (in_degree[v] == 0) {
            cur_buf[cur_size++] = v;
        }
    }

    while (cur_size > 0) {
        level_sizes[num_levels++] = cur_size;
        nxt_size = 0;
        for (int j = 0; j < cur_size; j++) {
            int u = cur_buf[j];
            order[count++] = u;
            for (int i = g->head[u]; i != -1; i = g->edges[i].next) {
                int v = g->edges[i].to;
                if (--in_degree[v] == 0) {
                    nxt_buf[nxt_size++] = v;
                }
            }
        }
        memcpy(cur_buf, nxt_buf, sizeof(int) * nxt_size);
        cur_size = nxt_size;
    }

    return (count == n) ? num_levels : -1;
}

/* ---- 测试 ---- */

static void print_order(const int *order, int n) {
    for (int i = 0; i < n; i++) {
        printf("%d%s", order[i], (i < n - 1) ? " -> " : "\n");
    }
}

int main(void) {
    Graph g;
    int order[MAX_VERTICES];
    int level_sizes[MAX_VERTICES];

    /*
     * 测试图:
     * 0 -> 2, 0 -> 3
     * 1 -> 3
     * 2 -> 4
     * 3 -> 4
     * 4 -> 5
     */
    graph_init(&g, 6);
    graph_add_edge(&g, 0, 2);
    graph_add_edge(&g, 0, 3);
    graph_add_edge(&g, 1, 3);
    graph_add_edge(&g, 2, 4);
    graph_add_edge(&g, 3, 4);
    graph_add_edge(&g, 4, 5);

    printf("=== Kahn (BFS) ===\n");
    int cnt = kahn_topo_sort(&g, order);
    if (cnt == g.vertex_count) {
        print_order(order, cnt);
    } else {
        printf("Cycle detected!\n");
    }

    printf("\n=== DFS ===\n");
    cnt = dfs_topo_sort(&g, order);
    if (cnt > 0) {
        print_order(order, cnt);
    } else {
        printf("Cycle detected!\n");
    }

    printf("\n=== Level-by-level ===\n");
    int levels = level_topo_sort(&g, order, level_sizes);
    if (levels > 0) {
        int offset = 0;
        for (int lv = 0; lv < levels; lv++) {
            printf("Level %d: ", lv);
            for (int j = 0; j < level_sizes[lv]; j++) {
                printf("%d ", order[offset + j]);
            }
            printf("\n");
            offset += level_sizes[lv];
        }
    } else {
        printf("Cycle detected!\n");
    }

    /* 测试有环的图 */
    printf("\n=== Cycle test ===\n");
    Graph g2;
    graph_init(&g2, 3);
    graph_add_edge(&g2, 0, 1);
    graph_add_edge(&g2, 1, 2);
    graph_add_edge(&g2, 2, 0);

    cnt = kahn_topo_sort(&g2, order);
    printf("Kahn: %s\n", (cnt == g2.vertex_count) ? "OK" : "Cycle!");

    cnt = dfs_topo_sort(&g2, order);
    printf("DFS:  %s\n", (cnt > 0) ? "OK" : "Cycle!");

    return 0;
}

编译与运行：

gcc -O2 -Wall -Wextra -o topo_sort topo_sort.c
./topo_sort

预期输出：

=== Kahn (BFS) ===
0 -> 1 -> 2 -> 3 -> 4 -> 5

=== DFS ===
0 -> 1 -> 2 -> 3 -> 4 -> 5

=== Level-by-level ===
Level 0: 0 1
Level 1: 2 3
Level 2: 4
Level 3: 5

=== Cycle test ===
Kahn: Cycle!
DFS:  Cycle!

实现要点：

  1. 邻接表用链式前向星（head + next 指针模拟链表）：避免动态内存分配，缓存友好
  2. DFS 用递归实现：真实的生产代码应该用显式栈避免爆栈。Linux 默认线程栈大小是 8MB，对于百万级节点的图，递归 DFS 会溢出
  3. 环检测用三色标记：比额外维护一个”当前路径”集合更高效
  4. 层级排序用双缓冲：cur_buf 和 nxt_buf 交替使用，避免频繁的内存分配

九、依赖解析：包管理器的拓扑排序

apt/dpkg

Debian 的包管理是最早系统性使用拓扑排序的软件之一。dpkg 在安装一组 .deb 包时，需要确定安装顺序使得每个包的依赖在它之前被配置。

依赖关系示例：
  libc6 -> (无依赖)
  libssl3 -> libc6
  openssl -> libssl3, libc6
  nginx -> openssl, libssl3, libc6, libpcre3

拓扑序：libc6 -> libpcre3 -> libssl3 -> openssl -> nginx

dpkg 的实际实现比这复杂得多。它需要处理：

npm

npm 从 v3 开始采用扁平化的 node_modules 结构。安装过程：

  1. 解析所有包的依赖，构建依赖图
  2. 检测循环依赖（警告但不阻止）
  3. 对依赖图做拓扑排序，确定安装顺序
  4. 尽可能将包提升（hoist）到顶层 node_modules，减少重复

npm 的依赖图实际上不是严格的 DAG——JavaScript 的 require() 允许循环依赖。Node.js 的处理方式是返回一个”部分构建”的 module.exports 对象。这在实践中经常导致难以调试的 bug。

Cargo

Rust 的 Cargo 是最严格的包管理器之一。它的依赖解析过程：

  1. 从 Cargo.toml 读取直接依赖
  2. 递归解析传递依赖，构建完整的依赖图
  3. 版本解析（SAT 求解的变体）
  4. 拓扑排序确定编译顺序
  5. 按层并行编译（cargo build -j N）

Cargo 不允许编译期循环依赖。如果 crate A 依赖 crate B 且 B 依赖 A，编译直接失败。但同一个 crate 内的模块之间可以有循环引用。

三者的对比

特性 apt/dpkg npm Cargo
循环依赖 通过两阶段安装处理 允许，运行时延迟解析 编译期禁止
并行安装 有限支持 支持 充分支持
依赖图规模 数千包 可达数万包 通常数百 crate
版本冲突 同一包只能一个版本 允许多版本共存 语义化版本解析
拓扑排序变体 两阶段 Kahn 带环处理的 Kahn 标准 Kahn + 并行层

十、构建系统中的拓扑排序

Make

Make 是最早的基于依赖图的构建工具（1976 年，Stuart Feldman 在贝尔实验室发明）。一个 Makefile 本质上就是一个 DAG 的声明：

# 目标: 依赖列表
main: main.o utils.o network.o
    $(CC) -o main main.o utils.o network.o

main.o: main.c utils.h network.h
    $(CC) -c main.c

utils.o: utils.c utils.h
    $(CC) -c utils.c

network.o: network.c network.h utils.h
    $(CC) -c network.c

这隐含了一个 DAG：

main.c ──> main.o ──┐
utils.h ──> main.o  │
network.h -> main.o │
utils.c ──> utils.o ──> main
utils.h ──> utils.o    │
network.c -> network.o ┘
network.h -> network.o
utils.h ──> network.o

make -j4 的执行过程：

  1. 解析 Makefile，构建依赖 DAG
  2. 对 DAG 做拓扑排序（层级版本）
  3. 第一层：并行编译 main.o、utils.o、network.o（最多 4 个 job）
  4. 第二层：链接 main（必须等第一层全部完成）

Make 的一个著名问题是”递归 Make 有害”（Recursive Make Considered Harmful，Peter Miller 1997）。当使用递归 Make 时，每个子目录的 Makefile 独立构建自己的依赖图，无法看到全局的 DAG，导致： - 依赖可能遗漏，造成增量构建错误 - 无法跨目录并行 - 串行的递归调用成为瓶颈

Bazel

Bazel（和它的前身 Blaze）解决了 Make 的根本问题：它维护一个全局的依赖图，覆盖整个代码仓库。

Bazel 的构建模型有两层图：

  1. Target Graph：由 BUILD 文件定义的目标（library、binary、test）之间的依赖
  2. Action Graph：将 Target Graph 展开为具体的编译/链接动作，每个动作有精确的输入和输出文件

Action Graph 是真正被拓扑排序和并行执行的 DAG。Bazel 的调度器使用一种贪心的”就绪即执行”策略，本质上就是 Kahn 算法的在线变体：维护一个”就绪队列”（所有前驱已完成的 action），从中取出 action 分配给空闲的 worker。

Bazel 执行流程:
  1. 加载阶段：解析 BUILD 文件，构建 Target Graph
  2. 分析阶段：展开 Target Graph 为 Action Graph
  3. 执行阶段：拓扑排序 + 并行调度 Action Graph

Bazel 相比 Make 的优势直接来源于全局 DAG： - 精确的增量构建：只重新执行输入发生变化的 action - 最大化并行度：全局 DAG 暴露了所有可并行的 action - 远程执行：将 action 发送到远程 worker，DAG 的拓扑关系保证了正确性 - 缓存：相同输入的 action 可以复用缓存结果（远程缓存或本地缓存）

十一、任务调度与真实场景

带依赖的任务调度

操作系统、数据库和大数据系统中，任务调度是拓扑排序最直接的应用。考虑一个简化的 MapReduce 风格的工作流：

任务 DAG:
  Extract_A ──> Transform_A ──> Load_A ──┐
  Extract_B ──> Transform_B ──> Load_B ──┤──> Aggregate -> Report
  Extract_C ──> Transform_C ──> Load_C ──┘

调度器的工作： 1. 拓扑排序得到执行层级 2. Layer 0: Extract_A, Extract_B, Extract_C（完全并行） 3. Layer 1: Transform_A, Transform_B, Transform_C（完全并行） 4. Layer 2: Load_A, Load_B, Load_C（完全并行） 5. Layer 3: Aggregate（必须等所有 Load 完成） 6. Layer 4: Report

Apache Airflow 就是这样工作的。它的核心数据结构是 DAG（Airflow 甚至把工作流直接叫做 DAG），调度器对每个 DAG 做拓扑排序来确定任务的执行顺序。

电子表格重新计算

Excel 和 Google Sheets 的每一次单元格编辑，都触发一次拓扑排序。

假设有以下公式：

A1 = 10
B1 = 20
C1 = A1 + B1
D1 = C1 * 2
E1 = C1 + D1

依赖图：A1 -> C1，B1 -> C1，C1 -> D1，C1 -> E1，D1 -> E1

当用户修改 A1 时： 1. 标记 A1 为”脏” 2. 通过依赖图找到所有传递依赖于 A1 的单元格：C1, D1, E1 3. 对这些脏单元格做拓扑排序：C1 -> D1 -> E1 4. 按此顺序重新计算

现代电子表格（如 Google Sheets）还支持跨 sheet 引用，这使得依赖图可以跨越多个工作表。如果用户创建了循环引用（A1 = B1, B1 = A1），电子表格会检测到环并显示错误。

课程先修关系

大学的课程体系是一个经典的 DAG：

高等数学 ──> 线性代数 ──> 数值分析
高等数学 ──> 概率论 ──> 机器学习
程序设计 ──> 数据结构 ──> 算法设计
程序设计 ──> 操作系统
数据结构 ──> 操作系统
数据结构 ──> 编译原理
离散数学 ──> 数据结构
离散数学 ──> 编译原理

学生选课就是在这个 DAG 上做拓扑排序。每学期能选的课就是”当前层”——所有先修课已完成的课程。最少多少个学期能毕业？就是 DAG 的层数（假设每学期可以选无限门课）。实际中受限于每学期最多选 N 门课，问题变成了一个带资源约束的调度问题。

编译器指令调度

编译器后端在生成机器代码时，需要对指令做调度（instruction scheduling）。指令之间的数据依赖形成 DAG：

r1 = load [addr]     # 可能需要多个时钟周期
r2 = r1 + 1          # 依赖 r1
r3 = load [addr2]    # 与 r1 无关，可以和上面的 load 并行
r4 = r3 * 2          # 依赖 r3
r5 = r2 + r4         # 依赖 r2 和 r4

编译器对这个指令 DAG 做拓扑排序，然后尝试在同一层放置可以并行执行的指令（利用处理器的流水线和多功能单元）。这就是所谓的指令级并行（ILP, Instruction-Level Parallelism）。

十二、工程陷阱与个人思考

工程陷阱总结

以下是在工程实践中使用拓扑排序时常见的坑：

陷阱 描述 后果 解决方案
隐式依赖 依赖关系没有显式声明，靠文件系统顺序碰巧工作 增量构建失败，并行构建失败 显式声明所有依赖，用工具检查完整性
动态依赖 依赖关系在运行时才能确定（如 C 的 #include） 依赖图不完整，遗漏重新编译 构建时记录实际依赖（gcc -M），下次构建使用
钻石依赖 A -> B -> D, A -> C -> D，D 的版本可能冲突 链接错误、运行时崩溃 统一版本管理（Cargo 的解析器、Go modules）
超大 DAG 数百万节点的依赖图 拓扑排序的内存和时间成本 增量拓扑排序、分区处理
非确定性 同一 DAG 可能有多种合法拓扑序 不同机器上构建结果不同 用字典序最小拓扑序保证确定性
虚假依赖 为了”安全”添加不必要的依赖 关键路径变长，并行度降低 定期审查依赖图，移除不必要的边
环的误报 将双向通信误认为循环依赖 项目结构被迫扭曲 区分编译依赖和运行时通信
递归深度 DFS 实现在深图上栈溢出 程序崩溃 改用显式栈或迭代 Kahn

增量拓扑排序

当依赖图频繁变化时（如 IDE 中编辑代码时依赖关系随时可能改变），从头跑一遍完整的拓扑排序代价太高。增量拓扑排序（Incremental Topological Sort）只更新受影响的部分。

基本思路：当添加一条边 (u, v) 时，如果 u 在当前拓扑序中排在 v 后面，那么需要重新调整 u 和 v 之间的节点的顺序。如果添加边后形成了环，则报错。

Marchetti-Spaccamela、Nanni 和 Rohnert（1996）给出了均摊 O(V) 每次更新的算法。Bender、Fineman 和 Gilbert（2009）改进到了均摊 O(V^{2/3}) 每次边插入。这些算法在 IDE 的语言服务器中被广泛使用。

拓扑排序与强连通分量

Tarjan 的强连通分量（SCC）算法和拓扑排序有深层联系。将有向图缩点（把每个 SCC 缩成一个点）后，得到的”缩点图”（condensation graph）一定是 DAG。对这个 DAG 做拓扑排序，就得到了 SCC 之间的依赖顺序。

这在编译器中用于处理模块之间的循环依赖： 1. 找出所有 SCC（Tarjan 算法） 2. 同一个 SCC 内的模块必须一起编译 3. SCC 之间按拓扑序编译

Haskell 的 GHC 编译器正是这样处理 .hs 文件之间的 import 循环的。

个人思考

工程中使用拓扑排序这些年，我最深的体会有三点：

第一，依赖图的质量比排序算法重要一百倍。Kahn 也好，DFS 也好，算法本身从来不是瓶颈。真正的问题是：你的依赖图正确吗？完整吗？有没有遗漏的隐式依赖？有没有多余的虚假依赖？构建系统的大部分 bug 都出在依赖图的声明上，而不是排序算法上。

第二，非确定性是万恶之源。当拓扑序不唯一时（这是常态），不同的运行可能得到不同的执行顺序。如果你的系统对执行顺序有隐含假设（比如假设 A 总是在 B 之前），那这个假设可能在某次构建中被打破。解决方案是要么用字典序最小拓扑序保证确定性，要么确保系统在任何合法拓扑序下都能正确工作。

第三，可视化是调试的唯一手段。当构建系统出现问题时，打印拓扑排序的结果几乎没用——你需要看到整个 DAG 的图形化表示。dot（Graphviz）是这里的标配工具。bazel query --output graph | dot -Tsvg 可以输出构建图的 SVG。当你第一次看到一个几千节点的依赖图时，通常会发现意想不到的依赖路径。

拓扑排序本身是一个简单的算法——O(V + E) 的复杂度，几十行代码就能实现。但围绕它建立的工程生态（构建系统、包管理器、任务调度器）却是软件工程中最复杂的领域之一。算法教科书教你怎么写 Kahn 算法，却不会告诉你当 node_modules 有三万个包、依赖图有十万条边、还有几百个循环依赖时该怎么办。这才是真正的挑战——不在于排序，而在于在混乱的现实中构建出一个足够正确的 DAG。

上一篇: 网络流与二分匹配 下一篇: PageRank 与随机游走 相关阅读: - Tarjan 算法族 - 进程调度

By .