auto_ai 知识库

Appearance

拓扑排序（Topological Sort）是对有向无环图（DAG）的顶点进行排序，使得对于任意一条有向边 u→v，顶点 u 都排在 v 之前。它不是传统意义上的"排序"，而是一种线性排列，反映了顶点之间的依赖关系。

定义与核心原理 ​

前提条件 ​

  • 图必须是有向无环图（DAG, Directed Acyclic Graph）
  • 有环图不存在拓扑排序
  • 拓扑排序结果可能不唯一

核心思想 ​

每次选择入度为 0 的顶点输出，然后删除该顶点及其出边，重复直到所有顶点输出。

操作步骤 ​

Kahn 算法（BFS 实现） ​

1. 计算所有顶点的入度
2. 将所有入度为 0 的顶点入队
3.  while 队列非空：
    a. 出队顶点 u，加入结果
    b. 遍历 u 的所有邻接顶点 v
    c. v 的入度减 1
    d. 如果 v 的入度变为 0，入队
4. 如果结果长度 < 顶点数 → 图有环

代码实现 ​

cpp
vector<int> topologicalSort(int n, vector<vector<int>>& adj) {
    vector<int> indegree(n, 0);
    for (int u = 0; u < n; u++)
        for (int v : adj[u])
            indegree[v]++;
    
    queue<int> q;
    for (int i = 0; i < n; i++)
        if (indegree[i] == 0) q.push(i);
    
    vector<int> result;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        result.push_back(u);
        for (int v : adj[u]) {
            indegree[v]--;
            if (indegree[v] == 0) q.push(v);
        }
    }
    return result;  // size < n 说明有环
}

示例图 ​

有向图：1→2, 1→3, 1→5, 2→3, 5→3（顶点 4 孤立）

入度：1=0, 2=1, 3=3, 4=0, 5=1

步骤1：入度为0的顶点 {1, 4}，选 1 输出
  删除 1 的出边：2入度→0, 3入度→2, 5入度→0
步骤2：入度为0的顶点 {4, 2, 5}，选 4 输出（孤立点）
步骤3：选 2 输出，删除 2→3：3入度→1
步骤4：选 5 输出，删除 5→3：3入度→0
步骤5：选 3 输出

一种拓扑序：1, 4, 2, 5, 3

复杂度分析 ​

操作时间复杂度空间复杂度
Kahn 算法O(V+E)O(V)
DFS 实现O(V+E)O(V)

实践应用 ​

  • 课程安排：先修课关系，确定选课顺序
  • 任务调度：有依赖关系的任务执行顺序
  • 编译系统：Makefile 中文件的编译顺序
  • 关键路径：AOE 网中求最早/最晚开始时间
  • 检测环：拓扑排序结果不完整说明图有环

常见误区 ​

  1. 有环图也能拓扑排序：只有 DAG 才有拓扑排序，有环图无法完成
  2. 结果唯一：拓扑序通常不唯一，入度为 0 的顶点选择顺序不同结果不同
  3. 孤立顶点：入度为 0 的孤立顶点可以在任意位置输出
  4. 混淆入度和出度：Kahn 算法用入度，每次选入度为 0 的点

一句话总结 ​

拓扑排序只对 DAG 有效：Kahn 算法反复取出入度为 0 的顶点入队，复杂度 O(V+E)；结果长度小于顶点数就说明图中有环。

相关概念 ​